Рекурсия
При изучении программирования мы часто решаем задачи линейно и просто. Но что делать, если мы сталкиваемся с проблемой, которую нужно разбить на меньшие, похожие задачи? Здесь на помощь приходит рекурсия.
Проще говоря, рекурсия — это когда функция вызывает саму себя во время выполнения. Это может показаться бесконечным циклом, но если мы правильно разработаем функцию, она в конечном итоге достигнет точки, когда перестанет вызывать саму себя.
Представьте себе матрёшку. Каждый раз, когда вы открываете куклу, внутри оказывается ещё одна, меньшего размера. И так продолжается, пока вы не доберётесь до самой маленькой, которую уже нельзя открыть. Этот процесс открытия кукол похож на рекурсию. Чтобы достичь самой маленькой куклы (решить самую сложную проблему), вы последовательно решаете более простые версии той же задачи (открываете большие куклы), пока не достигнете точки, где проблему больше нельзя упростить (последняя кукла).
Процесс решения большой задачи путём рекурсивного деления её на меньшие задачи до достижения самой маленькой/простой лучше всего понимается через концепцию «рекурсивного прыжка веры».
Рекурсивный прыжок веры
При реализации рекурсивного решения задачи обычно создаётся функция, которая в определённый момент вызывает саму себя. Эта часть, где функция вызывает себя, обычно называется рекурсивным вызовом.
Преимущество рекурсивных решений в том, что мы можем предположить, что функция работает правильно при вызове с простыми аргументами, а затем реализовать корректное поведение для более сложных случаев. Подобно тому, как мы вызываем другие функции, такие как
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. Главное требование — чтобы при вызове функции sum из неё самой мы приходили к тем меньшим значениям n (0, 1, 2 или 3). Таким образом, для больших значений n, таких как 4, 5 или 6 и т.д., мы можем реализовать функцию sum, используя тот факт, что для вычисления 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
# ...Таким образом, благодаря рекурсивному прыжку веры, мы предполагаем/знаем, что функция правильно работает для меньших/более простых случаев, и строим остальную часть функции на основе этих простых случаев. Это помогает понять, как работают рекурсивные функции и как их можно реализовать.
💡
Рекурсивный вызов функции подобен вызову совершенно другой функции, которая, вы точно знаете, будет работать с переданными аргументами.