Recursive Types

Types that reference themselves for complex data structures.

Basic Recursive Type

type JsonValue =
  | string
  | number
  | boolean
  | null
  | JsonObject
  | JsonArray;

interface JsonObject {
  [key: string]: JsonValue;
}

interface JsonArray extends Array<JsonValue> {}

const json: JsonValue = {
  name: "Alice",
  age: 25,
  tags: ["developer", "typescript"],
  metadata: {
    created: "2024-01-01"
  }
};

Tree Structure

interface TreeNode<T> {
  value: T;
  children: TreeNode<T>[];
}

const tree: TreeNode<string> = {
  value: "root",
  children: [
    {
      value: "child1",
      children: []
    },
    {
      value: "child2",
      children: [
        {
          value: "grandchild",
          children: []
        }
      ]
    }
  ]
};

Linked List

type LinkedList<T> =
  | { kind: "empty" }
  | { kind: "node"; value: T; next: LinkedList<T> };

const list: LinkedList<number> = {
  kind: "node",
  value: 1,
  next: {
    kind: "node",
    value: 2,
    next: { kind: "empty" }
  }
};

Recursive Mapped Types

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;
    coordinates: {
      lat: number;
      lng: number;
    };
  };
}

type ReadonlyUser = DeepReadonly<User>;

Recursive Conditional Types

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

Path Types

type Paths<T> = T extends object
  ? {
      [K in keyof T]: K extends string
        ? K | `${K}.${Path<T[K]>}`
        : never;
    }[keyof T]
  : never;

type Path<T> = T extends object ? Paths<T> : never;

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

type UserPaths = Path<User>;
// "name" | "address" | "address.street" | "address.city"

Exercises

Exercise 1: JSON Type

// Create a recursive type for JSON values
// Support: string, number, boolean, null, objects, arrays

Exercise 2: Deep Readonly

// Create a recursive DeepReadonly type
// Make all properties readonly at all levels

Exercise 3: Tree Type

// Create a recursive tree type
// Each node has a value and children (array of nodes)

Exercise 4: Nested Paths

// Create a type that generates all possible paths
// For nested object properties
// Example: "a" | "a.b" | "a.b.c"

Exercise 5: Recursive Transformation

// Create a type that recursively transforms
// All string properties to optional
// In a nested object structure

Best Practices

1. Use base cases - Prevent infinite recursion
2. Test with real data - Ensure types work correctly
3. Be aware of depth limits - TypeScript has recursion limits
4. Document recursion - Explain the recursive structure
5. Use helper types - Break complex recursion into parts

Common Mistakes

1. Infinite recursion

// ❌ No base case
type Bad<T> = T extends object ? Bad<T> : T;

// ✅ With base case
type Good<T> = T extends object ? { [K in keyof T]: Good<T[K]> } : T;

2. Too deep recursion

// ❌ Might hit recursion limit
type VeryDeep<T, Depth extends number = 50> = 
  Depth extends 0 ? T : VeryDeep<DeepTransform<T>, Prev<Depth>>;

// ✅ Limit depth
type Limited<T, MaxDepth extends number = 5> = 
  MaxDepth extends 0 ? T : Limited<Transform<T>, Prev<MaxDepth>>;

3. Not handling primitives

// ❌ Assumes object
type Bad<T> = {
  [K in keyof T]: Bad<T[K]>;
};

// ✅ Handle primitives
type Good<T> = T extends object
  ? { [K in keyof T]: Good<T[K]> }
  : T;

Next Steps

Learn about Type-Level Programming.