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

Question

В Introduction to Algorithmsp169 речь идет об использовании хвостовой рекурсии для Quicksort.

оригинальный Quicksort алгоритм ранее в главе (в псевдокоде)

Quicksort(A, p, r) 
{ 
if (p < r) 
{ 
    q: <- Partition(A, p, r) 
    Quicksort(A, p, q) 
    Quicksort(A, q+1, r) 
} 
} 

Оптимизированная версия с помощью хвоста рекурсии следующим

Quicksort(A, p, r) 
{ 
while (p < r) 
{ 
    q: <- Partition(A, p, r) 
    Quicksort(A, p, q) 
    p: <- q+1 
} 
} 

Где Partition сортирует массив согласно а стержень.

Разница в том, что второй алгоритм вызывает только Quicksort, чтобы отсортировать LHS.

Может кто-нибудь объяснить мне, почему первый алгоритм может вызвать переполнение стека, а второй - нет? Или я не понимаю книгу.

Answer 1

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

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

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

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

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

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

source

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

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

Bad:

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. 
} 
} 

Второй один guarenteed никогда не нужно больше, чем log2 (длина) кадры стека, потому что smallerSlice меньше чем в два раза меньше, чем arraySlice. Но для первого неравенства меняются на противоположные, и он всегда будет иметь больше или равен логарифмическим строкам log2 (длина), и может потребовать фреймы кадров O (N) в худшем случае, когда минималистская линия всегда имеет длину 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), вы никогда не столкнетесь с потреблением памяти quicksort в наихудшем случае O (N), поэтому вам технически не нужно это делать. Выполнение этой оптимизации (сначала появление небольших срезов) все же улучшает постоянный коэффициент O (log (N)), поэтому настоятельно рекомендуется.