Суть Прочитайте четыре маленьких сниппета на TypeScript, проследите стек кадр за кадром, посчитайте глубину рекурсии и предскажите, что реально делают передача параметров и возврат.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небе
◷ 14 min
Чтение стека вызовов по коду — навык, к которому ведёт весь юнит. Для каждого сниппета прогоните его в голове: кладите кадр на каждый вызов, снимайте один на каждый возврат и следите, куда текут значения.
Цель
Потренируйтесь трассировать реальный код так, как его выполняет машина, — считая активные кадры, предсказывая глубину рекурсии и рассуждая о том, что пересекает границу кадра, когда аргументы входят, а значение выходит.
Сниппет 1 — вложенные вызовы и глубина стека
function inner(): void { let c = 3; // единственная локальная переменная inner}function outer(): void { let b = 2; // единственная локальная переменная outer inner(); // кладёт кадр inner}function main(): void { let a = 1; // единственная локальная переменная main outer(); // кладёт кадр outer}main();
Викторина
Completed
В момент, когда inner выполняет let c = 3, сколько кадров на стеке и какой из них хранит a = 1?
Heads-up outer и main ещё не вернулись — они приостановлены ниже inner, ожидая его завершения. Их кадры остаются на стеке, поэтому сосуществуют три кадра.
Heads-up a — локальная переменная main, поэтому она живёт в кадре main внизу, а не в inner. Локальные переменные каждой функции живут только в её собственном кадре.
Heads-up Число кадров — это число активных вызовов, а не вызываемых функций. main, outer и inner все активны, пока выполняется inner, поэтому кадров три.
Сниппет 2 — передача параметров (по значению)
function bump(x: number): void { x = x + 100; // переприсваивает собственную копию x в bump}function main(): void { let v = 1; bump(v); // аргумент 1 копируется в x функции bump // чему равно v здесь?}
Викторина
Completed
После возврата bump(v) чему равно v в main и почему?
Heads-up bump прибавил 100 к своей копии x, а не к v. При передаче по значению аргумент копируется в кадр вызываемой функции, поэтому переменная вызывающей стороны никогда не меняется от переприсвоения параметра.
Heads-up Передача значения как аргумента не расходует и не удаляет переменную вызывающей стороны. v в main сохраняет своё исходное значение 1 всё время.
Heads-up x инициализируется копией аргумента (1), а не 0, поэтому x становится 101 внутри bump — но это живёт в кадре bump и никогда не утекает обратно. v в main остаётся 1.
Сниппет 3 — глубина рекурсии
function sumTo(n: number): number { if (n === 0) return 0; // базовый случай return n + sumTo(n - 1); // рекурсивный случай}sumTo(4);
Викторина
Completed
Для sumTo(4) каково максимальное число кадров, активных одновременно, и какое значение возвращается?
Heads-up Каждый рекурсивный вызов кладёт новый независимый кадр со своим n; кадр n = 4 приостановлен на 4 + sumTo(3), пока вся цепочка не вернётся. В самой глубокой точке сосуществуют пять кадров.
Heads-up Вызов базового случая sumTo(0) тоже кладёт кадр перед возвратом 0, поэтому пик — пять кадров, а не четыре, даже если он ничего не добавляет к сумме.
Heads-up Базовый случай даёт 0, но каждый приостановленный кадр добавляет свой n при разматывании: 0 + 1 + 2 + 3 + 4 = 10. Базовый случай лишь останавливает спуск.
Сниппет 4 — отсутствующий базовый случай
function blow(n: number): number { return n + blow(n + 1); // нет базового случая: n только растёт}blow(0);
Викторина
Completed
Что происходит при запуске blow(0) и в чём первопричина?
Heads-up Базового случая нет, а n только растёт, поэтому ни один вызов никогда не возвращает обычное значение, чтобы начать разматывание. Ничего не суммируется — программа падает раньше, чем что-либо вернёт.
Heads-up В отличие от цикла, каждый рекурсивный вызов потребляет новый кадр стека. Стек конечен, поэтому он переполняется и падает за миллисекунды, а не крутится бесконечно.
Heads-up Компиляторы обычно не доказывают достижимость базового случая; это собирается нормально. Сбой — это переполнение стека во время выполнения, а не ошибка компиляции.
Итог
Каждый сниппет читается прогоном стека в голове: вложенные вызовы держат кадры всех вызывающих функций активными ниже текущего; скопированный аргумент означает, что переприсвоение параметра никогда не трогает переменную вызывающей стороны; рекурсивный вызов кладёт новый кадр на уровень, поэтому пиковая глубина — это число вложенных активных вызовов (включая базовый случай); а рекурсия без достижимого базового случая растит стек без ограничений, пока он не переполнится. Трассируйте укладку-при-вызове и снятие-при-возврате — и ответы выпадают сами.