TypeScript Academy · Урок

Глубина и ограничения рекурсии

Разберитесь в ограничениях глубины рекурсии TypeScript

«Глубина и ограничения рекурсии» — бесплатный урок TypeScript Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения TypeScript Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс TypeScript Academy содержит 4 уроков всего.

У TypeScript есть ограничения рекурсии

Рекурсивные типы очень мощны, но проверяющий типов ограничивает глубину, до которой он будет их разворачивать. При достижении ограничения возникает ошибка глубины.

// Excessively deep recursive types can produce:
// "Type instantiation is excessively deep and possibly infinite."

Откуда берутся ошибки глубины

Условные типы, которые рекурсивно вызывают себя без ясного базового случая, постепенно уменьшающегося на каждом шаге, могут выйти из-под контроля, особенно в сочетании с большими объединениями или построением кортежей.

type Repeat<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : Repeat<N, [...Acc, unknown]>;
// Large N can exceed the instantiation depth.
type Five = Repeat<5>;

Безопасная ограниченная рекурсия

Делайте рекурсию неглубокой и ограниченной. Построить небольшой кортеж вполне допустимо: базовый случай Acc["length"] extends N своевременно останавливает рекурсию.

type Tuple<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : Tuple<N, [...Acc, unknown]>;
type Three = Tuple<3>; // [unknown, unknown, unknown]
const t: Three = [1, 2, 3];
console.log(t.length);

Шаблоны хвостовой рекурсии для типов

TypeScript оптимизирует некоторые условные типы с хвостовой рекурсией, передавая аккумулятор, что позволяет выполнять более глубокую рекурсию, чем при наивной вложенности.

type Reverse<T extends unknown[], Acc extends unknown[] = []> =
  T extends [infer Head, ...infer Tail]
    ? Reverse<Tail, [Head, ...Acc]>
    : Acc;
type R = Reverse<[1, 2, 3]>; // [3, 2, 1]
const r: R = [3, 2, 1];
console.log(r);

Зачем нужны аккумуляторы

Передача результатов вперёд в аккумуляторе сохраняет рекурсию в хвостовой позиции, поэтому TypeScript может разворачивать её эффективнее, чем глубоко вложенные условные типы.

type Join<T extends string[], Acc extends string = ""> =
  T extends [infer H extends string, ...infer R extends string[]]
    ? Join<R, Acc extends "" ? H : Acc>
    : Acc;
type First = Join<["a", "b", "c"]>; // "a"
const f: First = "a";
console.log(f);

Как избежать рекурсии не в хвостовой позиции

Обёртывание рекурсивного вызова в другую операцию над типом нарушает хвостовую позицию и может привести к более быстрому достижению ограничений. Вместо этого храните состояние в аккумуляторе.

// Non-tail (can be costly): builds nesting around the recursive call
// type Bad<T> = T extends [infer H, ...infer R] ? [H, ...Bad<R>] : [];
// Tail-friendly alternative uses an accumulator parameter.
console.log("prefer accumulators");

Явное ограничение глубины

Добавьте счётчик глубины, чтобы тип прекращал работу после фиксированного числа уровней, жертвуя полнотой ради гарантированного завершения.

type Flatten<T, Depth extends unknown[] = []> =
  Depth["length"] extends 5
    ? T
    : T extends (infer U)[]
      ? Flatten<U, [...Depth, unknown]>
      : T;
type X = Flatten<number[][]>; // number
const x: X = 7;
console.log(x);

Практическая глубина обычно не вызывает проблем

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

type Json = string | number | boolean | null | Json[] | { [k: string]: Json };
const v: Json = { a: { b: { c: 1 } } }; // fine, shallow
console.log(v);

Как распознать сообщение об ошибке

Увидев сообщение «слишком глубокий и, возможно, бесконечный», ищите отсутствующий базовый случай, аккумулятор не в хвостовой позиции или слишком большой ввод.

// Fixes: add/tighten the base case, switch to tail recursion,
// reduce input size, or cap with a depth counter.
console.log("check base case and tail position");

Рекурсия во время выполнения — это другое

Эти ограничения относятся к рекурсии на уровне типов. Обычные рекурсивные функции над рекурсивными типами выполняются во время работы программы и ограничены только стеком вызовов.

type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function count<T>(n: TreeNode<T>): number {
  return 1 + n.children.reduce((a, c) => a + count(c), 0);
}
console.log(count({ value: 1, children: [{ value: 2, children: [] }] }));

Проектирование с учётом ограничений

Предпочитайте неглубокие данные, шаблоны хвостовой рекурсии с аккумуляторами и явные ограничения глубины. При таких привычках вы редко столкнётесь с ограничением в реальном коде.

type Length<T extends unknown[]> = T["length"];
type N = Length<[1, 2, 3]>; // 3
const n: N = 3;
console.log(n);

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

Проверьте своё понимание глубины и ограничений рекурсии.

Итоги: глубина и ограничения рекурсии

Вы узнали, что TypeScript ограничивает глубину рекурсии на уровне типов, что шаблоны хвостовой рекурсии с аккумуляторами и явные ограничения глубины помогают избежать проблем, а обычные рекурсивные данные редко достигают этого ограничения.

type Reverse<T extends unknown[], Acc extends unknown[] = []> =
  T extends [infer H, ...infer R] ? Reverse<R, [H, ...Acc]> : Acc;
const r: Reverse<[1, 2]> = [2, 1];
console.log(r);

Часто задаваемые вопросы

Урок «Глубина и ограничения рекурсии» бесплатный?

Да — полный текст урока «Глубина и ограничения рекурсии» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс TypeScript Academy, подпишись на CoddyKit PRO. Курс TypeScript Academy содержит 4 уроков всего.

Чему я научусь в уроке «Глубина и ограничения рекурсии»?

Разберитесь в ограничениях глубины рекурсии TypeScript Ты практикуешь TypeScript Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать TypeScript Academy?

Предыдущий опыт не требуется. TypeScript Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Глубина и ограничения рекурсии»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке TypeScript Academy?

Да. Каждый урок TypeScript Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к TypeScript Academy