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

В этом руководстве мы поговорим о различных аспектах рекурсивных функций и реализуем рекурсивные функции в Python с нуля.

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

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

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

В частности, мы рассмотрим следующие темы:

  • Базовая анатомия рекурсивной функции
  • Представление памяти рекурсивной функции:
    • Дерево
    • Стек
  • Отслеживание рекурсии
  • Пространственно-временной анализ рекурсивной функции
  • Реализация простой рекурсивной функции в Python

Анатомия рекурсивной функции

Вероятно, сам термин «рекурсия» вам уже знаком. Сейчас мы рассмотрим эту концепцию еще раз, но более увлекательно, чем в учебнике.

Вернемся к определению рекурсии: «Рекурсия – это функция, которая вызывает сама себя». Давайте рассмотрим пример, подтверждающий это определение:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Вы можете видеть, что функция A() вызывает сама себя. Это пример рекурсии, где A() — рекурсивная функция.

Давайте теперь изучим некоторые основные совйства рекурсивной функции.

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

Рекурсивная функция должна иметь следующие два свойства:

  • Рекуррентное отношение
  • Условие прекращения

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

n ≤ 1 — условие завершения, или условие привязки, или базовое условие. Когда оно выполняется, рекурсия останавливается. Указание этого условия является обязательным. В противном случае функция попадет в бесконечный цикл и будет выполняться непрерывно, чего нам не очень хочется.

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

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

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

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

Представление памяти рекурсивной функции

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

Рассмотрим уже знакомую нам рекурсивную функцию A():

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

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

Дерево

Здесь следует отметить пару моментов:

  • Функция вызывается с параметром A(3) и поэтому здесь выполняются 4 (= 3 + 1) вызова функций. Если обобщить, то при вызове A(n) потребуется всего (n+1) вызовов функции.
  • Вызовы P() — это выводы, созданные функцией print(n).
  • Функция A(0) приведет к невыполнению условия if, так как мы получим n < 1, что, в свою очередь, приведет к завершению работы рекурсивной функции.

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

Стек

Стек — структура данных, организованных по принципу LIFO (англ. last in — first out, «последним пришел — первым ушел»).

От редакции Pythonist. О стеке можно почитать в статье «Реализация стека на Python».

Для представления стека вам придется пройти по дереву сверху вниз и слева направо. Следующее изображение прояснит это.

Интерпретация этого странного дерева

Имейте в виду, что стек состоит из двух операций:

  1. push используется для вставки элемента в стек
  2. pop — для извлечения элемента из стека.

Мы начинаем обход дерева в порядке сверху вниз и слева направо:

  • встречая вызов функции, вы помещаете его в стек
  • встречая вызов print() (т.е. P()), вы просто печатаете соответствующий элемент

Результатом обхода дерева от A(3) до A(0) будут следующие элементы стека (в перевернутом виде):

Теперь вы начинаете вторую половину обхода дерева, т. е. слева направо. Встречая вызов функции во второй раз, вы его удаляете (pop). Удивительно, но первым будет удален тот элемент стека, который последним попал в стек (LIFO, помните?).

Также на своем пути вы столкнетесь с тремя вызовами P(): P(1), P(2) и P(3). Вы выведете их на экран в том порядке, в котором они появляются на пути вашего обхода:

1 2 3

Наконец, когда вы закончите процесс обхода, стек будет полностью пуст.

Стек после полного извлечения всех элементов

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

Отслеживание рекурсии

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

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

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

К примеру, функция с именем main() вызвала указанную выше функцию A() как A(3). Давайте пронумеруем строки A() из оператора if для лучшего понимания:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

Записи активации будут выглядеть следующим образом:

Как упоминалось ранее, функции имеют свои копии локальных переменных и указатели инструкций (в данном случае — номера строк). После того, как A(0) завершит работу, функция произведет выталкивание (pop). Обратите внимание, что здесь используется горизонтальный стек — точно такой же, как те, которые вы видели ранее в уроке. Кроме того, пока записи помещаются в стек, также будет выполняться печать, и будут напечатаны следующие элементы:

2 1 0

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

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

Пространственно-временной анализ рекурсивной функции

Давайте быстро вспомним, что подразумевается под пространственным и временным анализом функции (также известными как пространственная и временная сложность).

Предполагается, что для заданного ввода функция должна производить некоторый вывод. Однако сколько времени для этого потребуется функции? Временная сложность — показатель приблизительного времени (также употребляется термин «время выполнения» функции). Аналогично, пространственная сложность — приблизительные требования к пространству (памяти) для функции (при заданных входных данных). Но зачем вообще нужны эти показатели?

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

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

Давайте теперь возьмем простую рекурсивную функцию и проанализируем ее пространственную и временную сложность.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Временная сложность

Прежде всего проведем анализ временной сложности. Предположим, что общее время, затраченное на вышеуказанную функцию A(), равно T(n).

T(n) представляет собой сумму времени, затраченного на сравнение, действительно ли n больше 1, и времени, затраченного на выполнение A(n-1).

T(n) можно выразить так:

Т (n) = 1 + Т (n-1),

где 1 — время, затраченное на сравнение (туда можно поставить любую константу).

Каково будет время (T(n)) для выполнения A(n-1)?

Т(n−1) = 1 + T(n−2)

Аналогично,

T(n−2) = 1 + T(n−3) и так далее.

Если внимательно отнестись к уравнениям, то можно заметить, что все они связаны. Не так ли? Если вы подставите их друг в друга, вы получите

T(n) = 1 + (1 + T(n−2)) = 2 + T(n−2) = 3 + T(n−3) = .... = k + T(n−k) ( после запуска функции k раз)

Теперь вам нужно определить, в какой момент функция остановится. В соответствии с заданным условием мы можем написать:

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

n − k = 1 => k = n − 1

Теперь подставим значение k (= n-1) в нашу формулу T(n) = k + T(n−k):

Т(n) = (n-1) + Т(n-(n-1))

=> Т (n) = (n-1) + T(1)

=> T(n) = n−1 + 1 = n // Для T(1) требуется только сравнение.

По правилу асимптотического анализа T(n) = n можно переписать как T(n) = O(n). Это означает, что временная сложность функции (при наихудшем случае) равна O(n).

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

Пространственная сложность

Анализ пространственной сложности функции прост. Эта функция находится в памяти и не использует никаких дополнительных переменных. Поэтому можно сделать вывод, что пространственная сложность функции O(n).

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

Реализация простой рекурсивной функции на Python

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

# Рекурсивная функция factorial_recursion()
def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)

# Вызов функции
num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

# Output:
# The factorial of  7  is  5040

Помните два ключевых момента для написания рекурсивной функции?

  • Рекуррентное отношение
  • Условие прекращения

В этом случае рекуррентное соотношение может быть следующим:

f(n) = n!

f(n) = n ∗ f(n−1) и так далее.

Условие завершения — когда n равно 1.

Просто, верно?

Теперь давайте реализуем итеративную версию той же функции.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)
factorial_iterative(7)

# Output:
# The factorial of 7 is 5040

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

Заключение

Вы дошли до конца. Поздравляем! В этом руководстве мы подробно разрбрали рекурсивные функции в Python. Начиная с абсолютных основ и заканчивая анализом пространственной и временной сложностей рекурсивной функции, мы охватили все. Более того, мы увидели, как рекурсия может быть полезна для решения определенных задач. Теперь вы должны быть в состоянии решать задачи, используя рекурсию. Возможно, вам будет интересно решить задачу поиска чисел Фибоначчи в заданном диапазоне.

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

Надеемся, данная статья была вам полезна! Успехов в написании кода!

Перевод статьи «Understanding Recursive Functions in Python».