Рекурсия
Эта страница требует современного браузера (с поддержкой SharedArrayBuffer). Пожалуйста, обновите Chrome, Edge, Firefox или Safari до последней версии.
Функция, вызывающая саму себя
- Рекурсия — это когда функция вызывает саму себя.
- Каждый вызов должен работать с меньшей версией задачи.
- При правильном выполнении задача уменьшается, пока её не станет тривиально решить.
Базовый случай и рекурсивный случай
- Базовый случай — это простейший случай, который останавливает рекурсию.
- Рекурсивный случай снова вызывает функцию на меньшем вводе.
- Без базового случая функция никогда не остановится (ошибка).
English
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
Разобранный пример: факториал
- Факториал
n!означаетn × (n-1) × ... × 1. - В рекурсивной форме:
n! = n × (n-1)!, а базовый случай —0! = 1. - Каждый вызов умножает
nна факториал числа на единицу меньше.
English
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
Как компьютер это выполняет
- Каждый вызов ставится на стек вызовов, ожидая внутреннего вызова.
- Когда базовый случай возвращает результат, приостановленные вызовы завершаются один за другим.
- Слишком много вызовов переполняет стек — Python поднимает ошибку
RecursionError.
В псевдокоде Cambridge
- Рекурсивная функция четко называет свой базовый и рекурсивный случаи.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
Распространенные ошибки
- Любая рекурсия требует базового случая, иначе произойдет переполнение стека вызовов.
- Каждый вызов должен приближаться к базовому случаю.
Теперь попробуйте сами
- Дайте каждой функции базовый случай и рекурсивный случай.
- Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Исследовать
Recursion returns from the leaves
Each call splits into smaller calls; answers return up from the base cases.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Write a recursive count_up(n) that returns the list [1, 2, ..., n]. The base case is count_up(0) which is the empty list [].
Нажмите Запустить, чтобы увидеть результат здесь.