Рекурсия

Базовый и рекурсивный случай, вычисление факториала и чисел Фибоначчи, сравнение с итеративным решением

Аналогия с матрёшкой

Хорошей наглядной аналогией рекурсии служит русская матрёшка: чтобы «разобрать» матрёшку, нужно открыть её и либо обнаружить внутри пустоту (базовый случай — самая маленькая, неразборная матрёшка), либо обнаружить внутри точно такую же, но меньшую матрёшку, с которой нужно повторить ту же самую процедуру разбора (рекурсивный случай). Именно эта идея — «решение через точно такую же, но меньшую версию себя» — лежит в основе любого рекурсивного алгоритма, будь то вычисление числа, обход файлов во вложенных папках или разбор арифметического выражения со скобками.

Что такое рекурсия

Рекурсией в программировании называют способ определения (и решения) задачи, при котором функция вызывает саму себя с изменёнными, обычно «уменьшенными», аргументами. Рекурсивный подход естественно возникает там, где саму задачу можно свести к точно такой же, но более простой задаче того же типа: например, чтобы вычислить факториал числа n, достаточно вычислить факториал числа n−1 и умножить его на n. Рекурсия — мощная альтернатива циклам, особенно удобная для задач, имеющих естественную рекурсивную структуру: обход деревьев, разбор вложенных структур, некоторые математические последовательности.

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

Любая корректно построенная рекурсивная функция обязательно содержит два элемента. Базовый случай (или условие остановки) — простейший вариант задачи, ответ на который известен без дальнейших рекурсивных вызовов; именно он прекращает цепочку самовызовов. Рекурсивный случай — правило, сводящее исходную задачу к такой же задаче, но с аргументом, приближающим её к базовому случаю. Если в функции отсутствует базовый случай или рекурсивный случай никогда не достигает его, вызовы функции продолжаются бесконечно, что приводит к ошибке переполнения стека вызовов.

Рекурсивное вычисление факториала

Факториал натурального числа n (обозначается n!) — произведение всех натуральных чисел от 1 до n. Факториал имеет естественное рекурсивное определение: факториал нуля равен 1 (базовый случай), а факториал любого числа n>0 равен n, умноженному на факториал числа n−1 (рекурсивный случай).

$0!=1\left(базовыйслучай\right)$

$n!=n·\left(n-1\right)!,приn>0\left(рекурсивныйслучай\right)$

def factorial(n):

if n == 0: # базовый случай

return 1

return n * factorial(n — 1) # рекурсивный случай

print(factorial(5)) # 120

print(factorial(0)) # 1

print(factorial(7)) # 5040

Проследим цепочку вызовов для factorial(4): вызывается factorial(4), которая вызывает factorial(3), та вызывает factorial(2), затем factorial(1) и, наконец, factorial(0) — базовый случай, возвращающий 1. После этого вызовы «разворачиваются» в обратном порядке: factorial(1) возвращает 1·1=1, factorial(2) возвращает 2·1=2, factorial(3) возвращает 3·2=6, а factorial(4) возвращает 4·6=24.

Рекурсивное вычисление чисел Фибоначчи

Числа Фибоначчи — последовательность 0, 1, 1, 2, 3, 5, 8, 13, 21, …, в которой каждое следующее число равно сумме двух предыдущих. Эта последовательность также имеет естественное рекурсивное определение с двумя базовыми случаями.

$F\left(0\right)=0,F\left(1\right)=1\left(базовыеслучаи\right)$

$F\left(n\right)=F\left(n-1\right)+F\left(n-2\right),приn>1\left(рекурсивныйслучай\right)$

def fibonacci(n):

if n == 0:

return 0

if n == 1:

return 1

return fibonacci(n — 1) + fibonacci(n — 2)

for i in range(10):

print(fibonacci(i), end=' ')

print() # 0 1 1 2 3 5 8 13 21 34

Сравнение рекурсивного и итеративного решений

Любую рекурсивную функцию, вычисляющую числовую последовательность, можно переписать без рекурсии — с помощью обычного цикла (итеративно). Итеративное решение хранит промежуточные результаты в переменных и последовательно их обновляет.

def factorial_iterative(n):

result = 1

for i in range(1, n + 1):

result *= i

return result

def fibonacci_iterative(n):

a, b = 0, 1

for _ in range(n):

a, b = b, a + b

return a

print(factorial_iterative(5)) # 120

print(fibonacci_iterative(9)) # 34

Рекурсивные вычисления с несколькими параметрами: наибольший общий делитель

Рекурсия хорошо подходит не только для вычисления последовательностей, но и для реализации классических математических алгоритмов. Например, алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух натуральных чисел естественно формулируется рекурсивно: НОД числа a и 0 равен самому a (базовый случай), а в общем случае НОД(a, b) равен НОД(b, остаток от деления a на b) — рекурсивный случай, на каждом шаге уменьшающий второй аргумент.

$НОД\left(a,0\right)=a;НОД\left(a,b\right)=НОД\left(b,amodb\right),приb>0$

def gcd(a, b):

if b == 0: # базовый случай

return a

return gcd(b, a % b) # рекурсивный случай

print(gcd(48, 18)) # 6

print(gcd(17, 5)) # 1 — числа взаимно простые

Глубина рекурсии и переполнение стека

Каждый рекурсивный вызов функции добавляет новую запись (кадр) в специальную область памяти — стек вызовов, где хранятся локальные переменные и точка возврата для каждого незавершённого вызова. Если глубина рекурсии становится слишком большой, происходит переполнение стека — в Python это приводит к ошибке RecursionError. По умолчанию Python ограничивает максимальную глубину рекурсии значением около 1000 вызовов; изменить этот предел можно функцией sys.setrecursionlimit(), однако злоупотреблять этим не стоит — правильнее переписать глубоко рекурсивный алгоритм итеративно.

import sys

def count_down(n):

if n == 0:

return

count_down(n — 1)

try:

count_down(10000)

except RecursionError:

print('Превышена максимальная глубина рекурсии!')

print('Текущий предел рекурсии:', sys.getrecursionlimit())

Эффективность рекурсивного вычисления чисел Фибоначчи

Наивная рекурсивная функция fibonacci(n) крайне неэффективна: при вычислении F(n) она многократно, заново пересчитывает одни и те же значения F(k) для меньших k (например, F(5) вычисляет F(3) дважды, F(2) — трижды и так далее), из-за чего общее число вызовов растёт экспоненциально с ростом n. Итеративное решение, напротив, вычисляет каждое значение последовательности ровно один раз.

$сложностьрекурсивноговычисленияF\left(n\right)=O\left(2^n\right)$

$сложностьитеративноговычисленияF\left(n\right)=O\left(n\right)$

Из-за этой разницы наивная рекурсивная функция для n=35 может выполняться заметно дольше секунды, тогда как итеративная справляется с этой же задачей практически мгновенно даже для гораздо больших n. Существуют более продвинутые техники (мемоизация — запоминание уже вычисленных значений), позволяющие ускорить именно рекурсивное решение, но они выходят за рамки базового курса.

Типичные ошибки

Самая грубая и опасная ошибка — отсутствие базового случая или условие, которое никогда не выполняется: такая функция вызывает саму себя бесконечно (точнее, до превышения предела глубины рекурсии) и завершается ошибкой RecursionError. Вторая ошибка — неверно сформулированный рекурсивный случай, при котором аргумент не приближается к базовому случаю (например, вызов factorial(n) вместо factorial(n — 1)). Третья распространённая проблема — использование наивной рекурсии для чисел Фибоначчи или аналогичных задач при больших n, что приводит к экспоненциальному росту времени выполнения программы и таймауту при проверке решения. Наконец, начинающие иногда забывают, что результат рекурсивного вызова нужно использовать (например, через return или в выражении), а не просто вызвать функцию «ради побочного эффекта».

Краткий словарь терминов

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

Базовый случай — простейший вариант задачи, завершающий цепочку рекурсивных вызовов без дальнейшей рекурсии.

Рекурсивный случай — правило, сводящее исходную задачу к такой же, но более простой (приближённой к базовому случаю).

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

RecursionError — ошибка Python, возникающая при превышении максимально допустимой глубины рекурсии.

Итеративное решение — решение задачи с помощью цикла, без использования рекурсивных вызовов функции.

Заключение

Рекурсия — элегантный и мощный инструмент, позволяющий выразить решение задачи через решение более простого варианта той же задачи, но требующий обязательного наличия корректного базового случая и внимательности к эффективности и глубине вызовов. Понимание того, как функция обращается к самой себе, напрямую подводит к следующей важной теме — алгоритмам поиска элемента в массиве, один из которых (бинарный поиск) также нередко реализуют рекурсивно.