Рекурсия

В мире программирования рекурсия является фундаментальной концепцией. В большинстве интервью Python это можно было бы спросить. Являетесь ли вы программистом или специалистом по данным, каждый должен знать эту концепцию. Рекурсивными являются не только алгоритмы поиска и сортировки, но и каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это делает рекурсию ключевой концепцией, которую необходимо пересмотреть перед любым собеседованием по программированию.

Здесь я попытаюсь максимально просто объяснить рекурсию, разделив рекурсию на шаги:

  • Что такое рекурсия?
  • Почему мы используем рекурсию?
  • Рекурсия в Python.
  • Примеры рекурсии.

Что такое рекурсия?

Рекурсия — это понятие в математике, которое мы используем и в программировании. Рекурсия — это процесс определения проблемы с точки зрения самой себя. Это самое простое определение рекурсии.

В программировании рекурсия — это процесс, в котором функция прямо или косвенно вызывает сама себя, а соответствующая функция вызывается как рекурсивная функция.

Таким образом, рекурсия заключается в том, чтобы определить новую, используя саму себя.

Почему мы используем рекурсию?

Большинство задач решаемы без рекурсии. Так что, строго говоря, рекурсия обычно не нужна. Рекурсия предназначена для решения проблем, которые можно разбить на более мелкие повторяющиеся задачи. Это особенно хорошо для работы с вещами, которые имеют много возможных ветвей и слишком сложны для итеративного подхода.

Плюсы:

  • Быстрее при оптимизации.
  • Меньше кода. Вы можете писать рекурсивный код быстрее, а для отладки у вас будет меньше кода по сравнению с итеративным кодом.
  • Декларативный.
  • Эффективная сортировка и поиск

Минусы:

  • Максимальная глубина рекурсии.
  • По ошибке или непреднамеренно использовать рекурсию без базового условия.
  • Больше потребление памяти.

Рекурсия в Python

Когда вы вызываете функцию в Python, интерпретатор создает новое локальное пространство имен, чтобы имена, определенные в этой функции, не сталкивались с идентичными именами, определенными где-либо еще.

def recurse():
    x = 5
recurse()

когда recurse()executes в первый раз, он создаст локальное пространство имен в python, а 10 будет присвоено x. После этого recurse() вызывает себя рекурсивно. При втором запуске recurse() интерпретатор создает второе пространство имен и также присваивает 10 значение x. Эти два экземпляра имени x отличаются друг от друга и могут сосуществовать без конфликтов, поскольку они находятся в разных пространствах имен.

После запуска recurse() он будет вызывать себя снова и снова, но python покажет трассировку, потому что невозможно запускать его вечно.

RecursionError: maximum recursion depth exceeded

Потому что в вашей системе существует ограничение рекурсии.

Теоретически он будет работать вечно, но практически ничто не вечно из-за ограничения памяти. Python этого не позволяет. Интерпретатор ограничивает максимальное количество рекурсивных вызовов функции, и когда она достигает этого предела, она вызывает исключение RecursionError.

Таким образом, чтобы остановить выполнение нашей функции навсегда, должно быть базовое условие.

Базовый вариант.

Базовое условие поможет завершить процесс рекурсии или остановить функцию, вызывая себя снова и снова. Есть один или несколько базовых случаев, которые можно решить напрямую без необходимости дальнейшей рекурсии.

Рекурсивный регистр.

Когда желаемое состояние не достигнуто и функция переходит на другой рекурсивный шаг. Каждый рекурсивный вызов постепенно приближает решение к базовому варианту.

Примеры рекурсии

Обратный отсчет до нуля

В приведенном выше примере он попросит пользователя ввести номер. В базовом случае n = ноль, и на этом рекурсия остановится. В рекурсивном случае в качестве аргумента передается на единицу меньше текущего значения n, и, подобно этому, рекурсия приближается к базовому варианту.

Вычислить факториал

В следующем примере используется математическое понятие факториал. Факториал положительного целого числа n, обозначаемого как n! и рассчитывается как:

n! = n*(n-1)*(n-2)...3*2*1

Другими словами, n! является произведением всех целых чисел от 1 до n включительно.

Примеров рекурсии может быть так много, но возникает вопрос: «Действительно ли необходимо реализовывать рекурсию?». Потому что эти два вышеприведенных кода также можно написать с помощью цикла for. Во-вторых, скорость выполнения. Между рекурсивными и нерекурсивными решениями (итеративными) могут быть значительные различия в производительности.

Это был один из немногих простых примеров рекурсии.

Я перечисляю больше примеров, на которых вы можете попрактиковаться или изучить рекурсию, чтобы получить опыт. Я не буду объяснять эти примеры, потому что любой новичок, прочитав эту статью, может запутаться, увидев эти продвинутые примеры рекурсии в структуре данных. Чтобы сделать эту статью простой, я просто пишу названия примеров.