Рекурсия в типах

Форма любого рекурсивного типа

У рекурсивного условного типа ровно две ветки, как у корректной рекурсивной функции:

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

«Меньший вход» — это почти всегда кортеж с отрезанной головой. Главный рычаг — [infer Head, ...infer Tail]. В ветке extends условного типа этот паттерн матчит непустой кортеж, связывает первый элемент с Head, а всё, что после него, — с Tail. Базовый случай — пустой кортеж [], который не проходит проверку extends и проваливается в ветку else.

Reverse: канонический обход

type Reverse<T extends readonly unknown[]> =
  T extends readonly [infer Head, ...infer Tail]
    ? [...Reverse<Tail>, Head]
    : [];

type R = Reverse<[1, 2, 3]>;
//   ^? type R = [3, 2, 1]

Читайте это как трассировку. Reverse<[1,2,3]> матчится, Head = 1, Tail = [2,3], поэтому превращается в [...Reverse<[2,3]>, 1]. Это рекурсирует в [...Reverse<[3]>, 2, 1], затем [...Reverse<[]>, 3, 2, 1], и Reverse<[]> попадает в базовый случай []. Накопленные спреды схлопываются в [3, 2, 1].

Join и Includes — тот же скелет, другое накопление

type Join<T extends readonly string[], D extends string> =
  T extends readonly [infer H extends string, ...infer R extends string[]]
    ? R extends [] ? H : `${H}${D}${Join<R, D>}`
    : "";

type J = Join<["a", "b", "c"], "-">;
//   ^? type J = "a-b-c"

type Includes<T extends readonly unknown[], U> =
  T extends readonly [infer H, ...infer R]
    ? [H] extends [U] ? [U] extends [H] ? true : Includes<R, U> : Includes<R, U>
    : false;

type Inc = Includes<[1, 2, 3], 2>;
//   ^? type Inc = true

Join несёт разделитель D вдоль рекурсии и обрабатывает последний элемент особым случаем (R extends []), чтобы строка не заканчивалась лишним разделителем. Includes коротко замыкается в момент, когда находит совпадение — рекурсивный вызов происходит только в ветке «ещё не найдено». (Обратите внимание на обёртки [H] extends [U] и [U] extends [H] — это отключает дистрибуцию, чтобы сравнение было точным; с этим приёмом вы встретитесь в следующем уроке.)

Стена глубины — и почему важна хвостовая позиция

Когда вы видите «Type instantiation is excessively deep and possibly infinite.» (ошибку «слишком глубокое инстанцирование типа, возможно бесконечное»), первый вопрос — это неверный базовый случай или просто не-хвостовой вызов. Одно сообщение покрывает оба, а фикс разный. Компилятор ограничивает рекурсию, чтобы проверка типов не зависала. Исторически рекурсивный условный тип взрывался около 50 уровней самоссылки с ошибкой:

type BuildBad<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : [unknown, ...BuildBad<N, [unknown, ...Acc]>];
//                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// Error: Type instantiation is excessively deep and possibly infinite.
// (рекурсивный вызов обёрнут в [unknown, ...] — НЕ в хвостовой позиции)

TypeScript 4.5 добавил устранение хвостовой рекурсии для условных типов. Когда рекурсивный вызов — это весь результат ветки условия (вокруг него ничего нет), компилятор переиспользует кадр вычисления вместо вложения, и эффективный лимит подскакивает примерно до 1000. Фикс — протащить аккумулятор и вернуть его напрямую:

type Build<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N
    ? Acc                                     // базовый случай
    : Build<N, [unknown, ...Acc]>;            // ХВОСТОВОЙ вызов: вся ветка ЕСТЬ рекурсия

type T999 = Build<999>["length"];
//   ^? type T999 = 999   (без ошибки — устранение хвостовой рекурсии)

Структурная разница: [unknown, ...Build<...>] оборачивает вызов, поэтому каждый кадр должен ждать внутренний результат — не устраняется. Build<N, [unknown, ...Acc]> и есть результат — устраняется. Перестройте рекурсию так, чтобы самовызов стоял в хвостовой позиции, и стена сдвинется с 50 до 1000.