🔄 Recursive Types: Self-Referential Type Wizardry

🎯 Introduction

Welcome to the mind-bending world of recursive types! 🎉 Think of recursive types as TypeScript’s way of creating infinite loops in the type system ♾️ - they can reference themselves to handle arbitrarily deep nesting, complex tree structures, and sophisticated self-referential patterns.

You’re about to discover one of TypeScript’s most powerful and advanced features. Whether you’re building JSON schemas 📋, creating nested navigation menus 🗺️, or designing complex data transformation pipelines 🔄, recursive types will give you the power to handle infinite depth with elegant type safety.

By the end of this tutorial, you’ll be creating recursive type definitions that can handle any level of nesting like a master architect designing fractal structures! 🏗️ Let’s dive into this recursive rabbit hole! 🐰

📚 Understanding Recursive Types

🤔 What are Recursive Types?

Recursive types are type definitions that reference themselves, directly or indirectly. Think of them as mathematical functions 🧮 that call themselves with different parameters - but instead of runtime recursion, this happens at the type level during compilation.

The basic pattern looks like this:

type RecursiveType<T> = {
  value: T;
  children?: RecursiveType<T>[];  // References itself!
}

This creates a type that can represent a tree structure with infinite depth!

🎨 Your First Recursive Type

Let’s start with simple examples:

// 🎯 Basic tree structure
type TreeNode<T> = {
  value: T;
  children: TreeNode<T>[];  // Self-reference
};

// 🧪 Testing the recursive type
type NumberTree = TreeNode<number>;
const numberTree: NumberTree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        {
          value: 4,
          children: []  // Can go infinitely deep!
        },
        {
          value: 5,
          children: []
        }
      ]
    },
    {
      value: 3,
      children: []
    }
  ]
};

// 🚀 Linked list with recursion
type LinkedListNode<T> = {
  value: T;
  next?: LinkedListNode<T>;  // Optional self-reference
};

// ✨ Testing linked list
type StringList = LinkedListNode<string>;
const stringList: StringList = {
  value: "first",
  next: {
    value: "second",
    next: {
      value: "third"
      // next is optional, so it can end here
    }
  }
};

💡 The Magic: Recursive types can represent data structures of arbitrary depth while maintaining complete type safety!

🔍 Understanding Self-Reference

// 🎨 Different recursive patterns
type DirectRecursion<T> = {
  value: T;
  self: DirectRecursion<T>;  // Direct self-reference
};

type IndirectRecursion<T> = {
  value: T;
  nested: NestedType<T>;
};

type NestedType<T> = {
  back: IndirectRecursion<T>;  // Indirect recursion
};

// ✨ Conditional recursion
type ConditionalRecursion<T, Depth extends number = 5> = 
  Depth extends 0 
    ? { value: T }  // Base case
    : {
        value: T;
        children?: ConditionalRecursion<T, Prev<Depth>>[];
      };

// Helper for decrementing depth
type Prev<T extends number> = T extends 1 ? 0 : T extends 2 ? 1 : T extends 3 ? 2 : number;

🌳 Tree Structures with Recursive Types

📝 Building Complex Tree Types

Let’s explore sophisticated tree patterns:

// 🎯 Generic tree with metadata
type MetaTree<T, M = {}> = {
  value: T;
  metadata: M;
  children: MetaTree<T, M>[];
  parent?: MetaTree<T, M>;
};

// 🚀 File system representation
type FileSystemNode = {
  name: string;
  type: 'file' | 'directory';
  size?: number;
  permissions: string;
  children?: FileSystemNode[];  // Only for directories
  parent?: FileSystemNode;
};

// ✨ Navigation menu with recursive nesting
type MenuItem = {
  id: string;
  label: string;
  url?: string;
  icon?: string;
  children?: MenuItem[];  // Infinite submenu depth
  metadata?: {
    isActive?: boolean;
    isDisabled?: boolean;
    permissions?: string[];
  };
};

// 🧪 Testing complex tree structures
const fileSystem: FileSystemNode = {
  name: "root",
  type: "directory",
  permissions: "755",
  children: [
    {
      name: "src",
      type: "directory",
      permissions: "755",
      children: [
        {
          name: "components",
          type: "directory",
          permissions: "755",
          children: [
            {
              name: "Button.tsx",
              type: "file",
              size: 1024,
              permissions: "644"
            },
            {
              name: "Modal.tsx",
              type: "file",
              size: 2048,
              permissions: "644"
            }
          ]
        },
        {
          name: "utils",
          type: "directory",
          permissions: "755",
          children: [
            {
              name: "helpers.ts",
              type: "file",
              size: 512,
              permissions: "644"
            }
          ]
        }
      ]
    },
    {
      name: "package.json",
      type: "file",
      size: 800,
      permissions: "644"
    }
  ]
};

const navigation: MenuItem = {
  id: "main",
  label: "Main Menu",
  children: [
    {
      id: "dashboard",
      label: "Dashboard",
      url: "/dashboard",
      icon: "dashboard"
    },
    {
      id: "products",
      label: "Products",
      children: [
        {
          id: "all-products",
          label: "All Products",
          url: "/products",
          children: [
            {
              id: "electronics",
              label: "Electronics",
              url: "/products/electronics",
              children: [
                {
                  id: "computers",
                  label: "Computers",
                  url: "/products/electronics/computers"
                },
                {
                  id: "phones",
                  label: "Phones",
                  url: "/products/electronics/phones"
                }
              ]
            },
            {
              id: "clothing",
              label: "Clothing",
              url: "/products/clothing"
            }
          ]
        },
        {
          id: "add-product",
          label: "Add Product",
          url: "/products/add"
        }
      ]
    }
  ]
};

🎮 Advanced Tree Utilities

// 🎨 Tree traversal types
type TreePath<T> = T extends { children: infer Children }
  ? Children extends readonly any[]
    ? Children[number] extends T
      ? [T] | [T, ...TreePath<Children[number]>]
      : [T]
    : [T]
  : [T];

// 🚀 Tree search utilities
type FindInTree<Tree, SearchValue> = Tree extends { value: SearchValue }
  ? Tree
  : Tree extends { children: infer Children }
    ? Children extends readonly any[]
      ? FindInTree<Children[number], SearchValue>
      : never
    : never;

// ✨ Tree depth calculation
type TreeDepth<T, Counter extends any[] = []> = 
  T extends { children: infer Children }
    ? Children extends readonly any[]
      ? Children extends []
        ? Counter['length']
        : TreeDepth<Children[number], [...Counter, any]>
      : Counter['length']
    : Counter['length'];

// 🧪 Tree transformation utilities
type MapTree<T, U> = T extends { value: infer V; children: infer Children }
  ? Children extends readonly any[]
    ? {
        value: U;
        children: MapTree<Children[number], U>[];
      }
    : { value: U; children: [] }
  : { value: U; children: [] };

// 🎯 Tree flattening
type FlattenTree<T> = T extends { value: infer V; children: infer Children }
  ? Children extends readonly any[]
    ? [V, ...FlattenTree<Children[number]>]
    : [V]
  : never;

🔄 JSON and Object Recursion

📝 Deep JSON Types

Let’s create types for handling deeply nested JSON:

// 🎯 Recursive JSON value type
type JSONValue = 
  | string
  | number
  | boolean
  | null
  | JSONValue[]
  | { [key: string]: JSONValue };  // Self-reference for objects

// 🚀 Strongly typed JSON schema
type JSONSchema = {
  type: 'string' | 'number' | 'boolean' | 'null' | 'array' | 'object';
  properties?: { [key: string]: JSONSchema };  // Recursive properties
  items?: JSONSchema;  // For arrays
  required?: string[];
  enum?: JSONValue[];
  default?: JSONValue;
};

// ✨ Nested object transformation
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];
};

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

// 🧪 Testing deep transformations
interface NestedConfig {
  database: {
    host: string;
    port: number;
    credentials: {
      username: string;
      password: string;
      options: {
        ssl: boolean;
        timeout: number;
      };
    };
  };
  api: {
    baseUrl: string;
    endpoints: {
      users: string;
      posts: string;
    };
  };
}

type PartialConfig = DeepPartial<NestedConfig>;
// Result: All properties at every level become optional

type ReadonlyConfig = DeepReadonly<NestedConfig>;
// Result: All properties at every level become readonly

// 🎮 Path-based property access
type PathsToProps<T, Prefix extends string = ''> = {
  [K in keyof T]: T[K] extends object
    ? PathsToProps<T[K], `${Prefix}${string & K}.`>
    : `${Prefix}${string & K}`;
}[keyof T];

type ConfigPaths = PathsToProps<NestedConfig>;
// Result: "database.host" | "database.port" | "database.credentials.username" | etc.

🎨 Dynamic Object Manipulation

// 🎯 Deep property access type
type GetDeepProperty<T, Path extends string> = 
  Path extends `${infer Key}.${infer Rest}`
    ? Key extends keyof T
      ? GetDeepProperty<T[Key], Rest>
      : never
    : Path extends keyof T
      ? T[Path]
      : never;

// 🚀 Deep property setting type
type SetDeepProperty<T, Path extends string, Value> = 
  Path extends `${infer Key}.${infer Rest}`
    ? Key extends keyof T
      ? {
          [P in keyof T]: P extends Key
            ? SetDeepProperty<T[P], Rest, Value>
            : T[P];
        }
      : T
    : Path extends keyof T
      ? {
          [P in keyof T]: P extends Path ? Value : T[P];
        }
      : T;

// ✨ Usage examples
type DatabaseHost = GetDeepProperty<NestedConfig, "database.host">; // string
type CredentialsSSL = GetDeepProperty<NestedConfig, "database.credentials.options.ssl">; // boolean

type UpdatedConfig = SetDeepProperty<NestedConfig, "database.port", string>;
// Changes database.port from number to string while preserving all other types

// 🧪 Deep merge utility
type DeepMerge<T, U> = {
  [K in keyof T | keyof U]: K extends keyof U
    ? K extends keyof T
      ? T[K] extends object
        ? U[K] extends object
          ? DeepMerge<T[K], U[K]>
          : U[K]
        : U[K]
      : U[K]
    : K extends keyof T
      ? T[K]
      : never;
};

// 🎮 Testing deep merge
interface BaseConfig {
  database: {
    host: string;
    port: number;
  };
  logging: {
    level: string;
  };
}

interface OverrideConfig {
  database: {
    port: string;  // Override port type
    ssl: boolean;  // Add new property
  };
  cache: {
    enabled: boolean;  // Add new section
  };
}

type MergedConfig = DeepMerge<BaseConfig, OverrideConfig>;
// Result: Intelligently merges nested objects

💡 Practical Examples

🛒 Example 1: Type-Safe Form Validation System

Let’s build a recursive form validation system:

// 🎯 Recursive form field definition
type FormField<T> = {
  value: T;
  validation: ValidationRule<T>[];
  errors: string[];
  touched: boolean;
  children?: { [key: string]: FormField<any> };  // Recursive nesting
};

type ValidationRule<T> = {
  type: 'required' | 'minLength' | 'maxLength' | 'pattern' | 'custom';
  message: string;
  params?: any;
  validator?: (value: T) => boolean;
};

// 🚀 Recursive form schema
type FormSchema<T> = {
  [K in keyof T]: T[K] extends object
    ? FormSchema<T[K]>  // Recursive for nested objects
    : {
        type: 'string' | 'number' | 'boolean' | 'email' | 'password';
        required?: boolean;
        validation?: ValidationRule<T[K]>[];
        default?: T[K];
      };
};

// ✨ Form data type
interface UserRegistrationData {
  personal: {
    firstName: string;
    lastName: string;
    dateOfBirth: string;
  };
  contact: {
    email: string;
    phone: string;
    address: {
      street: string;
      city: string;
      country: string;
      coordinates: {
        lat: number;
        lng: number;
      };
    };
  };
  preferences: {
    newsletter: boolean;
    theme: 'light' | 'dark';
    notifications: {
      email: boolean;
      push: boolean;
      sms: boolean;
    };
  };
}

// 🧪 Form schema definition
const userFormSchema: FormSchema<UserRegistrationData> = {
  personal: {
    firstName: {
      type: 'string',
      required: true,
      validation: [
        { type: 'required', message: 'First name is required' },
        { type: 'minLength', message: 'Min 2 characters', params: 2 }
      ]
    },
    lastName: {
      type: 'string',
      required: true,
      validation: [
        { type: 'required', message: 'Last name is required' }
      ]
    },
    dateOfBirth: {
      type: 'string',
      required: true
    }
  },
  contact: {
    email: {
      type: 'email',
      required: true,
      validation: [
        { type: 'required', message: 'Email is required' },
        { type: 'pattern', message: 'Invalid email format', params: /^[^\s@]+@[^\s@]+\.[^\s@]+$/ }
      ]
    },
    phone: {
      type: 'string',
      required: true
    },
    address: {
      street: {
        type: 'string',
        required: true
      },
      city: {
        type: 'string',
        required: true
      },
      country: {
        type: 'string',
        required: true
      },
      coordinates: {
        lat: {
          type: 'number',
          required: false
        },
        lng: {
          type: 'number',
          required: false
        }
      }
    }
  },
  preferences: {
    newsletter: {
      type: 'boolean',
      default: false
    },
    theme: {
      type: 'string',
      default: 'light'
    },
    notifications: {
      email: {
        type: 'boolean',
        default: true
      },
      push: {
        type: 'boolean',
        default: true
      },
      sms: {
        type: 'boolean',
        default: false
      }
    }
  }
};

// 🎮 Recursive form validator
class RecursiveFormValidator<T extends Record<string, any>> {
  private schema: FormSchema<T>;

  constructor(schema: FormSchema<T>) {
    this.schema = schema;
  }

  // 🎯 Validate entire form recursively
  validateForm(data: T, path: string = ''): ValidationResult<T> {
    const result: ValidationResult<T> = {
      isValid: true,
      errors: {},
      data
    };

    this.validateObject(data, this.schema, result, path);
    return result;
  }

  // 🚀 Recursive object validation
  private validateObject(
    data: any,
    schema: any,
    result: ValidationResult<T>,
    path: string
  ): void {
    for (const key in schema) {
      const fieldPath = path ? `${path}.${key}` : key;
      const fieldSchema = schema[key];
      const fieldValue = data?.[key];

      if (this.isFieldSchema(fieldSchema)) {
        // Validate leaf field
        const fieldErrors = this.validateField(fieldValue, fieldSchema);
        if (fieldErrors.length > 0) {
          result.isValid = false;
          this.setNestedError(result.errors, fieldPath, fieldErrors);
        }
      } else {
        // Recursively validate nested object
        this.validateObject(fieldValue, fieldSchema, result, fieldPath);
      }
    }
  }

  // ✨ Field validation
  private validateField(value: any, schema: any): string[] {
    const errors: string[] = [];

    if (schema.required && (value === undefined || value === null || value === '')) {
      errors.push('This field is required');
    }

    if (schema.validation && value !== undefined && value !== null && value !== '') {
      for (const rule of schema.validation) {
        if (!this.applyValidationRule(value, rule)) {
          errors.push(rule.message);
        }
      }
    }

    return errors;
  }

  // 🧪 Apply validation rule
  private applyValidationRule(value: any, rule: ValidationRule<any>): boolean {
    switch (rule.type) {
      case 'required':
        return value !== undefined && value !== null && value !== '';
      case 'minLength':
        return typeof value === 'string' && value.length >= rule.params;
      case 'maxLength':
        return typeof value === 'string' && value.length <= rule.params;
      case 'pattern':
        return typeof value === 'string' && rule.params.test(value);
      case 'custom':
        return rule.validator ? rule.validator(value) : true;
      default:
        return true;
    }
  }

  // 🎨 Helper methods
  private isFieldSchema(schema: any): boolean {
    return schema.type !== undefined;
  }

  private setNestedError(errors: any, path: string, fieldErrors: string[]): void {
    const keys = path.split('.');
    let current = errors;

    for (let i = 0; i < keys.length - 1; i++) {
      if (!current[keys[i]]) {
        current[keys[i]] = {};
      }
      current = current[keys[i]];
    }

    current[keys[keys.length - 1]] = fieldErrors;
  }
}

// 🎯 Validation result type
type ValidationResult<T> = {
  isValid: boolean;
  errors: NestedErrors<T>;
  data: T;
};

type NestedErrors<T> = {
  [K in keyof T]?: T[K] extends object ? NestedErrors<T[K]> : string[];
};

// 🧪 Usage example
const validator = new RecursiveFormValidator(userFormSchema);

const testData: UserRegistrationData = {
  personal: {
    firstName: '',  // Invalid - required
    lastName: 'Doe',
    dateOfBirth: '1990-01-01'
  },
  contact: {
    email: 'invalid-email',  // Invalid - bad format
    phone: '+1-555-0123',
    address: {
      street: '123 Main St',
      city: 'New York',
      country: 'USA',
      coordinates: {
        lat: 40.7128,
        lng: -74.0060
      }
    }
  },
  preferences: {
    newsletter: true,
    theme: 'dark',
    notifications: {
      email: true,
      push: false,
      sms: false
    }
  }
};

const validationResult = validator.validateForm(testData);
console.log('🔍 Validation result:', validationResult);
// Will show nested errors for firstName and email fields

🎮 Example 2: AST (Abstract Syntax Tree) Parser

Let’s create a recursive AST type system:

// 🎯 AST Node base type
type ASTNode = {
  type: string;
  position: {
    line: number;
    column: number;
  };
  children?: ASTNode[];
};

// 🚀 Expression types
type Literal = ASTNode & {
  type: 'Literal';
  value: string | number | boolean;
};

type Identifier = ASTNode & {
  type: 'Identifier';
  name: string;
};

type BinaryExpression = ASTNode & {
  type: 'BinaryExpression';
  operator: '+' | '-' | '*' | '/' | '===' | '!==' | '<' | '>' | '&&' | '||';
  left: Expression;
  right: Expression;
};

type UnaryExpression = ASTNode & {
  type: 'UnaryExpression';
  operator: '!' | '-' | '+' | 'typeof';
  operand: Expression;
};

type CallExpression = ASTNode & {
  type: 'CallExpression';
  callee: Expression;
  arguments: Expression[];
};

type MemberExpression = ASTNode & {
  type: 'MemberExpression';
  object: Expression;
  property: Expression;
  computed: boolean;
};

// ✨ Statement types
type ExpressionStatement = ASTNode & {
  type: 'ExpressionStatement';
  expression: Expression;
};

type VariableDeclaration = ASTNode & {
  type: 'VariableDeclaration';
  declarations: VariableDeclarator[];
  kind: 'var' | 'let' | 'const';
};

type VariableDeclarator = ASTNode & {
  type: 'VariableDeclarator';
  id: Identifier;
  init?: Expression;
};

type FunctionDeclaration = ASTNode & {
  type: 'FunctionDeclaration';
  id: Identifier;
  params: Identifier[];
  body: BlockStatement;
};

type BlockStatement = ASTNode & {
  type: 'BlockStatement';
  body: Statement[];
};

type IfStatement = ASTNode & {
  type: 'IfStatement';
  test: Expression;
  consequent: Statement;
  alternate?: Statement;
};

type ReturnStatement = ASTNode & {
  type: 'ReturnStatement';
  argument?: Expression;
};

// 🧪 Union types for recursive references
type Expression = 
  | Literal
  | Identifier
  | BinaryExpression
  | UnaryExpression
  | CallExpression
  | MemberExpression;

type Statement = 
  | ExpressionStatement
  | VariableDeclaration
  | FunctionDeclaration
  | BlockStatement
  | IfStatement
  | ReturnStatement;

type Program = ASTNode & {
  type: 'Program';
  body: Statement[];
};

// 🎮 AST utilities with recursive types
type VisitorPattern<T = void> = {
  [K in ASTNode['type']]?: (node: Extract<ASTNode, { type: K }>) => T;
};

// 🎯 AST Walker class
class ASTWalker {
  // 🚀 Walk the entire AST recursively
  walk<T>(node: ASTNode, visitor: VisitorPattern<T>): T[] {
    const results: T[] = [];
    this.walkNode(node, visitor, results);
    return results;
  }

  // ✨ Recursive node walking
  private walkNode<T>(node: ASTNode, visitor: VisitorPattern<T>, results: T[]): void {
    // Visit current node
    const visitorFn = visitor[node.type as keyof VisitorPattern<T>];
    if (visitorFn) {
      const result = visitorFn(node as any);
      if (result !== undefined) {
        results.push(result);
      }
    }

    // Recursively walk children
    if (node.children) {
      for (const child of node.children) {
        this.walkNode(child, visitor, results);
      }
    }

    // Walk specific node properties
    this.walkNodeProperties(node, visitor, results);
  }

  // 🧪 Walk specific properties based on node type
  private walkNodeProperties<T>(node: ASTNode, visitor: VisitorPattern<T>, results: T[]): void {
    switch (node.type) {
      case 'BinaryExpression':
        const binaryNode = node as BinaryExpression;
        this.walkNode(binaryNode.left, visitor, results);
        this.walkNode(binaryNode.right, visitor, results);
        break;
      case 'UnaryExpression':
        const unaryNode = node as UnaryExpression;
        this.walkNode(unaryNode.operand, visitor, results);
        break;
      case 'CallExpression':
        const callNode = node as CallExpression;
        this.walkNode(callNode.callee, visitor, results);
        for (const arg of callNode.arguments) {
          this.walkNode(arg, visitor, results);
        }
        break;
      case 'MemberExpression':
        const memberNode = node as MemberExpression;
        this.walkNode(memberNode.object, visitor, results);
        this.walkNode(memberNode.property, visitor, results);
        break;
      case 'VariableDeclaration':
        const varNode = node as VariableDeclaration;
        for (const declarator of varNode.declarations) {
          this.walkNode(declarator, visitor, results);
        }
        break;
      case 'VariableDeclarator':
        const declaratorNode = node as VariableDeclarator;
        this.walkNode(declaratorNode.id, visitor, results);
        if (declaratorNode.init) {
          this.walkNode(declaratorNode.init, visitor, results);
        }
        break;
      case 'FunctionDeclaration':
        const funcNode = node as FunctionDeclaration;
        this.walkNode(funcNode.id, visitor, results);
        for (const param of funcNode.params) {
          this.walkNode(param, visitor, results);
        }
        this.walkNode(funcNode.body, visitor, results);
        break;
      case 'BlockStatement':
        const blockNode = node as BlockStatement;
        for (const stmt of blockNode.body) {
          this.walkNode(stmt, visitor, results);
        }
        break;
      case 'IfStatement':
        const ifNode = node as IfStatement;
        this.walkNode(ifNode.test, visitor, results);
        this.walkNode(ifNode.consequent, visitor, results);
        if (ifNode.alternate) {
          this.walkNode(ifNode.alternate, visitor, results);
        }
        break;
      case 'ReturnStatement':
        const returnNode = node as ReturnStatement;
        if (returnNode.argument) {
          this.walkNode(returnNode.argument, visitor, results);
        }
        break;
      case 'ExpressionStatement':
        const exprNode = node as ExpressionStatement;
        this.walkNode(exprNode.expression, visitor, results);
        break;
      case 'Program':
        const programNode = node as Program;
        for (const stmt of programNode.body) {
          this.walkNode(stmt, visitor, results);
        }
        break;
    }
  }

  // 🎨 Find all nodes of specific type
  findNodesByType<T extends ASTNode['type']>(
    root: ASTNode,
    nodeType: T
  ): Extract<ASTNode, { type: T }>[] {
    const results = this.walk(root, {
      [nodeType]: (node) => node
    } as VisitorPattern<Extract<ASTNode, { type: T }>>);
    
    return results;
  }

  // 🔧 Transform AST recursively
  transform(node: ASTNode, transformer: VisitorPattern<ASTNode>): ASTNode {
    // Transform current node
    const transformerFn = transformer[node.type as keyof VisitorPattern<ASTNode>];
    let transformedNode = transformerFn ? transformerFn(node as any) || node : node;

    // Recursively transform based on node type
    transformedNode = this.transformNodeProperties(transformedNode, transformer);

    return transformedNode;
  }

  private transformNodeProperties(node: ASTNode, transformer: VisitorPattern<ASTNode>): ASTNode {
    // Implementation similar to walkNodeProperties but returns transformed nodes
    switch (node.type) {
      case 'BinaryExpression':
        const binaryNode = node as BinaryExpression;
        return {
          ...binaryNode,
          left: this.transform(binaryNode.left, transformer),
          right: this.transform(binaryNode.right, transformer)
        };
      case 'UnaryExpression':
        const unaryNode = node as UnaryExpression;
        return {
          ...unaryNode,
          operand: this.transform(unaryNode.operand, transformer)
        };
      // ... other cases follow similar pattern
      default:
        return node;
    }
  }
}

// 🧪 Usage example
const sampleAST: Program = {
  type: 'Program',
  position: { line: 1, column: 1 },
  body: [
    {
      type: 'VariableDeclaration',
      position: { line: 1, column: 1 },
      kind: 'const',
      declarations: [
        {
          type: 'VariableDeclarator',
          position: { line: 1, column: 7 },
          id: {
            type: 'Identifier',
            position: { line: 1, column: 7 },
            name: 'sum'
          },
          init: {
            type: 'BinaryExpression',
            position: { line: 1, column: 13 },
            operator: '+',
            left: {
              type: 'Literal',
              position: { line: 1, column: 13 },
              value: 1
            },
            right: {
              type: 'Literal',
              position: { line: 1, column: 17 },
              value: 2
            }
          }
        }
      ]
    }
  ]
};

const walker = new ASTWalker();

// Find all identifiers
const identifiers = walker.findNodesByType(sampleAST, 'Identifier');
console.log('🔍 Identifiers found:', identifiers.map(id => id.name));

// Find all literals
const literals = walker.findNodesByType(sampleAST, 'Literal');
console.log('📊 Literals found:', literals.map(lit => lit.value));

console.log('🎉 Recursive AST processing complete!');

🚀 Advanced Recursive Patterns

🧙‍♂️ Conditional Recursion

// 🎨 Depth-limited recursion
type RecursiveDepth<T, Depth extends number> = 
  Depth extends 0 
    ? never 
    : {
        value: T;
        children?: RecursiveDepth<T, Subtract1<Depth>>[];
      };

type Subtract1<N extends number> = 
  N extends 1 ? 0 :
  N extends 2 ? 1 :
  N extends 3 ? 2 :
  N extends 4 ? 3 :
  N extends 5 ? 4 :
  number;

// 🎯 Tree with maximum depth of 3
type LimitedTree<T> = RecursiveDepth<T, 3>;

// 🚀 Conditional recursion based on type
type SmartRecursion<T> = T extends string
  ? { text: T; nested?: SmartRecursion<T>[] }
  : T extends number
    ? { count: T; children?: SmartRecursion<T>[] }
    : T extends boolean
      ? { flag: T; branches?: SmartRecursion<T>[] }
      : { data: T; items?: SmartRecursion<T>[] };

🏗️ Mutual Recursion

// ✨ Types that reference each other
type NodeA<T> = {
  type: 'A';
  value: T;
  linkToB?: NodeB<T>;
  children?: NodeA<T>[];
};

type NodeB<T> = {
  type: 'B';
  data: T;
  linkToA?: NodeA<T>;
  siblings?: NodeB<T>[];
};

// 🧪 Graph-like structures
type GraphNode<T> = {
  id: string;
  value: T;
  edges: Edge<T>[];
};

type Edge<T> = {
  to: GraphNode<T>;
  weight?: number;
  metadata?: any;
};

⚠️ Common Pitfalls and Solutions

😱 Pitfall 1: Infinite Recursion

// ❌ Potential infinite loop in type checking
type BadRecursion<T> = {
  value: T;
  self: BadRecursion<T>;  // Always requires self, causes infinite expansion
};

// ✅ Safe recursion with optional self-reference
type GoodRecursion<T> = {
  value: T;
  self?: GoodRecursion<T>;  // Optional prevents infinite expansion
};

// ✅ Use conditional recursion for termination
type SafeRecursion<T, Depth extends number = 5> = 
  Depth extends 0 
    ? { value: T }  // Base case terminates recursion
    : {
        value: T;
        children?: SafeRecursion<T, Subtract1<Depth>>[];
      };

🤯 Pitfall 2: Type Instantiation Too Deep

// ❌ TypeScript has recursion limits
type TooDeep<T, N extends any[] = []> = 
  N['length'] extends 50
    ? T
    : TooDeep<T, [...N, any]>;  // Will hit recursion limit

// ✅ Use reasonable depth limits
type ReasonableDepth<T, N extends any[] = []> = 
  N['length'] extends 10
    ? T
    : ReasonableDepth<T, [...N, any]>;

// ✅ Design with TypeScript's limits in mind
const MAX_RECURSION_DEPTH = 45;  // Stay under TypeScript's limit

🔍 Pitfall 3: Performance Issues

// ❌ Complex recursive types can slow down compilation
type ComplexRecursion<T> = T extends any[]
  ? {
      items: { [K in keyof T]: ComplexRecursion<T[K]> };
      meta: ComplexRecursion<T[0]>;
    }
  : T extends object
    ? { [K in keyof T]: ComplexRecursion<T[K]> }
    : T;

// ✅ Simplify recursive logic
type SimpleRecursion<T> = T extends object
  ? { [K in keyof T]: SimpleRecursion<T[K]> }
  : T;

🛠️ Best Practices

🎯 Use Optional References: Make recursive properties optional to prevent infinite expansion
📝 Limit Recursion Depth: Use conditional types to limit depth and prevent compiler errors
🛡️ Provide Base Cases: Always have a way for recursion to terminate
🎨 Keep It Simple: Complex recursive logic can hurt compilation performance
✨ Test Thoroughly: Recursive types can behave unexpectedly with complex data
🔍 Monitor Compilation Time: Watch for performance impact of complex recursive types

🧪 Hands-On Exercise

🎯 Challenge: Build a Type-Safe State Machine

Create a recursive state machine type system:

📋 Requirements:

✅ Define states that can transition to other states
🔧 Type-safe event handling with recursive transitions
🎨 Support for nested state machines (statecharts)
📊 Guard conditions and actions
✨ State history and time travel debugging!

🚀 Bonus Points:

Add parallel state machines
Create visual state diagram generation
Build state machine optimization utilities

💡 Solution

🔍 Click to see solution

// 🎯 State machine core types
type StateNode<TContext, TEvent> = {
  id: string;
  type: 'simple' | 'compound' | 'parallel' | 'final';
  entry?: Action<TContext, TEvent>[];
  exit?: Action<TContext, TEvent>[];
  on?: TransitionMap<TContext, TEvent>;
  initial?: string;  // For compound states
  states?: { [key: string]: StateNode<TContext, TEvent> };  // Recursive!
  invoke?: InvokeConfig<TContext, TEvent>[];
  always?: Transition<TContext, TEvent>[];
};

type Action<TContext, TEvent> = {
  type: string;
  exec?: (context: TContext, event: TEvent) => TContext;
};

type Guard<TContext, TEvent> = {
  type: string;
  predicate: (context: TContext, event: TEvent) => boolean;
};

type Transition<TContext, TEvent> = {
  target?: string;
  actions?: Action<TContext, TEvent>[];
  guard?: Guard<TContext, TEvent>;
  internal?: boolean;
};

type TransitionMap<TContext, TEvent> = {
  [K in TEvent extends { type: infer T } ? T : never]?: Transition<TContext, TEvent>;
};

type InvokeConfig<TContext, TEvent> = {
  id: string;
  src: string | ((context: TContext, event: TEvent) => Promise<any>);
  onDone?: Transition<TContext, TEvent>;
  onError?: Transition<TContext, TEvent>;
};

// 🚀 State machine definition
type StateMachineDefinition<TContext, TEvent> = {
  id: string;
  initial: string;
  context: TContext;
  states: { [key: string]: StateNode<TContext, TEvent> };
};

// ✨ Machine state type
type MachineState<TContext, TEvent> = {
  value: string | { [key: string]: MachineState<TContext, TEvent> };  // Recursive for nested states
  context: TContext;
  history?: MachineState<TContext, TEvent>;
  meta?: {
    timestamp: number;
    event?: TEvent;
    actions: Action<TContext, TEvent>[];
  };
};

// 🧪 State machine interpreter
class StateMachineInterpreter<TContext, TEvent extends { type: string }> {
  private definition: StateMachineDefinition<TContext, TEvent>;
  private currentState: MachineState<TContext, TEvent>;
  private listeners: ((state: MachineState<TContext, TEvent>) => void)[] = [];

  constructor(definition: StateMachineDefinition<TContext, TEvent>) {
    this.definition = definition;
    this.currentState = {
      value: this.definition.initial,
      context: this.definition.context
    };
  }

  // 🎯 Send event to state machine
  send(event: TEvent): MachineState<TContext, TEvent> {
    const newState = this.transition(this.currentState, event);
    
    // Store history
    newState.history = this.currentState;
    newState.meta = {
      timestamp: Date.now(),
      event,
      actions: []
    };

    this.currentState = newState;
    this.notifyListeners();
    return newState;
  }

  // 🚀 Recursive state transition
  private transition(
    state: MachineState<TContext, TEvent>,
    event: TEvent
  ): MachineState<TContext, TEvent> {
    const currentStateNode = this.getStateNode(state.value);
    if (!currentStateNode) return state;

    // Check for transitions
    const transitions = currentStateNode.on;
    if (!transitions) return state;

    const transition = transitions[event.type as keyof typeof transitions];
    if (!transition) return state;

    // Check guard condition
    if (transition.guard && !transition.guard.predicate(state.context, event)) {
      return state;
    }

    // Execute exit actions
    const exitActions = currentStateNode.exit || [];
    let newContext = state.context;
    for (const action of exitActions) {
      if (action.exec) {
        newContext = action.exec(newContext, event);
      }
    }

    // Execute transition actions
    const transitionActions = transition.actions || [];
    for (const action of transitionActions) {
      if (action.exec) {
        newContext = action.exec(newContext, event);
      }
    }

    // Determine new state value
    const newValue = transition.target || state.value;
    const targetStateNode = this.getStateNode(newValue);

    // Execute entry actions
    const entryActions = targetStateNode?.entry || [];
    for (const action of entryActions) {
      if (action.exec) {
        newContext = action.exec(newContext, event);
      }
    }

    return {
      value: newValue,
      context: newContext
    };
  }

  // ✨ Get state node by path (supports nested states)
  private getStateNode(
    statePath: string | { [key: string]: any }
  ): StateNode<TContext, TEvent> | null {
    if (typeof statePath === 'string') {
      return this.definition.states[statePath] || null;
    }

    // Handle nested state paths recursively
    const keys = Object.keys(statePath);
    if (keys.length === 0) return null;

    const topLevelState = this.definition.states[keys[0]];
    if (!topLevelState || !topLevelState.states) return topLevelState;

    // Recursively find nested state
    return this.findNestedState(topLevelState, statePath[keys[0]]);
  }

  // 🧪 Recursively find nested state
  private findNestedState(
    parentState: StateNode<TContext, TEvent>,
    nestedPath: any
  ): StateNode<TContext, TEvent> | null {
    if (typeof nestedPath === 'string') {
      return parentState.states?.[nestedPath] || null;
    }

    const keys = Object.keys(nestedPath);
    if (keys.length === 0) return parentState;

    const childState = parentState.states?.[keys[0]];
    if (!childState) return null;

    return this.findNestedState(childState, nestedPath[keys[0]]);
  }

  // 🎮 Subscribe to state changes
  subscribe(listener: (state: MachineState<TContext, TEvent>) => void): () => void {
    this.listeners.push(listener);
    return () => {
      const index = this.listeners.indexOf(listener);
      if (index > -1) {
        this.listeners.splice(index, 1);
      }
    };
  }

  private notifyListeners(): void {
    for (const listener of this.listeners) {
      listener(this.currentState);
    }
  }

  // 🔧 Get current state
  getState(): MachineState<TContext, TEvent> {
    return this.currentState;
  }

  // 🎯 Get state history
  getHistory(): MachineState<TContext, TEvent>[] {
    const history: MachineState<TContext, TEvent>[] = [];
    let current: MachineState<TContext, TEvent> | undefined = this.currentState;

    while (current) {
      history.unshift(current);
      current = current.history;
    }

    return history;
  }
}

// 🎮 Example: Traffic Light State Machine
type TrafficLightContext = {
  timer: number;
  emergencyMode: boolean;
};

type TrafficLightEvent = 
  | { type: 'TIMER' }
  | { type: 'EMERGENCY' }
  | { type: 'NORMAL' };

const trafficLightMachine: StateMachineDefinition<TrafficLightContext, TrafficLightEvent> = {
  id: 'trafficLight',
  initial: 'green',
  context: {
    timer: 0,
    emergencyMode: false
  },
  states: {
    green: {
      id: 'green',
      type: 'simple',
      entry: [
        {
          type: 'setTimer',
          exec: (context) => ({ ...context, timer: 30 })
        }
      ],
      on: {
        TIMER: {
          target: 'yellow',
          guard: {
            type: 'timerExpired',
            predicate: (context) => context.timer <= 0
          }
        },
        EMERGENCY: {
          target: 'emergency'
        }
      }
    },
    yellow: {
      id: 'yellow',
      type: 'simple',
      entry: [
        {
          type: 'setTimer',
          exec: (context) => ({ ...context, timer: 5 })
        }
      ],
      on: {
        TIMER: {
          target: 'red'
        },
        EMERGENCY: {
          target: 'emergency'
        }
      }
    },
    red: {
      id: 'red',
      type: 'simple',
      entry: [
        {
          type: 'setTimer',
          exec: (context) => ({ ...context, timer: 25 })
        }
      ],
      on: {
        TIMER: {
          target: 'green'
        },
        EMERGENCY: {
          target: 'emergency'
        }
      }
    },
    emergency: {
      id: 'emergency',
      type: 'compound',
      initial: 'flashing',
      entry: [
        {
          type: 'enableEmergency',
          exec: (context) => ({ ...context, emergencyMode: true })
        }
      ],
      on: {
        NORMAL: {
          target: 'green'
        }
      },
      states: {  // Nested states (recursive!)
        flashing: {
          id: 'flashing',
          type: 'simple',
          entry: [
            {
              type: 'startFlashing',
              exec: (context) => context
            }
          ]
        }
      }
    }
  }
};

// 🧪 Usage example
const interpreter = new StateMachineInterpreter(trafficLightMachine);

// Subscribe to state changes
const unsubscribe = interpreter.subscribe((state) => {
  console.log('🚦 Traffic light state:', state.value);
  console.log('⏱️ Context:', state.context);
});

// Send events
console.log('🟢 Initial state:', interpreter.getState().value);

interpreter.send({ type: 'TIMER' });
console.log('🟡 After TIMER:', interpreter.getState().value);

interpreter.send({ type: 'TIMER' });
console.log('🔴 After TIMER:', interpreter.getState().value);

interpreter.send({ type: 'EMERGENCY' });
console.log('🚨 Emergency mode:', interpreter.getState().value);

interpreter.send({ type: 'NORMAL' });
console.log('🟢 Back to normal:', interpreter.getState().value);

// View history
const history = interpreter.getHistory();
console.log('📜 State history:', history.map(s => s.value));

console.log('🎉 Recursive state machine implementation complete!');

🎓 Key Takeaways

You’ve mastered recursive types! Here’s what you can now do:

✅ Create self-referential type definitions that handle infinite nesting with precision 💪
✅ Build sophisticated tree and graph structures with complete type safety 🛡️
✅ Design recursive form validation and AST systems that scale beautifully 🎯
✅ Handle deeply nested JSON and object transformations like a pro 🐛
✅ Create advanced state machines and complex data structures with elegant recursion 🚀

Remember: Recursive types are like having infinite mirrors 🪞 that can reflect type structures at any depth while maintaining perfect type safety!

🤝 Next Steps

Congratulations! 🎉 You’ve conquered recursive types!

Here’s what to explore next:

💻 Practice with the state machine exercise above - try different state configurations
🏗️ Build your own recursive AST or form validation system
📚 Move on to our next tutorial: Utility Types Deep Dive: Partial, Required, Readonly
🌟 Share your recursive type patterns with the TypeScript community!

You now possess one of TypeScript’s most advanced features. Use recursive types to create elegant solutions for complex nested data structures. Remember - every recursive type master started with curiosity about self-reference. Keep experimenting, keep building, and most importantly, have fun creating infinitely deep type systems! 🚀✨

Happy recursive typing! 🎉🔄✨

Prerequisites

What you'll learn