Понимание рекурсии

Погружение в рекурсию и ее преимущества и ограничения по сравнению с итерациями

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

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

Что нужно для рекурсии

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

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

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

Наряду с методом «разделяй и властвуй» рекурсия широко используется многими традиционными алгоритмами программирования, такими как:

1. Ханойская башня
2. Сортировка слиянием
3. Быстрая сортировка
4. Обход дерева (BFS и DFS)

Как реализовать рекурсию в Python

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

def factorial_using_loop(num):
    factorial = 1
    for i in range(1, num+1):
        factorial *= i
    return factorial

num = 5
print(f"Factorial of {num} is => {factorial_using_loop(num)}")

# Output: Factorial of 5 is => 120

Теперь давайте посмотрим, как это будет выглядеть, если мы используем рекурсивную функцию,

def factorial_using_recursion(num):
    if num == 0 or num == 1:
        return 1
    else:
        return num * factorial_using_recursion(num-1)
    
num = 5
print(f"Factorial of {num} is => {factorial_using_recursion(num)}")
# Output: Factorial of 5 is => 120

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

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

def fibonacci_using_recursion(num):
    if num <= 0:
        return []
    elif num == 1:
        return [0]
    elif num == 2:
        return [0, 1]
    else:
        return fibonacci_using_recursion(num-1) + [fibonacci_using_recursion(num-1)[-1] + fibonacci_using_recursion(num-2)[-1]]
print(fibonacci_using_recursion(10))
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Сравнение рекурсии с итеративными функциями

В Python рекурсия, циклы for и циклы while — все это способы управления потоком программы, но они используются немного по-разному.

Давайте посмотрим, как они сравниваются с точки зрения потребления памяти и скорости выполнения.

Потребление памяти

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

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

Скорость выполнения

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

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

Подводя итог,

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

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

Первоначально опубликовано на https://dev.to 25 января 2023 г.