Рекурсивные алгоритмы — тренажёр для 9 класса

Раздел 1 — Определение

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

Рекурсия опирается на математическую идею определения через предыдущее значение. Факториал задаётся формулой n! = n · (n − 1)!, а числа Фибоначчи — формулой F(n) = F(n − 1) + F(n − 2): в обеих записях определяемое имя встречается справа от знака равенства.

Место темы в курсе 9 класса — переход от циклов к другому способу организации повторения. Цикл повторяет действия, изменяя переменную-счётчик; рекурсия повторяет вызовы, уменьшая аргумент. Обе конструкции решают задачу многократного выполнения, но рекурсия ближе к формулировке задачи на языке математики.

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

Раздел 2 — Ключевые правила

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

1. Базовый случай проверяется первым. Для факториала базовый случай — n = 0 или n = 1, результат равен 1. Без проверки в начале функция уйдёт в вызовы до аварийного завершения.
2. Аргумент рекурсивного вызова строго приближается к базовому. Запись F(n − 1) уменьшает параметр на единицу, поэтому цепочка вызовов конечна; запись F(n) внутри F(n) конечности не даёт.
3. Число базовых случаев равно числу «предыдущих» значений в формуле. У Фибоначчи формула использует два предыдущих члена, значит база состоит из двух равенств: F(1) = 1 и F(2) = 1.
4. Результат внутреннего вызова участвует в вычислении внешнего. В строке return n * fact(n − 1) умножение выполняется после того, как fact(n − 1) вернёт число.
5. Глубина рекурсии ограничена. Стек вызовов имеет конечный размер: при слишком большой глубине среда выдаёт ошибку переполнения стека (RecursionError в Python).

Раздел 3 — Разбор примеров

Пример 1. Факториал, определение и трассировка.

def fact(n): if n <= 1: return 1 # базовый случай return n * fact(n - 1) # рекурсивный вызов

Вызов fact(4) порождает цепочку: fact(4) → 4 · fact(3) → 4 · 3 · fact(2) → 4 · 3 · 2 · fact(1). Вызов fact(1) попадает в базовый случай и возвращает 1, после чего произведения «сворачиваются» в обратном порядке: 2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24. Вывод: рекурсия работает в два хода — спуск до базы и подъём с вычислением результатов.

Пример 2. Числа Фибоначчи, дерево вызовов.

def fib(n): if n <= 2: return 1 return fib(n - 1) + fib(n - 2)

Вызов fib(5) разворачивается в fib(4) + fib(3); fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1). Базовые вызовы возвращают 1, дальше: fib(3) = 2, fib(4) = 3, fib(5) = 3 + 2 = 5. Всего выполнено 9 вызовов при ответе 5. Вывод: каждый вызов ветвится надвое, поэтому количество вызовов растёт быстрее самого результата.

Пример 3. Отсутствие базового случая.

def bad(n): return n * bad(n - 1)

Аргумент уменьшается: 3, 2, 1, 0, −1, −2, … — но условия остановки нет, поэтому вызовы продолжаются, пока не переполнится стек. Вывод: уменьшение аргумента без проверки конечности не спасает — бесконечная рекурсия завершается ошибкой, а не результатом.

Пример 4. Недостижимый базовый случай.

Функция def f(n): if n == 0: return 0; return f(n - 2) при n = 5 даёт цепочку 5 → 3 → 1 → −1 → −3: значение 0 пропускается, база не срабатывает. Вывод: базовый случай должен покрывать все значения, при которых спуск заканчивается, — надёжнее писать if n <= 0.

Пример 5. Сумма цифр числа.

def s(n): return n if n < 10 else n % 10 + s(n // 10). Для n = 407: 7 + s(40) → 7 + 0 + s(4) → 7 + 0 + 4 = 11. Вывод: рекурсия применима всюду, где задача сводится к такой же задаче меньшего масштаба.

Раздел 4 — Таблица

Раздел 5 — Типичные ошибки

Пропущен базовый случай. Ошибка возникает, когда ученик переносит в код только формулу n! = n · (n − 1)!, забыв про равенство 1! = 1. Неправильно: return n * fact(n - 1); правильно: сначала if n <= 1: return 1, затем рекурсивная строка.

Аргумент не уменьшается. Причина — описка в скобках. Неправильно: return n * fact(n); правильно: return n * fact(n - 1). Проверка простая: аргумент вызова обязан отличаться от параметра функции.

Потерян результат вызова. Ученик пишет fact(n - 1) отдельной строкой без return и без умножения, вычисление уходит «в никуда». Правильно: значение вложенного вызова используется в выражении — return n * fact(n - 1).

Одна база вместо двух у Фибоначчи. При условии только if n == 1: return 1 вызов fib(2) уходит к fib(0) и fib(−1), база не достигается. Правильно: if n <= 2: return 1.

Смешение номера и значения. Запись F(5) = 5 верна, но из неё не следует F(n) = n: F(6) = 8. Правильно — восстанавливать ряд 1, 1, 2, 3, 5, 8, 13 по формуле, а не по совпадению.

Раздел 6 — Пошаговый алгоритм

1. Прочитайте определение функции и выпишите условие базового случая с его результатом.
2. Выпишите рекурсивную строку и определите, как меняется аргумент.
3. Подставьте заданное n и записывайте цепочку (или дерево) вызовов, пока аргумент не попадёт в базовый случай.
4. Отметьте значения, возвращённые базовыми вызовами.
5. Поднимайтесь по цепочке снизу вверх, подставляя полученные числа в отложенные выражения.
6. Запишите значение самого первого вызова — оно и есть ответ.
7. Проверьте результат независимым способом: факториал — прямым произведением 1·2·…·n, Фибоначчи — выписыванием ряда до нужного номера; при расхождении найдите шаг, где база или аргумент записаны неверно.

Раздел 7 — Как запомнить

• Формула «БАЗА + ШАГ»: без базы — зависание, без шага — нет движения к базе.
• Образ матрёшки: вызовы вкладываются вниз до самой маленькой (база), затем собираются вверх.
• Проверочный вопрос к любому коду: «Какое n остановит функцию и достижимо ли оно из моего n?»
• Опорные числа для самопроверки: 4! = 24, 5! = 120; ряд Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21.
• Правило счёта баз: сколько предыдущих значений в формуле — столько строк условия остановки.