6.5 Recursive Types

What Are Recursive Types?

A recursive type is a type whose definition references itself. They are essential for modeling hierarchical structures — trees, nested JSON, file systems, and so on.

// The simplest recursive type
type NestedArray<T> = T | NestedArray<T>[];
// number | number[] | number[][] | ...

TypeScript 3.7 introduced direct support for recursive type aliases. Earlier versions required an interface-based workaround.

Recursive types let you:

• Accurately represent deeply nested structures like JSON, where the nesting depth is unknown.
• Model hierarchical data such as file systems, DOM trees, and navigation menus.
• Implement utility types like DeepPartial and DeepReadonly that apply to every nesting level.

---

Core Concepts

1. Basic Recursive Type Structure

// Basic pattern: base case + recursive case
type RecursiveType =
  | BaseCase          // base case — a concrete type that stops recursion
  | { nested: RecursiveType }; // recursive case

// Linked list type
type LinkedList<T> =
  | null                                    // empty list (base case)
  | { value: T; next: LinkedList<T> };      // node

// Binary tree type
type BinaryTree<T> =
  | null                                    // empty node (base case)
  | {
      value: T;
      left: BinaryTree<T>;
      right: BinaryTree<T>;
    };

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

const tree: BinaryTree<number> = {
  value: 10,
  left: { value: 5, left: null, right: null },
  right: { value: 15, left: null, right: null },
};

2. JSONValue Type — Representing Nested JSON

// A type that covers all values representable in JSON
type JSONPrimitive = string | number | boolean | null;

type JSONValue =
  | JSONPrimitive
  | JSONValue[]                        // array (recursive)
  | { [key: string]: JSONValue };      // object (recursive)

// More explicit form
type JSONObject = { [key: string]: JSONValue };
type JSONArray = JSONValue[];

// Usage
const data: JSONValue = {
  name: 'Alice',
  age: 30,
  active: true,
  address: {
    city: 'New York',
    zip: '10001',
    coordinates: [40.7128, -74.0060],
  },
  tags: ['developer', 'TypeScript'],
  metadata: null,
};

// Type-safe JSON serialization / deserialization wrappers
function safeJsonParse(input: string): JSONValue {
  return JSON.parse(input) as JSONValue;
}

function safeJsonStringify(value: JSONValue): string {
  return JSON.stringify(value);
}

3. DeepPartial, DeepReadonly, DeepRequired

// DeepPartial: make all properties optional at every depth
type DeepPartial<T> = T extends object
  ? { [K in keyof T]?: DeepPartial<T[K]> }
  : T;

// DeepReadonly: make all properties read-only at every depth
type DeepReadonly<T> = T extends (infer U)[]
  ? ReadonlyArray<DeepReadonly<U>>
  : T extends object
  ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
  : T;

// DeepRequired: remove all optional markers at every depth
type DeepRequired<T> = T extends object
  ? { [K in keyof T]-?: DeepRequired<T[K]> }
  : T;

// DeepMutable: remove all readonly modifiers at every depth
type DeepMutable<T> = T extends (infer U)[]
  ? DeepMutable<U>[]
  : T extends object
  ? { -readonly [K in keyof T]: DeepMutable<T[K]> }
  : T;

// Usage
interface AppConfig {
  database: {
    host: string;
    port: number;
    options: {
      poolSize: number;
      timeout: number;
    };
  };
  cache: {
    ttl: number;
    maxItems: number;
  };
}

// Patch update: all fields optional
type ConfigPatch = DeepPartial<AppConfig>;

const patch: ConfigPatch = {
  database: {
    options: {
      poolSize: 10, // other fields can be omitted
    },
  },
};

// Immutable config: all fields readonly
type ImmutableConfig = DeepReadonly<AppConfig>;

4. Combining Recursive Types with Conditional Types

// Recursively unwrap nested types
type Unwrap<T> = T extends Promise<infer U>
  ? Unwrap<U>
  : T extends Array<infer U>
  ? Unwrap<U>
  : T;

type A = Unwrap<Promise<Promise<number>>>;        // number
type B = Unwrap<number[][]>;                      // number
type C = Unwrap<Promise<string[]>>;               // string

// How the built-in Awaited<T> works (TypeScript internals)
// type Awaited<T> = T extends null | undefined
//   ? T
//   : T extends object & { then(onfulfilled: infer F, ...args: infer _): any }
//   ? F extends ((value: infer V, ...args: infer _) => any)
//     ? Awaited<V>
//     : never
//   : T;

// Flatten nested arrays
type Flatten<T> = T extends Array<infer U>
  ? Flatten<U>
  : T;

type FlatNumber = Flatten<number[][][]>; // number
type FlatString = Flatten<string[]>;     // string

5. Nested Path Types

// Extract all nested paths of an object as "a.b.c" strings
type PathsOf<T, Prefix extends string = ''> = {
  [K in keyof T & string]: T[K] extends object
    ? Prefix extends ''
      ? PathsOf<T[K], K> | K
      : PathsOf<T[K], `${Prefix}.${K}`> | `${Prefix}.${K}`
    : Prefix extends ''
    ? K
    : `${Prefix}.${K}`;
}[keyof T & string];

interface Config {
  server: {
    host: string;
    port: number;
    ssl: {
      enabled: boolean;
      cert: string;
    };
  };
  database: {
    url: string;
    name: string;
  };
}

type ConfigPaths = PathsOf<Config>;
// 'server' | 'server.host' | 'server.port'
// | 'server.ssl' | 'server.ssl.enabled' | 'server.ssl.cert'
// | 'database' | 'database.url' | 'database.name'

// Extract the value type at a given path
type ValueAtPath<T, P extends string> =
  P extends `${infer Key}.${infer Rest}`
    ? Key extends keyof T
      ? ValueAtPath<T[Key], Rest>
      : never
    : P extends keyof T
    ? T[P]
    : never;

type ServerHost = ValueAtPath<Config, 'server.host'>;        // string
type SSLEnabled = ValueAtPath<Config, 'server.ssl.enabled'>; // boolean

---

Code Examples

Example 1: File System Tree Type

// File node
interface FileNode {
  type: 'file';
  name: string;
  size: number;
  extension: string;
  modifiedAt: Date;
}

// Directory node — self-referencing
interface DirectoryNode {
  type: 'directory';
  name: string;
  children: FileSystemNode[]; // recursive reference
  modifiedAt: Date;
}

type FileSystemNode = FileNode | DirectoryNode;

// File system traversal functions
function getAllFiles(node: FileSystemNode): FileNode[] {
  if (node.type === 'file') {
    return [node];
  }
  return node.children.flatMap(getAllFiles);
}

function getTotalSize(node: FileSystemNode): number {
  if (node.type === 'file') {
    return node.size;
  }
  return node.children.reduce((sum, child) => sum + getTotalSize(child), 0);
}

function findByExtension(
  node: FileSystemNode,
  ext: string
): FileNode[] {
  if (node.type === 'file') {
    return node.extension === ext ? [node] : [];
  }
  return node.children.flatMap(child => findByExtension(child, ext));
}

function printTree(node: FileSystemNode, indent = 0): void {
  const prefix = '  '.repeat(indent);
  if (node.type === 'file') {
    console.log(`${prefix}📄 ${node.name} (${node.size}B)`);
  } else {
    console.log(`${prefix}📁 ${node.name}/`);
    node.children.forEach(child => printTree(child, indent + 1));
  }
}

// Sample file system
const rootFS: FileSystemNode = {
  type: 'directory',
  name: 'project',
  modifiedAt: new Date(),
  children: [
    {
      type: 'directory',
      name: 'src',
      modifiedAt: new Date(),
      children: [
        { type: 'file', name: 'index.ts', size: 1024, extension: 'ts', modifiedAt: new Date() },
        { type: 'file', name: 'utils.ts', size: 512, extension: 'ts', modifiedAt: new Date() },
      ],
    },
    { type: 'file', name: 'package.json', size: 256, extension: 'json', modifiedAt: new Date() },
  ],
};

const tsFiles = findByExtension(rootFS, 'ts');
console.log(`TypeScript files: ${tsFiles.length}`);

Example 2: Nested Menu Structure

interface MenuItem {
  id: string;
  label: string;
  path?: string;           // path for leaf nodes
  icon?: string;
  badge?: number;
  disabled?: boolean;
  children?: MenuItem[];   // recursive — sub-menu items
}

// Menu utility functions
function findMenuItemById(
  items: MenuItem[],
  id: string
): MenuItem | undefined {
  for (const item of items) {
    if (item.id === id) return item;
    if (item.children) {
      const found = findMenuItemById(item.children, id);
      if (found) return found;
    }
  }
  return undefined;
}

function flattenMenu(items: MenuItem[]): MenuItem[] {
  return items.flatMap(item => [
    item,
    ...(item.children ? flattenMenu(item.children) : []),
  ]);
}

function getMenuDepth(items: MenuItem[], depth = 0): number {
  return Math.max(
    depth,
    ...items.map(item =>
      item.children ? getMenuDepth(item.children, depth + 1) : depth
    )
  );
}

function buildBreadcrumb(
  items: MenuItem[],
  targetId: string,
  path: MenuItem[] = []
): MenuItem[] | null {
  for (const item of items) {
    const currentPath = [...path, item];
    if (item.id === targetId) return currentPath;
    if (item.children) {
      const found = buildBreadcrumb(item.children, targetId, currentPath);
      if (found) return found;
    }
  }
  return null;
}

// Sample menu
const appMenu: MenuItem[] = [
  {
    id: 'home',
    label: 'Home',
    path: '/',
    icon: 'home',
  },
  {
    id: 'users',
    label: 'User Management',
    icon: 'people',
    children: [
      { id: 'users-list', label: 'User List', path: '/users' },
      { id: 'users-add', label: 'Add User', path: '/users/new' },
      {
        id: 'users-roles',
        label: 'Role Management',
        children: [
          { id: 'roles-list', label: 'Role List', path: '/users/roles' },
          { id: 'roles-add', label: 'Add Role', path: '/users/roles/new' },
        ],
      },
    ],
  },
];

const breadcrumb = buildBreadcrumb(appMenu, 'roles-add');
// [Home, User Management, Role Management, Add Role]

Example 3: DOM Tree Type Modeling

// Minimal DOM tree types
interface TextNode {
  nodeType: 'text';
  content: string;
}

interface ElementNode {
  nodeType: 'element';
  tagName: string;
  attributes: Record<string, string>;
  children: DOMNode[];  // recursive
}

interface CommentNode {
  nodeType: 'comment';
  content: string;
}

type DOMNode = TextNode | ElementNode | CommentNode;

// Serialize a DOM tree to HTML
function serialize(node: DOMNode, indent = 0): string {
  const pad = '  '.repeat(indent);

  switch (node.nodeType) {
    case 'text':
      return `${pad}${node.content}`;

    case 'comment':
      return `${pad}<!-- ${node.content} -->`;

    case 'element': {
      const attrs = Object.entries(node.attributes)
        .map(([k, v]) => ` ${k}="${v}"`)
        .join('');

      if (node.children.length === 0) {
        return `${pad}<${node.tagName}${attrs} />`;
      }

      const children = node.children
        .map(child => serialize(child, indent + 1))
        .join('\n');

      return `${pad}<${node.tagName}${attrs}>\n${children}\n${pad}</${node.tagName}>`;
    }
  }
}

// Usage
const dom: DOMNode = {
  nodeType: 'element',
  tagName: 'div',
  attributes: { class: 'container' },
  children: [
    {
      nodeType: 'element',
      tagName: 'h1',
      attributes: {},
      children: [{ nodeType: 'text', content: 'Hello!' }],
    },
    { nodeType: 'comment', content: 'Body starts here' },
    {
      nodeType: 'element',
      tagName: 'p',
      attributes: { class: 'body' },
      children: [{ nodeType: 'text', content: 'TypeScript recursive type example.' }],
    },
  ],
};

console.log(serialize(dom));

---

Practical Examples

Example 1: State Management — Nested State Updates

// Recursive utility for updating a value at a nested path
type SetValueByPath<T, P extends string, V> =
  P extends `${infer Key}.${infer Rest}`
    ? Key extends keyof T
      ? { [K in keyof T]: K extends Key ? SetValueByPath<T[K], Rest, V> : T[K] }
      : T
    : P extends keyof T
    ? { [K in keyof T]: K extends P ? V : T[K] }
    : T;

// Runtime implementation
function setNestedValue<T extends object>(
  obj: T,
  path: string,
  value: unknown
): T {
  const keys = path.split('.');
  if (keys.length === 1) {
    return { ...obj, [keys[0]]: value };
  }
  const [first, ...rest] = keys;
  return {
    ...obj,
    [first]: setNestedValue(
      (obj as any)[first] ?? {},
      rest.join('.'),
      value
    ),
  };
}

// Get a value at a nested path
function getNestedValue<T>(obj: T, path: string): unknown {
  return path.split('.').reduce(
    (current: unknown, key) =>
      current != null && typeof current === 'object'
        ? (current as any)[key]
        : undefined,
    obj
  );
}

// Usage
interface State {
  user: {
    profile: {
      name: string;
      avatar: string;
    };
    preferences: {
      theme: 'light' | 'dark';
      language: string;
    };
  };
}

const state: State = {
  user: {
    profile: { name: 'Alice', avatar: '/images/default.png' },
    preferences: { theme: 'light', language: 'en' },
  },
};

const newState = setNestedValue(state, 'user.preferences.theme', 'dark');
const theme = getNestedValue(newState, 'user.preferences.theme'); // 'dark'

Example 2: Schema Validation System

// Recursive schema type — Zod/Yup style
type StringSchema = { type: 'string'; minLength?: number; maxLength?: number; pattern?: RegExp };
type NumberSchema = { type: 'number'; min?: number; max?: number; integer?: boolean };
type BooleanSchema = { type: 'boolean' };
type ArraySchema = { type: 'array'; items: Schema; minItems?: number; maxItems?: number };
type ObjectSchema = { type: 'object'; properties: { [key: string]: Schema }; required?: string[] };
type UnionSchema = { type: 'union'; schemas: Schema[] };

// Recursive union
type Schema =
  | StringSchema
  | NumberSchema
  | BooleanSchema
  | ArraySchema
  | ObjectSchema
  | UnionSchema;

// Infer a TypeScript type from a schema
type InferSchema<S extends Schema> =
  S extends StringSchema ? string :
  S extends NumberSchema ? number :
  S extends BooleanSchema ? boolean :
  S extends ArraySchema ? InferSchema<S['items']>[] :
  S extends ObjectSchema ? {
    [K in keyof S['properties']]: InferSchema<S['properties'][K]>
  } :
  S extends UnionSchema ? InferSchema<S['schemas'][number]> :
  never;

// Schema definition
const userSchema = {
  type: 'object' as const,
  properties: {
    id: { type: 'number' as const },
    name: { type: 'string' as const, minLength: 1, maxLength: 50 },
    email: { type: 'string' as const, pattern: /^[^\s@]+@[^\s@]+\.[^\s@]+$/ },
    roles: {
      type: 'array' as const,
      items: { type: 'string' as const },
    },
  },
  required: ['id', 'name', 'email'],
};

type InferredUser = InferSchema<typeof userSchema>;
// {
//   id: number;
//   name: string;
//   email: string;
//   roles: string[];
// }

---

Pro Tips

Tip 1: Limiting Recursion Depth

// TypeScript recursion limit: roughly 100 levels by default
// "Type instantiation is excessively deep" appears if you go deeper

// Pattern for limiting depth using a counter tuple
type BuildTuple<L extends number, T extends unknown[] = []> =
  T['length'] extends L ? T : BuildTuple<L, [...T, unknown]>;

type Prev<T extends number> = [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10][T];

// DeepPartial with a maximum depth limit
type DeepPartialLimited<T, Depth extends number = 5> =
  [Depth] extends [0]
    ? T
    : T extends object
    ? { [K in keyof T]?: DeepPartialLimited<T[K], Prev<Depth>> }
    : T;

// Recurses at most 5 levels deep (default)
type LimitedPartial = DeepPartialLimited<{
  a: { b: { c: { d: { e: { f: string } } } } }
}>;

Tip 2: Tail Recursion Optimization Style

TypeScript 4.5+ supports tail recursion elimination for conditional types.

// Tail recursion optimization: accumulate results in an extra parameter
// Standard recursion (may hit depth limit)
type Reverse1<T extends unknown[]> =
  T extends [infer Head, ...infer Tail]
    ? [...Reverse1<Tail>, Head]
    : [];

// Tail recursion optimized (handles deeper recursion)
type Reverse2<T extends unknown[], Acc extends unknown[] = []> =
  T extends [infer Head, ...infer Tail]
    ? Reverse2<Tail, [Head, ...Acc]>  // accumulate result in Acc
    : Acc;

type R1 = Reverse1<[1, 2, 3, 4, 5]>; // [5, 4, 3, 2, 1]
type R2 = Reverse2<[1, 2, 3, 4, 5]>; // [5, 4, 3, 2, 1]

// Practical example: remove specific types from a tuple
type RemoveType<
  T extends unknown[],
  U,
  Acc extends unknown[] = []
> = T extends [infer Head, ...infer Tail]
  ? Head extends U
    ? RemoveType<Tail, U, Acc>             // skip if matches
    : RemoveType<Tail, U, [...Acc, Head]>  // otherwise accumulate
  : Acc;

type WithoutStrings = RemoveType<[1, 'a', 2, 'b', 3], string>;
// [1, 2, 3]

Tip 3: Recursive Types vs Interfaces

// Interfaces use implicit lazy evaluation and are more stable for recursion
// For complex recursion, interfaces can be more reliable

// Option 1: type alias (works in most cases from TypeScript 3.7+)
type TreeNode<T> = {
  value: T;
  children: TreeNode<T>[];
};

// Option 2: interface (stable even on older versions)
interface ITreeNode<T> {
  value: T;
  children: ITreeNode<T>[];
}

// Option 3: workaround using an intermediate interface
interface RecursiveObject {
  [key: string]: JSONValueWithInterface;
}
interface RecursiveArray extends Array<JSONValueWithInterface> {}
type JSONValueWithInterface =
  | string | number | boolean | null
  | RecursiveObject
  | RecursiveArray;

Tip 4: Recursive Type Performance Optimization

// Situations where recursive types slow down and how to fix them

// Problem: same type checked recursively multiple times
type SlowDeepMerge<T, U> = {
  [K in keyof T | keyof U]:
    K extends keyof T & keyof U
      ? T[K] extends object
        ? U[K] extends object
          ? SlowDeepMerge<T[K], U[K]> // checked twice
          : U[K]
        : U[K]
      : K extends keyof T
      ? T[K]
      : K extends keyof U
      ? U[K]
      : never;
};

// Solution: cache the conditional result (use infer)
type FastDeepMerge<T, U> = {
  [K in keyof T | keyof U]: K extends keyof T & keyof U
    ? [T[K], U[K]] extends [object, object]
      ? FastDeepMerge<T[K], U[K]>
      : U[K]
    : K extends keyof T
    ? T[K]
    : K extends keyof U
    ? U[K]
    : never;
} extends infer R ? { [K in keyof R]: R[K] } : never; // expand to cache

---

Summary Table

Concept	Description	Example
Basic recursive type	A type that references itself	LinkedList<T>, TreeNode<T>
JSONValue	Recursive type covering all JSON values	string | number | JSONValue[]
DeepPartial	Optional at every depth	{ [K in keyof T]?: DeepPartial<T[K]> }
DeepReadonly	Readonly at every depth	Recursion + readonly modifier
Nested path type	Extract "a.b.c" style paths	PathsOf<T>, ValueAtPath<T, P>
Awaited	Recursively unwrap nested Promises	Built-in since TypeScript 4.5
Depth limiting	Control maximum depth with a counter tuple	Prev<N> pattern
Tail recursion optimization	Deeper recursion via accumulator parameter	TypeScript 4.5+
Interface recursion	Stable recursion with lazy evaluation	interface I { children: I[] }
Flatten	Flatten nested arrays or Promises	T extends Array<infer U> ? Flatten<U> : T

---

Next is Ch7: Advanced Utility Types. You will study the internal implementation and combination patterns of built-in TypeScript utility types including Exclude, Extract, NonNullable, ReturnType, Parameters, ConstructorParameters, and InstanceType.