Поколение Python 🐍

Друзья, сегодня поговорим про рекурсию. 👀 📌 Рекурсия — это ситуация, когда объект является частью самого себя. Классические примеры рекурсии — треугольник Серпинского и эффект Дросте. 👨‍💻 В программировании рекурсия — это подход, при котором функция вызывает саму себя:

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)  # рекурсивный случай

🧐 Более подробно про рекурсию мы расскажем в планируемом курсе «Алгоритмы и структуры данных для продвинутых». Чтобы первым узнать дату выхода и другие подробности, подпишитесь на новости о курсе на нашем сайте. Ставьте реакцию: 🔥 — если уже слышали понятие рекурсии 👀 — если узнали о нем впервые #алгоритмыдляпродвинутых