跳到主要内容

第 13 章 · 递归类型

读完本章你会
  • 掌握类型层递归的「骨架」：拆一步 → 递归 → 组合 + 终止条件
  • 处理嵌套结构：DeepReadonly、DeepPartial、Flatten
  • 理解递归深度的边界，知道 TS 什么时候会「撑不住」
  • 组合「分布式条件 + 递归」处理联合的排列组合问题
  • 用「递归 + 相等判定」实现 Includes、Unique 这类集合操作
本章是「类型体操」的正式起点

第 5-8 章是语法，第 13 章开始是算法。从这里起，你把类型系统当成一台「只有递归和条件分支的图灵机」来用。之后的第 14-17 章全是本章招式的组合。

13.1 递归的骨架​

类型层的递归和函数递归长得几乎一样。看一个最典型的例子——Flatten（打平嵌套数组）：

type Flatten<T extends any[]> =
  T extends [infer F, ...infer Rest]
    ? F extends any[]                       // 第一个元素是数组吗？
      ? [...Flatten<F>, ...Flatten<Rest>]   // 是 → 递归展开它
      : [F, ...Flatten<Rest>]               // 否 → 保留，继续处理剩余
    : []                                    // 拆空了 → 终止

type R = Flatten<[1, [2, [3]], 4]> // [1, 2, 3, 4]

每一层递归都在做三件事：

1. 拆一步     → T extends [infer F, ...infer Rest]
2. 递归 + 组合 → 把 F、Rest 分别喂给自己，再把结果拼回
3. 终止条件    → 拆不动时的 else（这里：[] ）
直觉：递归 = 「在类型里写循环」

TS 类型没有循环语法，递归就是循环。每一层处理一个元素/一层结构，直到没有可拆的。看不懂时，就把它当成「一个处理数组的递归函数，只不过处理的是类型」。

13.2 深度变换：DeepReadonly / DeepPartial​

13.2.1 先看「浅层」再想「深层」​

第 6 章的 Readonly 只处理一层：

type Shallow = Readonly<{ a: string; b: { c: number } }>
// { readonly a: string; readonly b: { c: number } }  ← b 内部没变

DeepReadonly 要把每一层都加 readonly——这就是递归的用武之地。

13.2.2 DeepReadonly：逐层递归 + 保底​

type DeepReadonly<T> = T extends any            // 先分发联合
  ? keyof T extends never                       // 函数/原始类型的 keyof 是 never
    ? T                                          //    → 原样返回（保底）
    : { readonly [P in keyof T]: DeepReadonly<T[P]> } // 对象 → 逐属性递归
  : never

type X = {
  a: string
  b: { c: { d: boolean } }
}
type R = DeepReadonly<X>
// { readonly a: string; readonly b: { readonly c: { readonly d: boolean } } }
三个关键点
  1. 先分发联合（T extends any）：让联合的每个成员单独递归，否则 keyof (A | B) 会塌成 never（第 2 章说过 keyof 联合 是键的交集）。
  2. 保底分支（keyof T extends never ? T）：函数、string、number 这些 keyof 为 never 的类型，直接原样返回，不能强行递归。
  3. 同态映射保留结构（{ readonly [P in keyof T]: ... }）：T 是数组/元组时，结果仍是数组/元组。

13.2.3 DeepPartial：一样的骨架，改一个修饰符​

type DeepPartial<T> = T extends any
  ? keyof T extends never
    ? T
    : { [P in keyof T]?: DeepPartial<T[P]> }   // 只把 ? 加进去
  : never
一眼看懂 Deep 系列

DeepXxx<T> 几乎都是同一个模板：

type DeepXxx<T> = T extends any
  ? keyof T extends never ? T
  : { [P in keyof T] 修饰符: DeepXxx<T[P]> }
  : never

区别只在「修饰符」（readonly / ? / 值变换）。学会一个，Deep 系列全会。

13.3 集合操作：Includes / Unique​

13.3.1 Includes：递归遍历数组，用严格相等比较​

type Equal<X, Y> =                         // 严格相等（第 12 章）
  (<T>() => T extends X ? 1 : 2) extends
  (<T>() => T extends Y ? 1 : 2) ? true : false

type Includes<T extends readonly any[], U> =
  T extends [infer F, ...infer Rest]
    ? Equal<F, U> extends true ? true : Includes<Rest, U>
    : false

type A = Includes<[1, 2, 3], 2>  // true
type B = Includes<[1, 2, 3], 4>  // false
为什么必须用 Equal 而不是 extends

Includes<[1 | 2], 1> 应该是 false——1 并不是数组里「存在 1 这个精确元素」，数组里只有一个 1 | 2。用 Equal（函数签名比较）能区分 1 和 1 | 2、区分 {} 和 { a: 'A' }；用 A extends B 会误判成 true。集合操作一律用严格相等。

13.3.2 Unique：去重 = Includes + 累积​

去重需要一个「已收集」的累积参数：

type Unique<T extends any[], R extends any[] = []> =
  T extends [infer F, ...infer Rest]
    ? Includes<R, F> extends true
      ? Unique<Rest, R>          // 已经收集过 → 跳过
      : Unique<Rest, [...R, F]>  // 没收集过 → 记进 R
    : R                          // 拆完 → 返回 R

type A = Unique<[1, 1, 2, 2, 3]> // [1, 2, 3]
累积参数是递归的核心手法

R 这种「带在参数里、一路累积」的写法，等价于函数里的「累加器」。它让递归不只是「拆解」，还能构建结果。Unique、Reverse、IndexOf（第 14 章）全是它。

13.4 分布式 + 递归：Permutation 排列​

Permutation<'A' | 'B' | 'C'> 生成全排列，是「分布式条件类型」和「递归」联动的代表作：

type Permutation<T, U = T> =
  [T] extends [never]
    ? []                                        // 空 → 终止
    : T extends any                             // 分发：对每个成员 T 单独做
      ? [T, ...Permutation<Exclude<U, T>>]      // 取一个 → 剩余递归全排
      : never

type R = Permutation<'A' | 'B'>
// ['A', 'B'] | ['B', 'A']
拆解这段
  • U = T：先把完整联合存进默认参数 U，否则分发后 T 只剩单个成员，Exclude 无从谈起
  • T extends any：把联合分发成「每次处理一个成员」
  • Exclude<U, T>：从完整联合里去掉当前成员，得到「剩余」
  • 递归对剩余做全排列，当前成员放最前

「分发一次 + 递归剩余」= 排列问题的标准解。00296 Permutation 就是它。

13.5 递归深度与优化​

13.5.1 TS 的深度上限​

递归类型有实例化深度上限（TS 6 大约几千层）。超出会报：

Type instantiation is excessively deep and possibly infinite.

比如 MinusOne<9007199254740992>（第 17 章）如果用「每次建一个元素、数到 N」的元组法，会直接撑爆——必须换思路（字符串算术）。

13.5.2 减小深度：尾递归​

TS 4.5+ 对「条件类型里最后一步是递归调用」的情况做了尾递归消除，深度能到几千而不爆：

// 非尾递归：每次递归后还有 [...A, F] 要算
type ReverseBad<T extends any[]> =
  T extends [infer F, ...infer R] ? [...ReverseBad<R>, F] : []

// 尾递归（用累积参数）：递归是「最后一步」
type ReverseGood<T extends any[], R extends any[] = []> =
  T extends [infer F, ...infer Rest] ? ReverseGood<Rest, [F, ...R]> : R
写递归的两条经验
  1. 能用累积参数就累积——把「要构建的结果」放到参数里，既快又不易爆
  2. 别靠蛮力数到 N——需要「数到某个大数」时，优先想字符串算术/数学规律，而不是建元组

本章小结​

  • 递归骨架：拆一步 → 递归 + 组合 → 终止；Flatten 是最干净的入门例
  • Deep 系列：T extends any 分发 + keyof T extends never 保底 + 同态映射递归
  • 集合操作用严格 Equal，Unique 靠累积参数
  • 排列 = 分发一次 + 递归剩余
  • 递归深度有上限；累积参数尾递归能撑更远

本章练习​

挑战题​

题号题目难度考察点
00898Includeseasy递归 + Equal
00459Flattenmedium嵌套数组递归
00009对象属性只读（递归）mediumDeepReadonly 全解
02070Drop Charmedium字符串递归删字符
00296Permutationmedium分发 + 递归排列
03243FlattenDepthmedium带层数计数的递归

代码练习

  1. Flatten 变体：给 Flatten 加一个「最多展开 N 层」的版本 FlattenDepth（提示：加一个 Count extends any[] = [] 累积层数，到 N 就不再展开）。

  2. DeepPartial：实现 DeepPartial<T>（13.2.3），验证对 { a: { b: { c: number } } } 得到全嵌套可选。

  3. DeepReadonly 函数保底：验证 DeepReadonly<{ f: () => number }> 里 f 保持 () => number 不被递归（体会 keyof T extends never 的保底）。

  4. DropChar：实现 type DropChar<S, C> 从字符串里删掉所有 C（递归 + 模板匹配），并思考 C 为空串时为什么必须返回 never（防止死循环）。

  5. 递归 + 分发：实现 type Includes 后，再用累积参数实现 type RemoveItem<T, U>（从元组里删掉所有等于 U 的元素）。