Recursive type definition

Basic Concepts of Recursive Type Definitions

Recursive type definitions allow types to reference themselves within their own definitions. This feature is particularly useful for handling tree structures, linked lists, nested data, and similar scenarios. TypeScript fully supports recursive types, enabling the type system to describe complex data shapes.

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

This simple TreeNode type defines a binary tree node where the left and right properties reference the TreeNode type itself. This self-referential nature is the core characteristic of recursive types.

Combining Recursive Types with Generics

Recursive types can be combined with generics to create more flexible type definitions. Generic parameters can preserve type information during recursion.

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

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

This LinkedList<T> type defines a generic linked list where each node contains a value and an optional next node. The generic parameter T ensures that all nodes in the list have consistent value types.

Recursion in Conditional Types

TypeScript's conditional types also support recursion, which can be used to create complex type transformation utilities.

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"
  }
};

// The following operations would cause compile-time errors
// user.name = "Bob"; 
// user.address.city = "Nowhere";

The DeepReadonly type recursively converts an object and all its nested properties to read-only. When encountering object-type properties, it recursively applies DeepReadonly.

Recursive Type Limitations and Tail Recursion Optimization

While recursive types are powerful, it's important to be aware of recursion depth limits. TypeScript has certain restrictions on recursion depth, and excessively deep recursion may lead to type-checking performance issues or errors.

// This type might hit recursion depth limits
type InfiniteRecursion<T> = {
  value: T;
  next: InfiniteRecursion<T>;
};

For particularly deep recursive types, consider using tail-recursion-optimized forms:

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

Practical Applications of Recursive Types

JSON Data Types

Recursive types are ideal for describing the complete type of JSON data:

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

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

interface JSONArray extends Array<JSONValue> {}

This definition fully describes all possible JSON value types, including nested objects and arrays.

Component Props Types

In frontend frameworks, recursive types can be used to define complex component prop types:

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

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

AST (Abstract Syntax Tree) Types

When working with languages or expressions, recursive types can perfectly describe AST structures:

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 }
  }
};

Recursive Types and Type Inference

TypeScript's type inference handles recursive types well. For example, when using recursive types as function parameters, the type checker correctly infers the types of nested structures.

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));
// Output: 1, 2, 4, 5, 3

Recursive Types and Template Literal Types

Template literal types introduced in TypeScript 4.1 can also be combined with recursive types to create powerful string pattern-matching types.

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"]>;
// Type is "user/profile/settings"

Advanced Combinations of Recursive Types and Conditional Types

Combining recursion and conditional types allows for the creation of complex type utilities, such as deep optional types, deep required types, etc.

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
    }
  }
};

Combining Recursive Types with Mapped Types

Mapped types can be combined with recursive types to create more flexible type transformation utilities.

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>;
/* Equivalent to:
{
  userName: string;
  userAge: number;
  addressInfo: {
    streetName: string;
    postalCode: string;
  };
}
*/

Recursive Types and the infer Keyword

The infer keyword is particularly useful in recursive types for extracting and transforming nested types.

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

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

Recursive Types and Union Types

Recursive types can be combined with union types to handle more complex type scenarios.

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);
      // In practice, safer operator handling would be needed
      return eval(`${left} ${expr.operator} ${right}`);
    case "call":
      // In practice, function lookup logic would be needed
      return expr.fn + "(" + expr.args.map(evaluate).join(", ") + ")";
  }
}

Recursive Types and Type Guards

When working with recursive types, type guards can help narrow down type ranges.

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)) {
    // Here, `node` is inferred as the `TreeNode` type
    console.log(node.value);
    if (node.left) processNode(node.left);
    if (node.right) processNode(node.right);
  }
}

Recursive Types and Indexed Access Types

Indexed access types can be combined with recursive types to create dynamic type queries.

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"

Recursive Types and Variadic Tuple Types

Variadic tuple types introduced in TypeScript 4.0 can be combined with recursive types.

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]

Recursive Types and Template Recursion Limits

While recursive types are powerful, it's important to be aware of TypeScript's recursion depth limits. For particularly deep recursion, iterative approaches or adjusted recursion strategies may be necessary.

// This type might hit recursion depth limits
type DeepArray<T> = T | DeepArray<T>[];

// A safer alternative
type SafeDeepArray<T> = T | SafeDeepArray<T>[];

Recursive Types and Performance Considerations

Complex recursive types may impact type-checking performance. In large projects, it's important to balance type precision with compilation performance.

// Simple recursive types generally perform well
type SimpleTree = {
  value: number;
  children?: SimpleTree[];
};

// Very complex recursive conditional types may impact performance
type ComplexTransform<T> = 
  T extends object 
    ? { [K in keyof T]: ComplexTransform<T[K]> } 
    : T;