Оптимизация быстрой и хвостовой рекурсии

Ответ 1

Сначала начнем с краткого, вероятно, неточного, но все же действительного, определения того, что переполнение стека.

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

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

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

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

Теперь для выполнения оптимизации хвостовых вызовов существуют некоторые правила. Во-первых, каждый вызов наиболее полно, и я имею в виду, что функция должна иметь возможность дать результат в любой момент, если вы прерываете выполнение, в SICP (http://mitpress.mit.edu/sicp/full-text/book/book.html) это называется итеративным процессом, даже если функция рекурсивна.

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

Однако второй пример не имеет этой проблемы, A является константой, и состояние p и r может быть определено локально, так как вся информация, которую следует продолжать, есть, тогда можно применить TCO.

Ответ 2

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

Ответ 3

Ну, самое очевидное наблюдение было бы:

Наиболее распространенная проблема - определение

The most common cause of Qaru is excessively deep or infinite recursion.

Вторая использует менее глубокую рекурсию, чем первая (n ветки на вызов вместо n^2), поэтому она с меньшей вероятностью вызывает переполнение стека.

(поэтому более низкая сложность означает меньше шансов вызвать переполнение стека)

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

источник

Ответ 4

Ну Если вы считаете сложность этих двух методов, первый метод, очевидно, имеет большую сложность, чем второй, поскольку он вызывает Recursion для LHS и RHS как результат есть больше шансов получить переполнение стека

Примечание: Это не означает, что нет абсолютно никаких шансов получить SO во втором методе

Ответ 5

Рекурсия хвоста сама по себе недостаточна. Алгоритм с циклом while может по-прежнему использовать пространство стека O (N), уменьшая его до O (log (N)) слева как упражнение в этом разделе CLRS.

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

Плохо:

Quicksort(arraySlice){
 if (arraySlice.length > 1)
 {
  slices = Partition(arraySlice)
  (smallerSlice, largerSlice) = sortBySize(slices)
  Quicksort(largerSlice) // Not a tail call, requires a stack frame until it returns. 
  Quicksort(smallerSlice) // Tail call, can replace the old stack frame.
 }
}

Хорошо:

Quicksort(arraySlice){
 if (arraySlice.length > 1)
 {
  slices = Partition(arraySlice)
  (smallerSlice, largerSlice) = sortBySize(slices)
  Quicksort(smallerSlice) // Not a tail call, requires a stack frame until it returns. 
  Quicksort(largerSlice) // Tail call, can replace the old stack frame.
 }
}

Второй из них гарантирует, что ему не нужно больше, чем log2 (длина) кадров стека, потому что lessSlice меньше половины длины массива. Но для первого неравенства обратное и оно всегда будет больше или равно логарифмическим логам (длины), и может потребовать O (N) кадров стека в худшем случае, когда smallerslice всегда имеет длину 1.

Если вы не отслеживаете, какой срез меньше или больше, у вас будут похожие худшие случаи в первый переполненный случай, даже если в среднем потребуются стопки кадров O (log (n)). Если вы сначала сортируете меньший фрагмент, вам никогда не понадобится больше, чем log_2 (длина) кадров стека.

Если вы используете язык, который не имеет оптимизации хвостового вызова, вы можете записать вторую версию (не стекающую):

Quicksort(arraySlice){
 while (arraySlice.length > 1)
 {
  slices = Partition(arraySlice)
  (smallerSlice, arraySlice) = sortBySize(slices)
  Quicksort(smallerSlice) // Still not a tail call, requires a stack frame until it returns. 
 }
}

Еще одна вещь, которую стоит отметить, заключается в том, что если вы внедряете что-то вроде Introsort, которое изменяется на Heapsort, если глубина рекурсии превышает некоторое число, пропорциональное log (N), вы никогда не столкнетесь с потреблением стека памяти O (N), поэтому вам технически не нужно это делать. Выполнение этой оптимизации (сначала появление небольших срезов) все же улучшает постоянный коэффициент O (log (N)), поэтому настоятельно рекомендуется.