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

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

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

Содержание

Анатомия рекурсивной функции
Представление памяти рекурсивной функции
Трассировка рекурсии
Пространственно-временной анализ рекурсивной функции
Реализация простой рекурсивной функции на Python

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

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

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

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

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

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

Основы рекурсивной функции

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

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

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

$n\le 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 (после вызова функции A(0)) получит n < 1, что приведет к завершению функции.

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

Стек – это структура данных, в которой порядок элементов соблюдается по принципу «последний пришел – первый ушел» (LIFO).

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

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

Push, с помощью которой вы вставляете элемент в стек.
Pop, с помощью которой вы извлекаете элемент из стека.

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

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

Ниже будут приведены элементы стека, полученные в результате обхода дерева от A(3) до A(0), только в порядке сверху вниз:

Стек вызовов с элементами, сверху вниз: A(0), A(1), A(2), A(3).

Теперь вы приступаете ко второй половине обхода дерева, то есть к порядку слева направо. Всякий раз, увидев вызов функции повторно, вы должны извлечь его из стека (pop). Примечательно, что элемент A(0), который будет первым извлечен из стека, был последним, который попал в стек (LIFO, помните?). Дальше на вашем пути встретятся три вызова P(): P(1), P(2) и P(3). Вы будете выводить их по мере обнаружения в процессе обхода. Порядок будет таким:

1 2 3

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

Тот же стек вызовов, но все элементы зачеркнуты

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

Трассировка рекурсии

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

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

Важный момент: при вызове функции в памяти создается запись активации, содержащая локальные переменные этой функции и указатель инструкций (обозначающий следующую задачу, которая будет выполнена после возврата к этой функции). Скажем, функция 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) функция A() завершится и произойдет выгрузка (операции pop). Обратите внимание, что здесь используется горизонтальный стек, точно такой же, как и те, что вы видели ранее. В то время как записи добавляются в стек, также происходит печать. Будут напечатаны следующие элементы:

2 1 0

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

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

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

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

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

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

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

void A(n){
    if(n>1) // Условие привязки
    {
       return A(n-1);
    }
}

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

$T(n)$ – это сумма времени, затраченного на сравнение, больше ли n, чем 1, и времени, затраченного на выполнение A(n-1). Таким образом, $T(n)$ можно выразить как

$T(n)$ = 1 + $T(n-1)$

1 – это время, затраченное на сравнение (можно подставить любую константу). А каково будет время выполнения A(n-1)?

$T(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)$:

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

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

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

Анализ пространственной сложности нашей функции прост. Это in-memory функция (выполняется в оперативной памяти), не использующая никаких дополнительных переменных. Таким образом, можно сделать вывод, что пространственная сложность этой функции $\mathcal{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))

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)

The factorial of 7 is 5040

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

Поздравляем!

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

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

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