递归类型定义

递归类型定义的基本概念

递归类型定义允许类型在自身内部引用自身。这种特性在处理树形结构、链表、嵌套数据等场景时非常有用。TypeScript 完全支持递归类型，使得类型系统能够描述复杂的数据形状。

type TreeNode = {
  value: number;
  left?: TreeNode;
  right?: TreeNode;
};

这个简单的 TreeNode 类型定义了一个二叉树节点，其中 left 和 right 属性又引用了 TreeNode 类型本身。这种自引用就是递归类型的核心特征。

递归类型与泛型结合

递归类型可以与泛型结合，创建更灵活的类型定义。泛型参数可以在递归过程中保持类型信息。

type LinkedList<T> = {
  value: T;
  next?: LinkedList<T>;
};

const list: LinkedList<number> = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3
    }
  }
};

这个 LinkedList<T> 类型定义了一个泛型链表，其中每个节点包含一个 value 和可选的 next 节点。通过泛型参数 T，我们可以确保链表中所有节点的 value 类型一致。

条件类型中的递归

TypeScript 的条件类型也支持递归，这可以用来创建复杂的类型转换工具。

type DeepReadonly<T> = {
  readonly [P in keyof T]: T[P] extends object ? DeepReadonly<T[P]> : T[P];
};

interface User {
  name: string;
  address: {
    street: string;
    city: string;
  };
}

const user: DeepReadonly<User> = {
  name: "Alice",
  address: {
    street: "123 Main St",
    city: "Wonderland"
  }
};

// 以下操作会在编译时报错
// user.name = "Bob"; 
// user.address.city = "Nowhere";

DeepReadonly 类型递归地将对象及其所有嵌套属性转换为只读。当遇到对象类型的属性时，它会递归地应用 DeepReadonly。

递归类型限制与尾递归优化

虽然递归类型强大，但需要注意递归深度限制。TypeScript 对递归深度有一定限制，过深的递归可能导致类型检查性能问题或错误。

// 这个类型可能会达到递归深度限制
type InfiniteRecursion<T> = {
  value: T;
  next: InfiniteRecursion<T>;
};

对于特别深的递归类型，可以考虑使用尾递归优化的形式：

type TailRecursion<T, Acc = never> = T extends infer U 
  ? TailRecursion<U, Acc | U> 
  : Acc;

递归类型在实战中的应用

JSON 数据类型

递归类型非常适合描述 JSON 数据的完整类型：

type JSONValue = 
  | string 
  | number 
  | boolean 
  | null 
  | JSONObject 
  | JSONArray;

interface JSONObject {
  [key: string]: JSONValue;
}

interface JSONArray extends Array<JSONValue> {}

这个定义完整描述了所有可能的 JSON 值类型，包括嵌套对象和数组。

组件 Props 类型

在前端框架中，递归类型可以用于定义复杂组件的 props 类型：

type MenuItem = {
  title: string;
  children?: MenuItem[];
};

const menuData: MenuItem[] = [
  {
    title: "Home"
  },
  {
    title: "Products",
    children: [
      {
        title: "Electronics",
        children: [
          { title: "Phones" },
          { title: "Laptops" }
        ]
      }
    ]
  }
];

AST (抽象语法树) 类型

处理语言或表达式时，递归类型可以完美描述 AST 结构：

type Expression = 
  | { type: "literal"; value: number }
  | { type: "variable"; name: string }
  | { type: "binary"; operator: "+" | "-" | "*" | "/"; left: Expression; right: Expression }
  | { type: "call"; callee: string; args: Expression[] };

const ast: Expression = {
  type: "binary",
  operator: "+",
  left: { type: "literal", value: 1 },
  right: {
    type: "binary",
    operator: "*",
    left: { type: "variable", name: "x" },
    right: { type: "literal", value: 2 }
  }
};

递归类型与类型推断

TypeScript 的类型推断能够很好地处理递归类型。例如，当使用递归类型作为函数参数时，类型检查器会正确推断嵌套结构的类型。

function traverseTree(node: TreeNode, callback: (value: number) => void) {
  callback(node.value);
  if (node.left) traverseTree(node.left, callback);
  if (node.right) traverseTree(node.right, callback);
}

const tree: TreeNode = {
  value: 1,
  left: {
    value: 2,
    left: { value: 4 },
    right: { value: 5 }
  },
  right: {
    value: 3
  }
};

traverseTree(tree, value => console.log(value));
// 输出: 1, 2, 4, 5, 3

递归类型与模板字面量类型

TypeScript 4.1 引入的模板字面量类型也可以与递归类型结合，创建强大的字符串模式匹配类型。

type JoinPath<T extends string[]> = 
  T extends [infer First, ...infer Rest]
    ? First extends string
      ? Rest extends string[]
        ? `${First}${Rest extends [] ? "" : "/"}${JoinPath<Rest>}`
        : never
      : never
    : "";

type Path = JoinPath<["user", "profile", "settings"]>;
// 类型为 "user/profile/settings"

递归类型与条件类型的高级组合

结合递归和条件类型，可以创建复杂的类型工具，如深度可选类型、深度必选类型等。

type DeepPartial<T> = {
  [P in keyof T]?: T[P] extends object ? DeepPartial<T[P]> : T[P];
};

type DeepRequired<T> = {
  [P in keyof T]-?: T[P] extends object ? DeepRequired<T[P]> : T[P];
};

interface Settings {
  user: {
    name: string;
    preferences?: {
      theme: string;
      notifications?: boolean;
    };
  };
}

const partialSettings: DeepPartial<Settings> = {
  user: {
    preferences: {}
  }
};

const requiredSettings: DeepRequired<Settings> = {
  user: {
    name: "Alice",
    preferences: {
      theme: "dark",
      notifications: true
    }
  }
};

递归类型与映射类型的结合

映射类型可以与递归类型结合，创建更灵活的类型转换工具。

type CamelCase<S extends string> = 
  S extends `${infer First}_${infer Rest}`
    ? `${Lowercase<First>}${Capitalize<CamelCase<Rest>>}`
    : Lowercase<S>;

type SnakeToCamel<T> = {
  [K in keyof T as CamelCase<string & K>]: 
    T[K] extends object ? SnakeToCamel<T[K]> : T[K];
};

interface SnakeCaseUser {
  user_name: string;
  user_age: number;
  address_info: {
    street_name: string;
    postal_code: string;
  };
}

type CamelCaseUser = SnakeToCamel<SnakeCaseUser>;
/* 等同于:
{
  userName: string;
  userAge: number;
  addressInfo: {
    streetName: string;
    postalCode: string;
  };
}
*/

递归类型与 infer 关键字

infer 关键字在递归类型中特别有用，可以用来提取和转换嵌套类型。

type UnpackArray<T> = 
  T extends (infer U)[] ? UnpackArray<U> : T;

type NestedArray = number[][][][];
type Unpacked = UnpackArray<NestedArray>; // number

递归类型与联合类型

递归类型可以与联合类型结合，处理更复杂的类型场景。

type Expression = 
  | { type: "number"; value: number }
  | { type: "string"; value: string }
  | { type: "binary"; operator: string; left: Expression; right: Expression }
  | { type: "call"; fn: string; args: Expression[] };

function evaluate(expr: Expression): any {
  switch (expr.type) {
    case "number":
      return expr.value;
    case "string":
      return expr.value;
    case "binary":
      const left = evaluate(expr.left);
      const right = evaluate(expr.right);
      // 实际实现中需要更安全的操作符处理
      return eval(`${left} ${expr.operator} ${right}`);
    case "call":
      // 实际实现中需要函数查找逻辑
      return expr.fn + "(" + expr.args.map(evaluate).join(", ") + ")";
  }
}

递归类型与类型守卫

在处理递归类型时，类型守卫可以帮助缩小类型范围。

function isTreeNode(node: any): node is TreeNode {
  return node && 
         typeof node.value === "number" &&
         (node.left === undefined || isTreeNode(node.left)) &&
         (node.right === undefined || isTreeNode(node.right));
}

function processNode(node: unknown) {
  if (isTreeNode(node)) {
    // 在这里 node 被推断为 TreeNode 类型
    console.log(node.value);
    if (node.left) processNode(node.left);
    if (node.right) processNode(node.right);
  }
}

递归类型与索引访问类型

索引访问类型可以与递归类型结合，创建动态的类型查询。

type PathImpl<T, Key extends keyof T> =
  Key extends string
    ? T[Key] extends Record<string, any>
      ? `${Key}.${PathImpl<T[Key], keyof T[Key]>}`
      : Key
    : never;

type Path<T> = PathImpl<T, keyof T>;

interface User {
  name: string;
  address: {
    street: string;
    city: string;
    coordinates: {
      lat: number;
      lng: number;
    };
  };
}

type UserPath = Path<User>;
// "name" | "address" | "address.street" | "address.city" | 
// "address.coordinates" | "address.coordinates.lat" | "address.coordinates.lng"

递归类型与可变元组类型

TypeScript 4.0 引入的可变元组类型可以与递归类型结合。

type Reverse<T extends any[]> = 
  T extends [infer First, ...infer Rest] 
    ? [...Reverse<Rest>, First] 
    : [];

type Original = [1, 2, 3, 4];
type Reversed = Reverse<Original>; // [4, 3, 2, 1]

递归类型与模板递归限制

虽然递归类型强大，但需要注意 TypeScript 对递归深度的限制。对于特别深的递归，可能需要使用迭代方式或调整递归策略。

// 这个类型可能会达到递归深度限制
type DeepArray<T> = T | DeepArray<T>[];

// 更安全的替代方案
type SafeDeepArray<T> = T | SafeDeepArray<T>[];

递归类型与性能考量

复杂的递归类型可能会影响类型检查性能。在大型项目中，需要权衡类型表达的精确性和编译性能。

// 简单的递归类型通常性能良好
type SimpleTree = {
  value: number;
  children?: SimpleTree[];
};

// 非常复杂的递归条件类型可能会影响性能
type ComplexTransform<T> = 
  T extends object 
    ? { [K in keyof T]: ComplexTransform<T[K]> } 
    : T;