Как думать о рекурсии?
1,00
р.
Как опытные программисты в частности алгоритмики думают о рекурсии, как они её воспринимают?
Разбираю быструю сортировку, выступая в качестве интерпретатора и начинаю путаться углубляясь в рекурсию.
def quick_sort(alist): if len(alist) <= 1: return<br> 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. мне известны правила рекурсии: читать с конца, базовый случай, рекуррентное соотношение.
Ответ
Любую рекурсивную функцию удобно рассматривать через ее дерево вызовов (англ. call stack tree):
Где каждая вершина - место вызова функции, а ветви, как ни странно, ветвление - рекурсивный вызов.
При этом важно в коде выделить 2 момента:
точка останова место рекурсивного вызова или, другими словами, "место ветвления"
В общем случае это выглядит примерно так:
def rec_func(...): if(stop_condition): <-- точка останова return ...<br> rec_func(...) <-- ветвление rec_func(...) <-- ветвление<br> return ... <-- "главный" return текущей вершины <br>
Теперь разберем Быструю сортировку из вопроса:
Сама по себе логика достаточно проста по своей природе:
делить массив по какому-то критерию, в данном алгоритме в зависимости от специального значения pivot, до тех пор, пока не будут получены массивы единичной длины - массивы единичной длины не могут быть не отсортированными. собрать массив из полученных отсортированный элементов
Секрет кроется в первом пункте - нужно делить массивы пополам относительно какого-то элемента, его обычно называют pivot'ом. Точка останова в данном алгоритме тоже достаточно очевидна - if(размер текущего массива <= 1).<br>Из всего этого получаем такое дерево в случае, когда 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 точки ветвления, получаем бинарное дерево <br>Кстати, по дереву вызовов вычисления числа Фибоначчи видно, почему рекурсия для данного случая - плохо. В дерево встречается целые ветви с одинаковыми вычислениями.
Разбираю быструю сортировку, выступая в качестве интерпретатора и начинаю путаться углубляясь в рекурсию.
def quick_sort(alist): if len(alist) <= 1: return<br> 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. мне известны правила рекурсии: читать с конца, базовый случай, рекуррентное соотношение.
Ответ
Любую рекурсивную функцию удобно рассматривать через ее дерево вызовов (англ. call stack tree):
Где каждая вершина - место вызова функции, а ветви, как ни странно, ветвление - рекурсивный вызов.
При этом важно в коде выделить 2 момента:
точка останова место рекурсивного вызова или, другими словами, "место ветвления"
В общем случае это выглядит примерно так:
def rec_func(...): if(stop_condition): <-- точка останова return ...<br> rec_func(...) <-- ветвление rec_func(...) <-- ветвление<br> return ... <-- "главный" return текущей вершины <br>
Теперь разберем Быструю сортировку из вопроса:
Сама по себе логика достаточно проста по своей природе:
делить массив по какому-то критерию, в данном алгоритме в зависимости от специального значения pivot, до тех пор, пока не будут получены массивы единичной длины - массивы единичной длины не могут быть не отсортированными. собрать массив из полученных отсортированный элементов
Секрет кроется в первом пункте - нужно делить массивы пополам относительно какого-то элемента, его обычно называют pivot'ом. Точка останова в данном алгоритме тоже достаточно очевидна - if(размер текущего массива <= 1).<br>Из всего этого получаем такое дерево в случае, когда 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 точки ветвления, получаем бинарное дерево <br>Кстати, по дереву вызовов вычисления числа Фибоначчи видно, почему рекурсия для данного случая - плохо. В дерево встречается целые ветви с одинаковыми вычислениями.
