← Курс/Рекурсивные типы#157 из 257+35 XP

Рекурсивные типы

Что такое рекурсивные типы

Рекурсивный тип — это тип, который ссылается сам на себя в своём определении. Они нужны для описания **вложенных структур** неограниченной глубины: деревья, вложенные объекты, JSON.

// Простейший рекурсивный тип — связанный список:
interface LinkedList<T> {
  value: T
  next: LinkedList<T> | null  // ссылается сам на себя!
}

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

JSON тип — классический рекурсивный тип

JSON может содержать строки, числа, булевы значения, null, массивы и объекты. Причём массивы и объекты могут содержать любое из перечисленного, включая другие массивы и объекты.

type JsonValue =
  | string
  | number
  | boolean
  | null
  | JsonValue[]           // массив из JsonValue
  | { [key: string]: JsonValue }  // объект со значениями JsonValue

// Теперь TypeScript будет проверять правильность JSON:
const data: JsonValue = {
  name: 'Алексей',
  age: 30,
  active: true,
  address: {              // вложенный объект
    city: 'Москва',
    zip: null,
  },
  scores: [10, 20, 30],  // массив
}

DeepReadonly — рекурсивно readonly

readonly от TypeScript делает только поверхностный readonly. Для вложенных объектов нужен рекурсивный тип:

// Встроенный Readonly только поверхностный:
type Readonly<T> = { readonly [P in keyof T]: T[P] }

// DeepReadonly — рекурсивный:
type DeepReadonly<T> = {
  readonly [P in keyof T]: T[P] extends object
    ? DeepReadonly<T[P]>  // рекурсия для объектов
    : T[P]                // примитивы — как есть
}

interface Config {
  server: { host: string; port: number }
  database: { url: string }
}

type FrozenConfig = DeepReadonly<Config>
// FrozenConfig.server.host — readonly, FrozenConfig.server — readonly

DeepPartial — рекурсивно опциональный

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

interface UserProfile {
  name: string
  settings: {
    theme: string
    notifications: {
      email: boolean
      sms: boolean
    }
  }
}

// Обновление вложенных полей:
function deepUpdate(
  profile: UserProfile,
  changes: DeepPartial<UserProfile>
): UserProfile {
  // ...глубокое слияние
}

deepUpdate(profile, {
  settings: {
    notifications: {
      email: false  // только это поле, остальные — без изменений
    }
  }
})

Дерево — классическая рекурсивная структура

interface TreeNode<T> {
  value: T
  children: TreeNode<T>[]  // рекурсия
}

type FileTree = TreeNode<{ name: string; isDirectory: boolean }>

const fileSystem: FileTree = {
  value: { name: 'root', isDirectory: true },
  children: [
    {
      value: { name: 'src', isDirectory: true },
      children: [
        { value: { name: 'index.ts', isDirectory: false }, children: [] },
        { value: { name: 'utils.ts', isDirectory: false }, children: [] },
      ]
    },
    { value: { name: 'package.json', isDirectory: false }, children: [] },
  ]
}

Ограничения рекурсивных типов

TypeScript имеет ограничение на глубину рекурсии (~100 уровней). При слишком глубокой рекурсии компилятор выдаст ошибку или замедлится. Для практических целей этого обычно достаточно.

// Взаимная рекурсия тоже работает:
type EvenList = { value: number; rest: OddList | null }
type OddList = { value: number; rest: EvenList | null }

Примеры

Рекурсивные структуры данных и алгоритмы: дерево, deep freeze, deep clone

// В TS: рекурсивные типы — для описания вложенных структур
// В JS: показываем рекурсивные ФУНКЦИИ для работы с такими структурами

// === JSON тип: валидация вложенного JSON ===
function isJsonValue(value) {
  // В TS: value is JsonValue — type predicate
  if (value === null) return true
  if (typeof value === 'string') return true
  if (typeof value === 'number') return true
  if (typeof value === 'boolean') return true
  if (Array.isArray(value)) return value.every(isJsonValue)
  if (typeof value === 'object') {
    return Object.values(value).every(isJsonValue)
  }
  return false
}

console.log('=== JSON валидация ===')
const validJson = {
  name: 'Алексей',
  age: 30,
  active: true,
  address: { city: 'Москва', zip: null },
  scores: [10, 20, 30],
}
console.log('Валидный JSON:', isJsonValue(validJson))   // true
console.log('Функция:', isJsonValue(() => {}))           // false
console.log('Symbol:', isJsonValue(Symbol()))            // false

// === DeepFreeze: рекурсивная заморозка (как DeepReadonly в TS) ===
function deepFreeze(obj) {
  Object.getOwnPropertyNames(obj).forEach(name => {
    const value = obj[name]
    if (typeof value === 'object' && value !== null && !Object.isFrozen(value)) {
      deepFreeze(value)
    }
  })
  return Object.freeze(obj)
}

console.log('\n=== DeepFreeze (как DeepReadonly) ===')
const config = deepFreeze({
  server: { host: 'localhost', port: 3000 },
  database: { url: 'postgres://...' }
})

config.server.port = 9999  // Игнорируется — глубокая заморозка
console.log(config.server.port)  // 3000

// === Дерево: рекурсивная структура (как TreeNode<T>) ===
console.log('\n=== Дерево ===')

function createNode(value, ...children) {
  return { value, children }
}

const fileTree = createNode('root',
  createNode('src',
    createNode('index.ts'),
    createNode('utils.ts'),
    createNode('components',
      createNode('Button.ts'),
      createNode('Input.ts'),
    )
  ),
  createNode('package.json'),
  createNode('tsconfig.json'),
)

// Рекурсивный обход дерева
function printTree(node, indent) {
  indent = indent || 0
  console.log(' '.repeat(indent * 2) + node.value)
  node.children.forEach(child => printTree(child, indent + 1))
}

printTree(fileTree)

// === DeepPartial: глубокое слияние (как DeepPartial в TS) ===
console.log('\n=== Deep Merge (как DeepPartial) ===')

function deepMerge(target, source) {
  const result = { ...target }
  for (const key in source) {
    const sourceVal = source[key]
    const targetVal = result[key]
    if (
      typeof sourceVal === 'object' && sourceVal !== null && !Array.isArray(sourceVal) &&
      typeof targetVal === 'object' && targetVal !== null && !Array.isArray(targetVal)
    ) {
      result[key] = deepMerge(targetVal, sourceVal)  // рекурсия для вложенных объектов
    } else if (sourceVal !== undefined) {
      result[key] = sourceVal
    }
  }
  return result
}

const profile = {
  name: 'Алексей',
  settings: {
    theme: 'dark',
    notifications: { email: true, sms: true }
  }
}

const updates = {
  settings: {
    notifications: { email: false }  // только это поле
  }
}

const merged = deepMerge(profile, updates)
console.log(merged.name)                           // 'Алексей' — не тронуто
console.log(merged.settings.theme)                 // 'dark' — не тронуто
console.log(merged.settings.notifications.email)   // false — обновлено
console.log(merged.settings.notifications.sms)     // true — не тронуто