Задача через такую же, но меньше
Сумма цифр 3815 — это сумма цифр 381 плюс 5.
А сумма цифр 381 — это сумма цифр 38 плюс 1. И так, пока не останется одна цифра: у неё ответ известен сразу.
. Шаг — та же задача, но меньше:
. На экране 17.Без базы — никуда
Базы нет: f(5) зовёт f(4), та — f(3), … f(−1), f(−2)… без конца.
Каждый незаконченный вызов занимает место. Около тысячи
вызовов — и Python останавливает программу: 
.
или 
из нечётного
при базе 
— та же беда.Стек вызовов
| Спуск | Что ждёт в стеке | Подъём |
|---|---|---|
 | ответа  , потом + 5 | 12 + 5 = 17 |
| ответа  , потом + 1 | 11 + 1 = 12 |
| ответа  , потом + 8 | 3 + 8 = 11 |
| база — ответ сразу | 3 |
У каждого вызова своё 
и своё «что
осталось сделать». Вызов кладётся на стек при входе и снимается при
, отдавая ответ тому, кто под ним.
Печать на спуске и на подъёме
: печать до вызова, на спуске —
3 2 1. 
: печать после вызова, на подъёме —
1 2 3.
,
потом 
печатает двоичную запись — остатки идут с
конца, а выходят с начала. 
→ 1 0 1 1.Рекурсивные объекты: фракталы
Ветка — это ствол и две ветки поменьше. Каждая повторяет целое.
Функция по формуле — задание 16 ЕГЭ
F(1) = 1;
F(n) = F(n − 1) + n, если n > 1 и n чётно;
F(n) = 2·F(n − 1), если n > 1 и n нечётно.
Чему равно F(6)?
Формула переписывается в функцию дословно: каждый случай — ветка
, база — первый случай.
Три ошибки рекурсии
- Нет базы — вызовы без конца, .
- Шаг мимо базы —
из нечётного проскакивает
. База должна ловить все концы: 
. - Забыт — сумма посчитана и выброшена, наверх
уходит
, а следующий вызов падает на
: 
.
Рекурсия или цикл
Алгоритм Евклида рекурсией — его определение почти дословно: НОД пары равен НОДу пары (b, a % b), а при b = 0 — это a.
Рекурсия хороша, когда задача сама устроена через меньшую такую же: фрактал, формула, разбор числа по цифрам.
Что делаем сегодня
- Тренажёр — шесть задач: значение функции, печать, число вызовов, формула, где упадёт, глубина стека.
- Три программы, в каждой две рекурсивные функции:
и 
, 
и
, 
и 
. - Проверка оболочкой —
: девять наборов
данных, проверка, что функции рекурсивные и без циклов, и прямые
вызовы каждой.
Отметка: три задания — «5», два — «4», одно — «3». Попыток сколько угодно. Для этой пары — новая папка.