Рекурсивные определения: базовые случаи, меньшие себя и контракт за прыжком веры

Две части: пол и правило, спускающееся к нему.

Рекурсивное определение задаёт вещь через её же меньшую версию. В нём всегда ровно два вида частей:

• Базовые случаи — входы, на которые ответ даётся сразу, без ссылки на определяемую вещь. Это пол.
• Рекурсивное правило — рецепт, собирающий ответ для большего входа из ответа для строго меньшего.

Классический пример — факториал числа, записывается n! — произведение всех целых чисел от 1 до n:

• Базовый случай: 0! = 1
• Правило: n! = n · (n-1)! для любого n ≥ 1

Посмотрите, как определение само вычисляет 4!. Каждый шаг заменяет факториал тем, что велит правило, пока базовый случай не оборвёт цепочку:

4! = 4 · 3!
   = 4 · (3 · 2!)
   = 4 · (3 · (2 · 1!))
   = 4 · (3 · (2 · (1 · 0!)))
   = 4 · (3 · (2 · (1 · 1)))    ← база: 0! = 1, дальше ссылок нет
   = 24

Ничего циклического не произошло. Правило для 4! ни разу не упомянуло 4! — оно упомянуло 3!, строго меньшую задачу. Цепочка 4 → 3 → 2 → 1 → 0 обязана была закончиться: каждый шаг вёл вниз, а на нуле был пол.

Трассировка factorial(4) через стек.

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

function factorial(n) {
  if (n === 0) return 1;        // база ПЕРВОЙ: пол отвечает сразу
  return n * factorial(n - 1);  // правило: один слой работы · меньший себя
}

factorial(4); // 24

Теперь проследим factorial(4) так, как это делает машина. Каждый вызов, который пока не может ответить, ждёт, и рантайм держит каждый ждущий вызов живым — кадром (frame) на стеке вызовов:

factorial(4) → нужно 4 * factorial(3)   …ждёт
  factorial(3) → нужно 3 * factorial(2)   …ждёт
    factorial(2) → нужно 2 * factorial(1)   …ждёт
      factorial(1) → нужно 1 * factorial(0)   …ждёт
        factorial(0) → база → возвращает 1   (не ждёт!)
      factorial(1) продолжает: 1 * 1 = 1
    factorial(2) продолжает: 2 * 1 = 2
  factorial(3) продолжает: 3 * 2 = 6
factorial(4) продолжает: 4 * 6 = 24

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

Рекурсивные структуры данных.

Паттерн нужен не только числам. Самые полезные структуры данных в программировании — рекурсивные определения:

• Список — это либо пустота, либо первый элемент (голова), за которым идёт меньший список (хвост).
• Дерево каталогов — это несколько файлов плюс несколько каталогов, каждый из которых — меньшее дерево каталогов.

Вы уже запускали рекурсивное определение в бою: каждый du -sh node_modules, каждый «посчитать размер папки» в файловом менеджере — это исполненное определение каталога. Структура кода повторяет структуру определения строка в строку:

function dirSize(dir) {
  let total = 0;
  for (const entry of entriesOf(dir)) {
    if (entry.isFile) total += entry.size;   // базовый ингредиент: у файла есть размер
    else              total += dirSize(entry); // каталог — это МЕНЬШЕЕ дерево
  }
  return total;
}

Где базовый случай? Спрятан на самом виду: у пустого каталога нет записей, тело цикла не выполняется ни разу, и функция возвращает 0, не вызвав себя. Базовые случаи не всегда носят if — иногда это ветка, в которой рекурсивный вызов просто не случается. Каждый лист файловой системы — пол.

Вот второе определение, построенное так же, без единой формулы. Лестничные числа: S(n) считает, сколькими способами можно подняться по лестнице из n ступеней, если шаг покрывает 1 или 2 ступени.

• Базовые случаи: S(1) = 1 (один одиночный шаг), S(2) = 2 (1+1 или один двойной)
• Правило: S(n) = S(n-1) + S(n-2) — первый шаг либо одиночный (остаётся лестница из n−1), либо двойной (остаётся n−2)

Правило позволяет вычислять значения, которых вы никогда не видели: S(3) = S(2) + S(1) = 3, затем S(4) = S(3) + S(2) = 5. Определение и есть алгоритм.

Два закона — и что ломается при их нарушении.

Каждое законное рекурсивное определение (и каждая рекурсивная функция) подчиняется двум законам:

1. Каждый рекурсивный шаг обязан двигаться к базовому случаю. Вход внутреннего вызова должен быть строго меньше по какой-то честной мере: меньшее число, более короткий список, поддерево.
2. Базовый случай обязан существовать на каждом пути. С какого входа ни начни, сжимающаяся цепочка должна реально приземлиться на пол.

Удалим базовый случай и запустим:

def factorial(n):
    return n * factorial(n - 1)   # пола нет

factorial(4)
# RecursionError: maximum recursion depth exceeded

Ничего мистического — просто следите за кадрами. factorial(4) ждёт factorial(3), тот ждёт factorial(2), потом 1, потом 0, потом −1, потом −2… Ни один вызов никогда не возвращается: чтобы вернуться, нужен базовый случай, а его нет. Каждый незавершённый вызов сидит и ждёт на стеке, кадр за кадром, а стек — конечная полоска памяти. Python сдаётся примерно на тысяче кадров с RecursionError; JavaScript бросает RangeError: Maximum call stack size exceeded. «Переполнение стека» — не машина, запутавшаяся в самоссылке, а машина, честно складирующая тысячи долговых расписок, которые никто никогда не оплатит.

Закон 2 коварнее, чем кажется: база должна быть достижима с любого стартового входа. factorial(4.5) шагает 4.5 → 3.5 → 2.5 → … и перепрыгивает n === 0, так и не попав в него — цепочка движется к полу и промахивается мимо. Настоящий код ставит охрану (if (!Number.isInteger(n) || n < 0) throw …); настоящие определения объявляют область («для целых n ≥ 0»).

Заблуждение: рекурсия — не циклическая магия.

Джуниору из пролога мы должны ответ. Вызов factorial(n - 1) внутри factorial ощущается как использование вещи до её существования. Это не так. Это использование определения: (n-1)! — определённое, зафиксированное значение; определение пригвождает его так же намертво, как 0! пригвождён к единице. Телу функции не нужно, чтобы factorial был «дописан»; ему нужно, чтобы уравнение было истинным, а уравнение стоит само по себе.

Вот рабочий контракт — то, что сеньоры на самом деле держат в голове:

• Обработайте один слой сами. Ваш код отвечает за соединение головы с результатом хвоста, текущего каталога — с его поддеревьями. Один слой, не больше.
• Полностью доверьтесь меньшему вызову. Считайте, что factorial(n - 1) возвращает ровно (n-1)!. Не перепроверяйте его мысленно.
• Проверьте два закона. Меньше на каждом шаге; пол на каждом пути.

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