Базовый CS с нуля
Функции и стек вызовов: постройте трассировщик стека
Читать трассировку стека в уроке — не то же, что построить её самому. В этом проекте вы делаете стек вызовов видимым: оснащаете маленькую рекурсивную программу так, чтобы она печатала стек по мере укладки и снятия кадров, затем намеренно вгоняете её в переполнение стека и объясняете, что именно закончилось.
Превратите ментальную модель юнита в нечто запускаемое: программу, которая показывает укладку и снятие собственных кадров, демонстрирует копирование параметров и воспроизводит настоящее переполнение стека с измеренной глубиной.
Постройте маленькую программу (на TypeScript/JavaScript или любом удобном языке), которая делает собственный стек вызовов наблюдаемым для рекурсивной функции, затем используйте её, чтобы продемонстрировать передачу по значению, область видимости/время жизни и настоящее переполнение стека — доказывая каждое утверждение запуском программы, а не описанием.
- Запуск оснащённой программы печатает укладку кадров на спуске и снятие на подъёме, с отступом/глубиной, соответствующими ожидаемому пику (n + 1 или n + 2).
- Показано, что поддерживаемый счётчик глубины возвращается к 0 после завершения, свидетельствуя об одном снятии на каждую укладку.
- Демонстрация передачи по значению показывает, что число вызывающей стороны не изменилось после того, как вызываемый переприсвоил свой параметр, с корректно объяснённым контрастом с изменением объекта.
- Программа производит настоящую ошибку переполнения стека (зафиксированный вывод или скриншот), и вы сообщаете примерную максимальную глубину с абзацем-объяснением, называющим фиксированную область стека как исчерпанный ресурс и отсутствующий базовый случай как причину.
- Отрисуйте стек как живую визуализацию: печатайте или рисуйте стопку кадров на каждом шаге (старейший внизу), чтобы трассировка выглядела как AlgoTrace из урока.
- Преобразуйте рекурсивную версию в эквивалентный итеративный цикл и сравните поведение по пиковой памяти — покажите, что цикл использует один кадр независимо от n, тогда как глубина рекурсии масштабируется с n.
- Измерьте фактическую максимальную глубину рекурсии, которую допускает ваш рантайм до переполнения, и оцените размер одного кадра из этой глубины и известного размера области стека (например, 1-8 МБ); обсудите, почему большие кадры означают меньшую допустимую глубину рекурсии.
- Добавьте вторую рекурсивную функцию с двумя самовызовами на уровень (например, наивный Фибоначчи) и покажите, как глубина стека всё равно масштабируется с длиной самого длинного одиночного пути, а не с общим числом вызовов.
Это цикл, стоящий за каждой трассировкой стека в отладчике, которую вы когда-либо прочтёте: вызов кладёт кадр, возврат снимает его, параметры копируются внутрь, локальные переменные живут и умирают вместе с кадром, а рекурсия — это та же укладка, повторённая снова, пока базовый случай её не остановит — или пока фиксированная область стека не переполнится. Построив трассировщик однажды и обрушив его намеренно, вы превращаете диаграмму юнита в нечто, что действительно видели своими глазами.