Рекурсия: базовый случай, шаг и трассировка

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

Нужны обе части. Без базового случая вызовы не остановятся; без уменьшения задачи базовый случай может существовать в коде, но никогда не быть достигнут.

1def sum_to(number):2    if number == 0:3        return 04    return number + sum_to(number - 1)

При sum_to(3) первый вызов не знает окончательного ответа, пока не завершится sum_to(2). Цепочка углубляется до нуля, а затем значения возвращаются в обратном порядке.

Для трассировки разделите лист на две части: аргументы при входе и результаты при возврате. Это не смешивает два направления движения.

В заданиях с рекурсивной функцией часто нужно не написать код, а аккуратно вычислить значение. Правило остаётся тем же: найдите базовые аргументы, раскройте только нужные вызовы и отдельно соберите возвраты. Если ветвей две, рисуйте небольшое дерево и не считайте один и тот же узел «на глаз» несколько раз.

1def f(number):2    if number <= 1:3        return 14    return f(number - 1) + f(number - 2)

Для f(3) понадобятся f(2) и f(1), а для f(2) — f(1) и f(0). Сначала подпишите обе единицы в базе, затем сложите возвраты снизу вверх: f(2) равно 2, f(3) равно 3.

Проверка number == 0 не спасёт функцию, если положительный аргумент на каждом шаге увеличивается. Расстояние до нуля растёт, и цепочка закончится RecursionError.

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