Рекурсивные алгоритмы (Python)

В этой статье вы сможете узнать:

что такое рекурсивная функция и из каких двух обязательных частей она состоит;
как реализовать вычисление факториала и чисел Фибоначчи рекурсивно;
как проследить порядок вызовов рекурсивной функции вручную.

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

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

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

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

Если базового случая нет или он никогда не достигается, рекурсия становится бесконечной и приводит к ошибке переполнения стека вызовов.

Вычисление факториала

Факториал числа $n$ определяется как произведение всех натуральных чисел от 1 до $n$ , при этом $0! = 1$ . Рекурсивное определение: $n! = n \cdot (n-1)!$ при $n>0$ , и $0!=1$ как базовый случай.

def factorial(n):
    if n == 0:            # базовый случай
        return 1
    return n * factorial(n - 1)   # рекурсивный случай

print(factorial(5))   # 120

Вычисление чисел Фибоначчи

Числа Фибоначчи определяются рекуррентно: $F(0)=0$ , $F(1)=1$ , а каждое следующее число равно сумме двух предыдущих: $F(n) = F(n-1) + F(n-2)$ .

def fib(n):
    if n <= 1:              # базовый случай
        return n
    return fib(n - 1) + fib(n - 2)   # рекурсивный случай

print([fib(i) for i in range(8)])   # [0, 1, 1, 2, 3, 5, 8, 13]

Обратите внимание: у этой функции два рекурсивных вызова внутри одного вызова, поэтому общее количество вызовов растёт очень быстро (экспоненциально) с увеличением $n$ .

Как проследить порядок вызовов рекурсивной функции

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

Пример. Проследим вызовы для factorial(3):

$\text{factorial}(3) = 3 \cdot \text{factorial}(2) = 3 \cdot (2 \cdot \text{factorial}(1)) = 3 \cdot (2 \cdot (1 \cdot \text{factorial}(0))) = 3 \cdot 2 \cdot 1 \cdot 1 = 6$

Вызовы идут «вглубь» до базового случая ( $\text{factorial}(0)=1$ ), а затем результаты умножаются в обратном порядке при возврате из каждого вызова.

Рекурсия с печатью значений

Порядок вывода данных в рекурсивной функции зависит от того, находится ли команда вывода до или после рекурсивного вызова.

def rec_before(n):
    if n == 0:
        return
    print(n)          # печать до рекурсивного вызова
    rec_before(n - 1)

rec_before(4)   # выведет: 4 3 2 1

def rec_after(n):
    if n == 0:
        return
    rec_after(n - 1)
    print(n)           # печать после рекурсивного вызова

rec_after(4)    # выведет: 1 2 3 4

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

Алгоритм разбора рекурсивной функции

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

Примеры решения

Пример 1. Определите, что вернёт вызов factorial(4).

$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$

Ответ: 24.

Пример 2. Определите, что вернёт вызов fib(6) при использовании функции из раздела про числа Фибоначчи.

По последовательности чисел Фибоначчи: $F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8$ .

Ответ: 8.

Пример 3. Определите, что выведет вызов rec_after(3) из раздела про порядок вывода.

Функция уходит в рекурсию до базового случая ( $n=0$ ), а затем при возврате печатает значения в порядке возрастания: 1, 2, 3.

Ответ: программа выведет 1, 2, 3 (каждое на отдельной строке).

Задание 16 ЕГЭ: анализ рекурсивной функции

Задание 16 ЕГЭ по информатике проверяет умение вычислить значение функции, заданной рекуррентными соотношениями (часто с условием на чётность или диапазон аргумента), не прибегая к программе, а анализируя её вручную.

Пример. Алгоритм вычисления функции $F(n)$ , где $n$ — целое число, задан соотношениями:

$F(n) = n$ , если $n < 10$ ;
$F(n) = F(n-3) + 5$ , если $n \geq 10$ и $n$ чётно;
$F(n) = F(n-1) \cdot 2$ , если $n \geq 10$ и $n$ нечётно.

Найдите значение $F(15)$ .

Эквивалентная запись на Python:

def F(n):
    if n < 10:
        return n
    if n % 2 == 0:
        return F(n - 3) + 5
    else:
        return F(n - 1) * 2

print(F(15))

Разбираем вручную, спускаясь к базовому случаю:

$F(15) \; (\text{нечётно}) = F(14) \cdot 2$ $F(14) \; (\text{чётно}) = F(11) + 5$ $F(11) \; (\text{нечётно}) = F(10) \cdot 2$ $F(10) \; (\text{чётно}) = F(7) + 5$ $F(7) \; (\text{базовый случай, } 7<10) = 7$

Теперь поднимаемся обратно: $F(10) = 7+5=12$ ; $F(11)=12\cdot2=24$ ; $F(14)=24+5=29$ ; $F(15)=29\cdot2=58$ .

Ответ: $F(15) = 58$ .

Задание 23 ЕГЭ: подсчёт количества программ через рекурсию

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

Пример. У исполнителя есть две команды: «прибавь 2» и «умножь на 3». Сколько существует программ, которые переводят число 1 в число 13, если по ходу выполнения программы значения не должны превышать 13?

target = 13

def count_ways(n):
    if n == target:
        return 1
    if n > target:
        return 0
    return count_ways(n + 2) + count_ways(n * 3)

print(count_ways(1))

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

Ответ: программа выведет 4 — существует ровно 4 различных способа получить 13 из 1 с помощью команд «+2» и «×3» без превышения 13 на промежуточных шагах.

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

Часто задаваемые вопросы

Что произойдёт, если в рекурсивной функции забыть указать базовый случай? Функция будет вызывать саму себя бесконечно (или до тех пор, пока аргумент не перестанет изменяться разумным образом), что приведёт к превышению максимальной глубины рекурсии и ошибке RecursionError в Python.

Почему рекурсивное вычисление чисел Фибоначчи работает медленно для больших значений $n$ ? Потому что функция fib(n) вызывает fib(n-1) и fib(n-2), каждый из которых снова порождает по два новых вызова, — одни и те же значения вычисляются многократно, из-за чего общее число вызовов растёт экспоненциально с увеличением $n$ .

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

Как определить глубину рекурсии для конкретного вызова? Глубина рекурсии равна количеству вложенных вызовов до достижения базового случая — например, для factorial(n) глубина рекурсии равна $n+1$ (включая финальный вызов с базовым случаем factorial(0)).

Задачи для самостоятельного решения

Определите, что вернёт вызов factorial(6).
Определите, что вернёт вызов fib(9), используя определение $F(0)=0$ , $F(1)=1$ .
Напишите рекурсивную функцию для вычисления суммы цифр натурального числа и определите её базовый случай.
Определите порядок вывода чисел для вызова rec_before(5) из раздела про печать значений.
Напишите рекурсивную функцию, вычисляющую $n$ -ю степень числа $a$ (то есть $a^n$ ), используя рекурсивное определение $a^n = a \cdot a^{n-1}$ , $a^0=1$ .
Объясните, почему вызов функции без базового случая приводит к ошибке RecursionError, а не выполняется бесконечно на практике.
Функция $F(n)$ задана соотношениями: $F(n)=n$ при $n<8$ ; $F(n)=F(n-2)+3$ при $n\geq8$ и чётном $n$ ; $F(n)=F(n-1)\cdot2$ при $n\geq8$ и нечётном $n$ . Найдите $F(13)$ .
У исполнителя есть две команды: «прибавь 1» и «умножь на 2». Найдите количество программ, переводящих число 1 в число 8 без превышения 8 на промежуточных шагах.