Народ, всем привет. Если вы уже более-менее освоили программирование, то наверняка сталкивались с рекурсией, скажем так, с одним из самых загадочных и одновременно мощных приёмов в программировании. Она пугает новичков, вызывает путаницу и кажется чем-то "магическим". Но стоит её понять на простом примере, как всё становится логичным и даже красивым. Ну ка попробуем сегодня разобрать рекурсию на пальцах, с аналогиями, визуализациями и живыми примерами кода. Ну елси у нас получиться, конечно.
Начнем с определения. Рекурсия — это когда функция вызывает саму себя, чтобы решить задачу. Все, достаточно определений. По факту, обычно, при этом каждое новое "поколение" функции работает над упрощённой версией той же задачи. Но мы же понимаем, что рекурсия не может продолжаться бесконечно и ей нужен базовый случай, когда функция перестаёт вызывать саму себя. вот классическая структура такой функции:
def function(args):
if базовый_случай:
return результат
else:
return function(меньшие_аргументы)
Башня задач
Представьте, что перед вами гора из одинаковых коробок. Внутри каждой коробки — инструкция: "Если ты не последняя — позови следующую. Когда дойдём до конца, начнём выполнять действия обратно вверх." Так же работает рекурсия:
- спуск вниз — вызовы "вглубь".
- подъём обратно — возвращение результата обратно вверх.
Простой пример, это факториал. Факториал числа n (обозначается n!) — это произведение всех чисел от 1 до n. Скажем, факториал 5! = 5 × 4 × 3 × 2 × 1 = 120. И это можно записать рекурсивно:
def factorial(n):
if n == 1:
return 1 # базовый случай
else:
return n * factorial(n - 1) # рекурсивный вызов
Если разобрать данный код, то что тут происходит? Мы начинаем с пяти, каждый раз наше значение не равно 1. Поэтому мы идем в elsе и вновь вызываем эту же функцию, они как бы «раскрываются» одна за другой внутри друг друга. Так она доходит до единицы, и начинает «закрываться» в обратную сторону.
factorial(5)
→ 5 * factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1 (базовый случай)
→ 2 * 1 = 2
→ 3 * 2 = 6
→ 4 * 6 = 24
→ 5 * 24 = 120
Каждый вызов "запоминает" своё значение n и ждёт, пока вернётся результат из глубины. Можно еще попробовать сравнить это с матрешками, вложенные друг в друга:
- самая маленькая (базовый случай) — знает ответ.
- все остальные открываются и ждут ответ от внутренней.
- ответ возвращается наружу шаг за шагом.
Если Вам нравятся наши статьи, и вы хотите отблагодарить автора (на развитие канала), нам будет очень приятно!
Зачем нужен базовый случай?
Без базового случая функция будет вызывать себя бесконечно, пока не "съест" всю память — произойдёт ошибка Stack Overflow. Вот пример плохой рекурсии:
def loop():
return loop()
Такой код никогда не завершится.
А можно еще проще?
Ну давайте возьмем конкретный пример попроще, например, сумму чисел. Допустим, нужно посчитать сумму от 1 до n, рекурсивно. Это будет выглядеть примерно так:
def sum_n(n):
if n == 1:
return 1
else:
return n + sum_n(n - 1)
Получается, что вызов sum_n(4) даст:
sum_n(4)
→ 4 + sum_n(3)
→ 3 + sum_n(2)
→ 2 + sum_n(1)
→ 1
→ 2 + 1 = 3
→ 3 + 3 = 6
→ 4 + 6 = 10
Если взять sum_n(2), то мы получим в начале, что n= 2, значит идем в else. Там находим еще одну эту же функцию, и смотрим уже в нее sum_n(1). Так как 1 = 1, понимаем, что результат возврата функции будет = 1. Идем вверх, и получаем 2 + 1 = 3. Если грубо «открыть» функцию, то получиться что-то вроде этого:
def sum_n(2):
… пошла первая функция
if n == 1:
return 1
else:
return n + …. еще раз вызываем функцию, но уже на 1 меньше (def sum_n(2-1))
if n == 1:
return 1
else:
return n + sum_n(n - 1)
Один из лучших способов понять рекурсию, не думать сразу обо всех вызовах, а просто поверить, что внутренняя функция вернёт правильный результат. «Если функция решает меньшую версию задачи — значит она решит и мою.»
Стоит помнить, что, хотя рекурсия бывает элегантной, она не всегда практична. Вложенность ограничена глубиной стека (обычно ~1000 в Python), и в некоторых случаях проще и быстрее использовать цикл. Зато рекурсия незаменима в алгоритмах поиска в деревьях и графах (DFS, обход дерева), решениях головоломок (лабиринты, судоку, 8-ферзей), обработке вложенных структур (например, HTML/XML, JSON) или генерация фракталов.
Хотите знать больше? Читайте нас в нашем Telegram – там еще больше интересного: новинки гаджетов, технологии, AI, фишки программистов, примеры дизайна и маркетинга.