Как думать о рекурсии?

#python #алгоритм #рекурсия

Как опытные программисты в частности алгоритмики думают о рекурсии, как они её воспринимают?

Разбираю быструю сортировку, выступая в качестве интерпретатора и начинаю путаться
углубляясь в рекурсию.

def quick_sort(alist):
    if len(alist) <= 1:
        return

    barr = alist[0]
    left = []
    mid = []
    right = []

    for i in range(len(alist)):
        if alist[i] < barr:
            left.append(alist[i])
        elif alist[i] > barr:
            right.append(alist[i])
        else: #alist[i] == bar
            mid.append(alist[i]) 

    quick_sort(left) # Отсортировать левую часть
    quick_sort(right) # Отсортировать правую часть

    k=0
    for x in left+mid+right:
        alist[k] = x
        k+=1
    return alist

alist = [2,3,4,1]
print(quick_sort(alist))


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

Неужели всё так просто и не стоит пытаться даже читать рекурсивные функции так как
обычные.

Особенно интересно как читать рекурсию в контексте этого алгоритма!

PS. мне известны правила рекурсии: читать с конца, базовый случай, рекуррентное соотношение.
    

Ответы

Ответ 1

Любую рекурсивную функцию удобно рассматривать через ее дерево вызовов (англ. call
stack tree):



Где каждая вершина - место вызова функции, а ветви, как ни странно, ветвление - рекурсивный
вызов.



При этом важно в коде выделить 2 момента:


точка останова
место рекурсивного вызова или, другими словами, "место ветвления"


В общем случае это выглядит примерно так:

def rec_func(...):
    if(stop_condition): <-- точка останова
        return ...

    rec_func(...) <-- ветвление
    rec_func(...) <-- ветвление

    return ... <-- "главный" return текущей вершины




Теперь разберем Быструю сортировку из вопроса:

Сама по себе логика достаточно проста по своей природе:


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


Секрет кроется в первом пункте - нужно делить массивы пополам относительно какого-то
элемента, его обычно называют pivot'ом. Точка останова в данном алгоритме тоже достаточно
очевидна - if(размер текущего массива <= 1).

Из всего этого получаем такое дерево в случае, когда pivot - всегда последний элемент:



В вашем коде всегда используется первый элемент в кач-ве pivot'а, но это сути алгоритма
не меняет.

Все вершины без потомков - единичные массивы, которые мы и искали, их "конкатенация"
в конечный массив слева направо и будет искомый отсортированный массив. 

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

Pivot и равные им элементы записываются в "центральный" массив, который не нужно
сортировать или куда-то передавать.



Ну и напоследок вернемся к Фибоначчи, с которого я начал ответ. Прямолинейный код
у данного алгоритма прост, как пробка:

def F(n):
    if n == 0: return 0   <-- точка останова
    elif n == 1: return 1 <-- точка останова
    else: return F(n-1)+F(n-2) <-- 2 точки ветвления, получаем бинарное дерево


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


Ответ 2

Рекурсия похожа на доказательство по индукции, которое сами математики признают неочевидным.

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

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

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

int getHeight(BinaryTree binaryTree)
{
    int leftHeight = getHeight(binaryTree.left);
    int rightHeight = getHeight(binaryTree.right);

    return 1 + max(leftHeight, rightHeight);
}


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

Мы можем остановить её, если добирёмся до вырожденного случая. Например, мы можем
считать высоту пустого поддерева равной нулю, то есть getHeight(null) == 0.

Тогда функция принимает вид:

int getHeight(BinaryTree binaryTree)
{
    if (binaryTree == null)
        return 0;

    int leftHeight = getHeight(binaryTree.left);
    int rightHeight = getHeight(binaryTree.right);

    return 1 + max(leftHeight, rightHeight);
}


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

Часть первая: общее правило. Наш алгоритм должен выражать вычисление чего-то через
это же вычисление, но уже для более мелкой структуры. Часть вторая: остановка. В конце
вычисления должен быть вырожденный случай, который считается не рекурсивно, а тривиально.
Скажем, высота пустого дерева равно нулю. Факториал единицы равен единице. И прочее
подобное.

Ещё один пример, это арифметические выражения. Возьмём вот такое:

g * h * i + k ^ l ^ m


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

        +
    *       ^
  *   i   k   ^
g   h       l   m


В узлах дерева находятся операторы, в нашем случае это сложение +, умножение * и
возведение в степень ^. Дочерними элементами являются другие выражения.

Функция вычисления значения выражения будет выглядеть так:

double calculate(Expression expression)
{
    double left = calculate(expression.left);
    double right = calculate(expression.right);

    switch (expression.operator)
    {
        case '+':
            return left + right;

        case '*':
            return left * right;

        case '^':
            return pow(left, right);

        default:
            throw new Exception();
    }
}


Теперь надо найти вырожденные случаи, чтобы остановить рекурсивный вывод. Эти случаи,
когда выражением является одна переменная g или i. Значением такого выражения является
значение самой переменной. Предположим, что для таких переменных у нас в объекте expression
поле operator равно 'v' и значение такой переменной хранится в ассоциативном массиве
variables. Тогда функция стала бы выглядеть так:

double calculate(Expression expression)
{
    if (expression.operator == 'v')
        return variables[expression.name];

    double left = calculate(expression.left);
    double right = calculate(expression.right);

    switch (expression.operator)
    {
        case '+':
            return left + right;

        case '*':
            return left * right;

        case '^':
            return pow(left, right);

        default:
            throw new Exception();
    }
}


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

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


Ответ 3

Приведу пример написания простой рекурсивной функции для распаковки вложенных списков
с комментариями, надеюсь кому-то пригодиться:

Допустим имеем список, нужно распаковать вложенность:

t = [1, 2, [3, 4, [5]]]


Таким образом начинаем писать функцию, на вход у меня будет список:

def extract(li):


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

def extract(li, result=[]):


Затем пишем тело функции в данном примере цикл по элементам:

for i in li:


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

if isinstance(i, list):
   extract(i, result)


Ну и рядовой случай определим - который также является вариантом выхода из рекурсии,
в данном случае выход из рекурсии вызовов это дойти до пустого списка или до элемента
который не является списком:

else:
    result.append(i)


Закончим функцию командой return, c чего начали тем и закончили:

return result


Итого:

t = [1, 2, [3, 4, [5]]]

def extract(li, result=[]):
    for i in li:
        if isinstance(i, list):
            extract(i, result)
        else:
            result.append(i)
    return result

print extract(t)
# [1, 2, 3, 4, 5]


Подадим на вход что-нибудь "эдакое", чтобы посмотреть как поведёт себя функция:    

print extract([1, 2, [3, [], [5]]], [])
print extract([{}, 2, [[[[[[3]]]]]]], [])
# [1, 2, 3, 5]
# [{}, 2, 3]


Ответ 4

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


Ответ 5

Чтобы не зациклиться на "Повторить", рекурсию лучше исследовать не "сверху вниз",
а "снизу вверх", то есть с конечного условия, которое прерывает рекурсию. Например
вычисление последовательности Фибоначчи лучше начать вычислять с условия "если a==1,
то вернуть 1" до момента, когда количество возвратов будет равно искомому значению.