Функция может вызвать любую функцию — в том числе саму себя. Это и есть рекурсия: функция решает задачу, задавая себе тот же вопрос о меньшей её части, пока часть не станет такой маленькой, что ответ очевиден.
Самый простой пример — обратный отсчёт. Чтобы отсчитать от 3, скажите «3» — а потом отсчитайте от 2. Чтобы отсчитать от 2, скажите «2», потом отсчитайте от 1… а когда дойдёте до 0, скажите «Go!» и остановитесь:
countdown(3) печатает 3 2 1 Go!. В функции нет цикла — она вызывает саму себя
с меньшим числом, а вызов с 0 останавливает цепочку.
Функция, которая возвращает ответ
Рекурсивная функция может и возвращать значение. Факториал 5! = 5 · 4 · 3 · 2 · 1 — это просто 5 · 4!, а 4! — это 4 · 3!, и так далее до 0!, который равен 1. Каждый шаг передаёт остаток работы меньшей копии той же задачи:
fact(3) не может закончить, пока не узнает fact(2), который ждёт fact(1),
который ждёт fact(0). Последний отвечает сразу — и тогда ответы идут обратно
вверх: 1, затем 1 · 1, затем 2 · 1, затем 3 · 2. Пройдите по шагам и следите, как
растёт и уменьшается панель стека вызовов: