Привет! Надеюсь у тебя все хорошо. В этой статье я расскажу

  • Что такое рекурсия,
  • Как выделяется память для рекурсии
  • Когда мы должны использовать рекурсию (над итерацией)
  • Это ограничения (или когда не использовать)
  • Справочные статьи.


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

Итак, давайте начнем с примера из реальной жизни. Простая, но захватывающая иллюстрация — Google Recursion. Заметили, что происходит?

Он продолжает спрашивать вас «Вы имели в виду рекурсию?И даже после щелчка по нему он продолжает задавать один и тот же вопрос. Разве он не вызывает себя снова и снова? Что ж, это рекурсия в игре.

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

def counting(no):

  print(no)
  counting(no+1)

Войти в полноэкранный режим

Выйти из полноэкранного режима



Когда рекурсия останавливается?

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

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

def counting (no):
  if no==10:
    print("Recursion ends at 10")
  else:
    print(no)
    counting(no+1)
Войти в полноэкранный режим

Выйти из полноэкранного режима

В приведенном выше коде, когда наша рекурсия попадает на вход с no=10, он просто печатает инструкцию и больше не вызывает сам себя. Таким образом, на этот раз у нас нет переполнения стека.



Разве это не похоже на итерацию?

Что ж, это так. Подобно итерации (независимо от цикла for или while), в рекурсии мы также выполняем подзадачи повторно. В общем, мы можем реализовать любую логику рекурсии с итерацией, если захотим, и наоборот.


Тогда зачем рекурсия?

Несмотря на то, что это выглядит похоже, рекурсия имеет определенные преимущества перед итерацией на основе удобочитаемости кода.

Особенно, когда нам нужно поддерживать стек, чтобы отслеживать процессы, которые мы вызываем, чтобы на них можно было снова ссылаться в более поздний момент времени. В отличие от итерации, рекурсия неявно сохраняет стек вызовов памяти для своего выполнения.



Как работает рекурсия?

Как сказано, рекурсия работает с помощью Memory Call stack.

Другими словами, при вызове любой функции выделяется некоторая память для хранения ее данных, чтобы к ней можно было обращаться при необходимости. Эта память не освобождается до тех пор, пока функция не вернет управление или не выйдет из ссылки на функцию.
Теперь, когда другие функции вызываются последовательно, эти вызовы также накапливаются в памяти, пока их выполнение не будет завершено один за другим в последовательности LIFO (Last In First Out).

Тот же процесс происходит, когда происходит рекурсия. Все вызовы функций накапливаются в памяти до тех пор, пока не будут выполнены. Как только функция возвращает управление, стек извлекается и выполняется следующий вызов функции в стеке.

Давайте проанализируем фрагмент кода:

def counting(no):
    if no>5:
        return
    counting(no+1)
    print(no, end = " ")

counting(0)
Войти в полноэкранный режим

Выйти из полноэкранного режима

Вывод фрагмента кода будет выглядеть так: 5 4 3 2 1 0


Почему вывод идет в обратном порядке?

Если мы запустим в режиме отладки и посмотрим на стек вызовов, мы найдем что-то вроде:

Фрагмент стека вызовов в рекурсии



Стек вызовов декодирования:

  • Как мы видим, стек вызовов начался с вызова функции в строке no. 9 . Это точка входа нашей рекурсивной функции и counting(0) толкается.

  • Опубликуйте это каждый раз, когда мы звонили counting(no+1) из строки no. 6 , у нас есть его запись в стеке вызовов с соответствующим значением. Оператор печати никогда не выполняется, так как до этого рекурсивно вызывается только функция.

  • Как только мы достигнем базового случая, то есть no>5 , мы возвращаемся из функции в первый раз. Следовательно, последний вызов функции, который был отправлен с помощью no=6 выталкивается из стека.

  • После этого начинается извлечение из стека вызовов. Память указывает на следующую функцию в стеке вызовов и выполняет оставшиеся инструкции в функции, которые ранее не выполнялись.

  • В таком случае, print(no) казнен и 5 печатается в терминале.

  • Точно так же все последовательные функции извлекаются из стека вызовов одна за другой по методу LIFO, и оператор печати выполняется с соответствующими значениями no . 4 3 2 1 0 печатается.

Вот и все.



Когда его использовать?

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

Другими словами, мы можем найти применение рекурсии там, где

  1. У нас есть определенная подзадача, которую необходимо выполнить.
  2. Мы хотим повторять эту подзадачу снова и снова.
  3. Нам нужен стек для отслеживания процессов, чтобы к ним можно было обращаться позже.

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



Когда не использовать?

Даже с этим заманчивым преимуществом рекурсии (кто не любит читаемый код? 👀), у рекурсии есть определенные недостатки. Как мы уже видели, рекурсия требует большего использования памяти, поскольку она сохраняет вызовы каждой функции в неявном стеке. Это может привести к значительным накладным расходам, когда задача проще. В этих случаях итерация должна быть лучшим выбором.

Например, для реализации ряд Фибоначчи итерация будет лучшим вариантом, чем рекурсия.



Использованная литература:



Вывод:

Я надеюсь, что эта статья поможет вам начать работу с основными понятиями рекурсии.

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

Для получения таких обновлений и статей о структуре данных и алгоритме следите за этой страницей и продолжайте поддерживать. Ваше здоровье! 🥂