Как работает Рекурсия в Python — пример рекурсивной функции

Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:

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

Рекурсивные функции

Рекурсивная функция — это та, которая вызывает сама себя.

В качестве простейшего примера рассмотрите следующий код:

Копировать



def factorial_recursive(n):

    if n == 1:

        return n

    else:

        return n*factorial_recursive(n-1)

Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).

Вкратце о факториалах

Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.

Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040

Вывести факториал числа можно с помощью функции:

Копировать



num = 3

print(f"Факториал {num} это {factorial_recursive(num)}")

Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:

def factorial_recursive(n):

    ...

По аналогии с обычной функцией имя рекурсивной указывается после def, а в скобках обозначается параметр n:

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

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

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1.

Это и есть рекурсия. В нашем примере это так сработало:

3 * (3-1) * ((3-1)-1)  # так как 3-1-1 равно 1, рекурсия остановилась

Детали работы рекурсивной функции

Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.

Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:

Копировать



# Первый вызов

factorial_recursive(3):

    if 3 == 1:

        return 3

    else:

        return 3*factorial_recursive(3-1)



# Второй вызов

factorial_recursive(2):

    if 2 == 1:

        return 2

    else:

        return 2*factorial_recursive(2-1)



# Третий вызов

factorial_recursive(1):

    if 1 == 1:

        return 1

    else:

        return 1*factorial_recursive(1-1)

Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1), поэтому она добавляет в стек еще один вызов.

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

/\ factorial_recursive(1) - последний вызов
|| factorial_recursive(2) - второй вызов
|| factorial_recursive(3) - первый вызов

Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.

Но как только в стек добавляется вызов factorial_recursive(1), для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.

factorial_recursive(1) завершается, отправляет 1 в
factorial_recursive(2) и выпадает из стека.
factorial_recursive(2) завершается, отправляет 2*1 в
factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.

Рекурсия в Python имеет ограничение в 3000 слоев.

Копировать



>>> import sys

>>> sys.getrecursionlimit()

3000

Рекурсивно или итеративно?

Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?

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

Рекурсия может быть медленной, если реализована неправильно

Тем не менее рекурсия может быть медленной, если ее неправильно реализовать. Из-за этого вычисления будут происходить чаще, чем требуется.

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

Копировать



def factorial_iterative(num):

    factorial = 1

    if num < 0:

        print("Факториал не вычисляется для отрицательных чисел")

    else:

        for i in range (1, num + 1):

            factorial = factorial*i

        print(f"Факториал {num} это {factorial}")