Рекурсия
Это понятие впервые встречается на программе «Разработка и инженерия для старшеклассников» — примерно 15-17 лет (9-11 класс).
Способ решить задачу через её же уменьшенную копию: правило ссылается само на себя, пока не дойдёт до самого простого случая.
Матрёшка: внутри каждой — такая же, но меньше, и так до самой маленькой, которая уже не открывается.
Нарисовать «телевизор, показывающий сам себя» с тремя вложениями и отметить, на каком рисунок пришлось остановить.
Приём, когда функция вызывает саму себя, но для меньшей задачи. Обязательны две части: базовый случай — ответ известен сразу, без нового вызова — и рекурсивный шаг, сводящий задачу к меньшей. Без базового случая вызовы никогда не закончатся.
Собрать в Scratch свой блок «ветка», который рисует линию и дважды вызывает сам себя с меньшей длиной; показать условие остановки и предсказать, что случится без него.
Вычисление, в котором функция определена через саму себя. Каждый вызов создаёт в стеке новый кадр со своими параметрами и локальными переменными; глубина ограничена — в Python предел по умолчанию 1000 вызовов, дальше RecursionError. Любая рекурсия переписывается циклом, иногда с явным стеком. Естественна для самоподобных данных: папки в папках, деревья, фракталы.
Написать в Python рекурсивную сумму списка; вызвать её на 5000 элементов, объяснить RecursionError через стек вызовов и переписать функцию циклом.
Частое заблуждение
«Рекурсивный вызов — это прыжок к началу функции». Нет: каждый вызов — новая копия функции со своими переменными; прежние вызовы ждут её завершения.