Рекурсия в Python

Функция, которая вызывает саму себя, использует рекурсию.

Эта идея встречается повсюду и в математике, и в программировании. Её преимущество в том, что функция может перебирать данные, пока не придёт к результату.

Будьте внимательны, когда пишете такую функцию: легко получить функцию, которая никогда не останавливается или расходует слишком много памяти или ресурсов процессора. Однако при правильном написании рекурсия — это эффективный и математически элегантный способ программирования.

Пример

Рекурсивный обратный отсчёт, начиная с 5:

Prompt
Напишите программу на Python, которая определяет рекурсивную функцию countdown(n), выводящую числа от n до 1, а затем выводящую «Готово!». Вызовите функцию с аргументом 5.
Вывод: полная программа на Python

Базовый случай и рекурсивный случай

В любой рекурсивной функции необходимы две части:

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

Уберите базовый случай, и функция будет вызывать себя, пока Python не остановит её ошибкой рекурсии.

Здесь нет ничего важнее базового случая, поэтому всегда проверяйте, что его условие рано или поздно будет достигнуто.

Пример

Определение базового и рекурсивного случаев:

Prompt
Напишите программу на Python, которая определяет рекурсивную функцию factorial(n) с базовым случаем, возвращающим 1 при n==0 или n==1, и рекурсивным случаем, возвращающим n * factorial(n-1). Выведите факториал числа 5.
Вывод: полная программа на Python

Последовательность Фибоначчи

Классический пример рекурсии — последовательность Фибоначчи. Она начинается с 0 и 1, а каждое следующее число получается сложением двух предыдущих:

0, 1, 1, 2, 3, 5, 8, 13 и так далее.

Последовательность не имеет конца, и одно и то же правило сложения действует на всём её протяжении.

С помощью рекурсии можно вычислить любое выбранное число последовательности:

Пример

Найдите число на позиции 7 в последовательности Фибоначчи, считая от 0:

Prompt
Напишите программу на Python, которая определяет рекурсивную функцию fibonacci(n), возвращающую n, если n<=1, а иначе fibonacci(n-1) + fibonacci(n-2). Выведите 7-е число Фибоначчи.
Вывод: полная программа на Python

Рекурсия и списки

Список можно обрабатывать рекурсивно, работая только с одним элементом при каждом вызове:

Пример

Сложите все элементы списка:

Prompt
Напишите программу на Python, которая определяет рекурсивную функцию sum_list(numbers), возвращающую 0 для пустого списка, а иначе возвращающую numbers[0] + sum_list(numbers[1:]). Проверьте её на списке [1, 2, 3, 4, 5] и выведите результат.
Вывод: полная программа на Python

Пример

Найдите наибольшее значение в списке:

Prompt
Напишите программу на Python, которая определяет рекурсивную функцию find_max(numbers), возвращающую numbers[0] для списка из одного элемента, а иначе сравнивающую numbers[0] с максимумом остальной части списка. Проверьте её на списке [3, 7, 2, 9, 1] и выведите результат.
Вывод: полная программа на Python

Ограничение глубины рекурсии

Рекурсия в Python может уходить вглубь лишь до определённого предела. По умолчанию это ограничение обычно составляет около 1000 рекурсивных вызовов.

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

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

Пример

Выведите текущее ограничение глубины рекурсии:

Prompt
Напишите программу на Python, которая импортирует sys и выводит ограничение глубины рекурсии с помощью sys.getrecursionlimit().
Вывод: полная программа на Python
main.py 
import sys
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())