Функция вызывает саму себя
Функция может вызвать саму себя — это рекурсия. Каждый вызов решает задачу чуть меньше прежней, пока она не станет совсем простой.
Простой случай называют базовым: в нем функция отвечает сразу, без нового вызова. countdown(0) ничего не выводит, а countdown(3) выводит 3 и поручает остальное countdown(2).
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
countdown(3)
print("Старт!")
Рекурсивная функция может возвращать ответ. Факториал n! = 1 · 2 · … · n, и n! = n · (n − 1)!, а 1! = 1. Так и пишут: return n * fact(n - 1).
Каждый вызов ждет ответа следующего: fact(3) ждет fact(2), тот ждет fact(1), а fact(1) отвечает сразу. Потом ответы возвращаются обратно и перемножаются.
def fact(n):
if n == 1:
return 1
return n * fact(n - 1)
print(fact(3))
print(fact(10))
Без базового случая рекурсия не останавливается: когда вызовов набирается около тысячи, Python прерывает программу ошибкой RecursionError.
Вторая частая причина — вызов не приближается к базовому случаю: f(n) вместо f(n - 1) или шаг через базовый случай, как n - 2 при нечетном n и условии n == 0.
def countdown(n):
print(n)
countdown(n - 1)
countdown(3)
Итог урока. Рекурсивная функция вызывает саму себя для задачи поменьше. В ней всегда есть базовый случай — ответ без нового вызова, — и каждый вызов приближается к нему.
Вывод до вызова идет на пути вниз, после вызова — на обратном пути. Ответ возвращают через return в каждой ветке.
В следующем уроке — рекурсия со строками и списками: хвост a[1:] как задача поменьше.
Урок пройден
Функция вызывает саму себя
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Функция вызывает саму себя
Рекурсия в Python: функция вызывает саму себя, базовый случай, вывод до и после вызова, return из рекурсии, RecursionError. В 6 заданиях вы выведете числа по возрастанию, вычислите степень и сумму цифр, перевернете строку, посчитаете шаги до единицы и прочитаете программу: что она выведет?