Базовый CS с нуля

Предварительный взгляд на рекурсию

Суть Рекурсивная функция вызывает саму себя. Каждый вызов — просто ещё один кадр на стеке. Базовый случай останавливает спуск. Без базового случая стек переполняется.

◷ 22 min

Ты трассировал стеки вызовов, где main вызывает outer, который вызывает inner. Каждый вызов кладёт новый кадр. Но в правилах нет ничего, что запрещало бы функции вызывать саму себя. Что тогда происходит со стеком?

Ответ: ровно то же самое. Функция, вызывающая себя, — это просто ещё одна инструкция CALL, указывающая на тот же адрес функции. Новый кадр кладётся с собственной копией параметров и локальных переменных. Функция не «перезапускается» — создаётся второй, независимый экземпляр кадра. Это рекурсия.

Критическое ограничение: что-то должно в конечном итоге остановить спуск, иначе стек растёт до переполнения. Это условие остановки — базовый случай.

Цель

После этого урока ты сможешь объяснить, что такое рекурсивная функция (функция, которая вызывает саму себя), описать каждый рекурсивный вызов как новый независимый кадр на стеке, определить базовый случай и рекурсивный случай в функции, и объяснить, что вызывает переполнение стека в рекурсивной программе.

Идея

Рекурсия имеет ровно две части:

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

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

Функция для трассировки: countdown(n) концептуально выводит n, n-1, …, 1, 0, и затем ещё один вызов, который попадает в базовый случай. Базовый случай: n < 0 (остановка ниже нуля — срабатывает, когда n становится равным -1). Рекурсивный случай вызывает countdown(n - 1). Трассируется с countdown(3).

Код


      1
      function countdown(n: number): void {
    

      2
      if (n < 0) return;          // базовый случай: остановиться ниже нуля
    

      3
      // (в реальной программе здесь мы бы вывели n)
    

      4
      countdown(n - 1);           // рекурсивный вызов: n уменьшается на 1
    

      5
      }

L1 n — параметр: каждый вызов получает свой n в своём кадре
L2 базовый случай: когда n < 0, вернуться без следующего вызова — останавливает спуск
L4 рекурсивный случай: CALL countdown с n-1; кладёт новый кадр для следующего уровня

countdown(n): базовый случай n < 0 останавливает рекурсию. Каждый вызов кладёт один новый кадр. countdown(3) создаёт 5 кадров всего (n=3,2,1,0,-1 при базовом случае).

Пошаговый разбор

Трассировка countdown(3). Каждая ячейка — один кадр. Кадры накапливаются по мере уменьшения n, затем разматываются по мере возврата каждого вызова.


      1
      function countdown(n: number): void {
    

      2
        if (n < 0) return;
    

      3
        countdown(n - 1);
    

      4
      }

Граничные случаи

Что если базового случая нет? Удали строку if (n < 0) return;. Теперь countdown(-1) вызывает countdown(-2), который вызывает countdown(-3), и так далее бесконечно. Каждый вызов кладёт новый кадр. Область стека (обычно 1–8 МБ) заполняется. Когда указатель стека должен выйти за пределы зарезервированной области, ОС завершает программу с ошибкой «переполнение стека» (stack overflow). Это не медленная ошибка — она крашит программу за миллисекунды, потому что каждый вызов занимает наносекунды и миллионы могут произойти до того, как стек исчерпается. Базовый случай в рекурсивных функциях не опционален.

Практика 0 / 5

Вызывается countdown(3). Включая вызов базового случая (n=-1), сколько всего кадров кладётся на стек?

При каком значении n срабатывает базовый случай в countdown?

countdown(3) вызывает countdown(2), который вызывает countdown(1), ..., до базового случая. Максимальное количество кадров на стеке одновременно равно 5 (для n=3,2,1,0,-1). Если бы был вызван countdown(10), каков максимум кадров на стеке одновременно?

У рекурсивной функции нет базового случая. Что происходит при её вызове? Введи 1 за 'переполнение стека', 0 за 'возвращается нормально'.

function factorial(n: number): number { if (n === 0) return 1; return n * factorial(n - 1); } — Каково значение n в базовом случае?

Проверь себя

Викторина

Что делает рекурсию безопасной (т. е. что предотвращает переполнение стека)?

Итог

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

Продолжить восхождение ↑Функции и стек вызовов: обзор с выбором ответа