Рекурсия
Когда мы пишем программы, обычно мы вызываем разные функции для выполнения конкретных задач. Мы вызываем
sqrt, чтобы вычислить квадратный корень числа, или вызываем функции max и min, чтобы найти максимум или минимум из набора чисел. Рекурсия — это процесс, при котором функция вызывает саму себя. То есть, если в теле функции с именем f есть участок кода, где мы снова обращаемся к f (обычно с другими аргументами), это считается рекурсивным вызовом:def f(n): # Определяем функцию с именем f
print(f'f() called with argument {n}') # Печатаем при каждом вызове (для демонстрации)
if n <= 0: # Остановиться, если n отрицательно
print('Let\'s stop here...')
else: # Иначе вызываем f с меньшим числом
f(n - 1)
f(10)Вот что выведет программа
f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...Это простой пример, который показывает, как может выглядеть совсем базовая рекурсивная функция. В реальных задачах мы обычно выполняем в функциях какие-то вычисления и возвращаем результат, а не просто выводим сообщения.
В алгоритмических задачах рекурсия может сильно помочь, особенно когда речь идет о графах, продвинутых алгоритмах сортировки или бэктрекинге, о котором мы поговорим позже в курсе. Рекурсивные задачи довольно распространены, и иногда рекурсивное решение оказывается проще, чем итеративное с циклами.
Подход к решению большой задачи путем рекурсивного деления ее на более мелкие подзадачи, пока не дойдем до самой простой версии, лучше всего проиллюстрировать на концепции, называемой «рекурсивный прыжок веры» (recursive leap of faith).
Рекурсивный прыжок веры
Когда мы пишем рекурсивное решение, обычно создается функция, которая в определенный момент вызывает саму себя. Часть, где функция вызывает саму себя, часто и называется рекурсивным вызовом.
Самое удобное в рекурсивных решениях — это возможность «довериться» тому, что функция будет корректно работать на более простых входных данных, а затем, используя эту уверенность, правильно решить более сложные случаи. Точно так же, как мы вызываем другие функции (
sqrt, max, abs и т.д.), мы можем считать, что для простых/меньших аргументов функция уже работает, и строить текущее решение, используя результат этих вызовов.💡
Единственное требование — убедиться, что функция в итоге придет к базовому случаю (самому простому). Иначе мы столкнемся с бесконечным рекурсивным вызовом и, возможно, получим ошибку StackOverflow!
Для наглядности посмотрим, как в рекурсивной функции может происходить вычисление. Допустим, нам нужно вычислить сумму всех чисел от
0, 1, 2, …, n для заданного n.Давайте пошагово реализуем функцию
sum. Первый шаг — удостовериться, что функция правильно работает для самого простого случая (корректно считает сумму, когда n равно 0 или 1):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # Если n равно 0 => сумма равна 0
return 0 # Завершаем выполнение функции здесь
if n == 1: # Если n равно 1 => сумма равна 1
return 1 # Завершаем выполнение функции здесь
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (так как эту часть мы еще не реализовали)Имея эту часть функции, мы уже можем использовать тот факт, что
sum(0) всегда вернет 0, а sum(1) всегда вернет 1. Функция будет корректно работать, даже если вызвать sum с аргументами 0 или 1 внутри самой sum.Теперь можно пойти дальше и реализовать
sum для n = 2 и n = 3, используя результаты, которые мы уже имеем для sum(1) и sum(0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # Если n равно 2, добавляем 2 к результату sum(1), которую мы уже реализовали
return n + sum(1) # или n + sum(n - 1)
if n == 3: # Если n равно 3, добавляем 3 к результату sum(2), которую мы уже реализовали
return n + sum(2) # или n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (эту часть мы еще не реализовали)Таким образом, видно, что функция
sum корректно работает в случаях n = 0, 1, 2, 3.Имея это, мы можем реализовать функцию и для других значений
n, больших 3. Единственное требование — дойти до наших уже реализованных меньших значений (0, 1, 2, 3), когда мы рекурсивно вызываем sum. Значит, для значений 4, 5, 6 и так далее мы можем записывать sum(n) через sum(n-1), например, sum(4) вычисляем как 4 + sum(3), sum(5) — это 5 + sum(4) и так далее:def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# Для всех остальных случаев (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...Ключевые части рекурсивной функции:
- Базовый случай: Условие, при котором рекурсия прекращается. Без этого функция будет вызвать саму себя бесконечно, что приведет к зацикливанию.
В нашем примере это
n == 0иn == 1.
- Рекурсивный шаг: Место, где функция вызывает саму себя обычно с другим аргументом.
В нашем примере это
sum(n - 1).
Так как вызовы для
n == 1, n == 2 и n == 3 ничем не отличаются от случая n == 4, n == 5 и т.д., мы можем упростить функцию sum, оставив лишь один базовый случай (когда n == 0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...Таким образом, пользуясь «рекурсивным прыжком веры», мы предполагаем (или знаем), что функция корректно работает для более простых значений, и строим дальнейшую логику, исходя из этих простых случаев. Это помогает понять, как устроены рекурсивные функции и как их можно реализовывать.
💡
Рекурсивный вызов функции можно рассматривать так, словно мы вызываем совершенно другую функцию, которая, как мы точно знаем, правильно отработает для переданных аргументов.
Задача
Реализуйте рекурсивную функцию, вычисляющую
n! по модулю .Входные данные
Во входных данных содержится одно целое число
n (1 ≤ n ≤ 1000).Выходные данные
Программа должна вывести результат вычисления
n! по модулю .Примеры
Input | Output |
5 | 120 |
10 | 3628800 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB