📌 Рекурсия — это ситуация, когда объект является частью самого себя. Классические примеры рекурсии — треугольник Серпинского и эффект Дросте.
👨💻 В программировании рекурсия — это подход, при котором функция вызывает саму себя:
def func():
func()
❌ В данном случае при вызове функция
func() будет бесконечно вызывать саму себя. Когда стек достигнет максимального допустимого размера (максимальной глубины рекурсии), Python принудительно завершит работу программы с ошибкой RecursionError: maximum recursion depth exceeded.✔️ Чтобы избежать бесконечного вызова функции, в рекурсии необходимо предусмотреть базовый случай — условие, при котором функция перестанет вызывать саму себя и вернет какое-нибудь значение. Условие, при котором функция вызывает саму себя, называется рекурсивным случаем.
💡 Идея рекурсии заключается в сведении исходной задачи к более простой подзадаче, которая решается той же функцией. Этот процесс продолжается до тех пор, пока исходная задача не будет сведена к простейшему случаю, при котором сведение к подзадаче невозможно.
🔸🔸🔸🔸🔸🔸⬇️
Реализуем рекурсивную функцию
sum_to(), которая принимает положительное целое число n и возвращает сумму чисел от 1 до n включительно.Сведем задачу к подзадаче: вычислим сумму чисел от
1 до n - 1, а затем прибавим к результату n. Для этой подзадачи используем ту же функцию sum_to(). При n = 1 сведение к подзадаче невозможно, поэтому в таком случае вернем явный ответ: 1.def sum_to(n):
if n == 1: # базовый случай
return 1
return n + sum_to(n - 1) # рекурсивный случай
🧐 Более подробно про рекурсию мы расскажем в планируемом курсе «Алгоритмы и структуры данных для продвинутых». Чтобы первым узнать дату выхода и другие подробности, подпишитесь на новости о курсе на нашем сайте.
Ставьте реакцию:
🔥 — если уже слышали понятие рекурсии
👀 — если узнали о нем впервые
#алгоритмыдляпродвинутых #алгоритмы