В чем преимущество использования хвостовой рекурсии здесь?

Question

Я читал статьи, описывающие, как пространственная сложность quicksort может быть уменьшена с помощью хвостовой рекурсивной версии, но я не могу понять, как это происходит. Ниже приведены два варианта:

QUICKSORT(A, p, r) 
     q = PARTITION(A, p, r) 
     QUICKSORT(A, p, q-1) 
     QUICKSORT(A, q+1, r) 


TAIL-RECURSIVE-QUICKSORT(A, p, r) 
    while p < r 
     q = PARTITION(A, p, r) 
     TAIL-RECURSIVE-QUICKSORT(A, p, q-1) 
     p = q+1 

(Источник - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html)

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

Псевдокод выше взят из статьи - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html Объяснение приводится в статье путает меня еще больше -

Quicksort перегородки данного суб-массива и переходит в два раза рекурсию; один в левой части и один справа. Для каждого из этих рекурсивных вызовов потребуется отдельный поток стека. Это пространство используется для хранения индексирующих переменных для массива на уровне определенного уровня рекурсии. Если мы увидим это с начала до конца выполнения, мы увидим, что пространство стека удваивается на каждом уровне .

Так как же Tail-Recursive-Quicksort исправить все это?

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

Я не вижу, как пространство стека удваивается на каждом уровне выполнения в случае обычной быстрой сортировки.

Примечание: - В статье не упоминается оптимизация компилятора.

Answer 1

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

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

Вот вики-странице, если вы хотите получить больше информации о том, как на самом деле работает это «экономия пространства» и повторное использование стека, наряду с примерами: Tail Call

Edit: я не объяснить, как это относится к быстрой сортировки, не так ли? Ну, некоторые термины брошены вокруг в этой статье, которые делают все запутанным (и некоторые из них просто неверны). Первая функция (QUICKSORT) делает рекурсивный вызов слева, рекурсивный вызов справа, а затем завершается. Обратите внимание, что рекурсивный вызов справа - это последнее, что происходит в функции. Если компилятор поддерживает рекурсивную оптимизацию хвоста (объяснено выше), только левые вызовы создают новые фреймы стека; все правильные вызовы просто повторно используют текущий кадр. Это может сэкономить кадров стека, но все равно может пострадать от случая, когда разбиение создает последовательность вызовов, в которых оптимизация хвостовой рекурсии не имеет значения. Плюс, хотя правосторонние вызовы используют один и тот же фрейм, левые вызовы, вызываемые , в пределах, вызовы с правой стороны все еще используют стек. В худшем случае глубина стека Н.

Вторая версия описанная не хвост рекурсивной быстрой сортировки, а скорее, где быстрая сортировка только левая сортировка выполняется рекурсивно, а правая сортировка осуществляется с помощью петли , Фактически, этот quicksort (как ранее описано другим пользователем) не может использовать оптимизацию рекурсии хвоста, поскольку рекурсивный вызов не является последним, что нужно выполнить. Как это работает? При правильной реализации первый вызов quicksort совпадает с левым вызовом в исходном алгоритме. Однако рекурсивные вызовы с правой стороны даже не называются. Как это работает? Ну, петля позаботится об этом: вместо сортировки «влево-то вправо», он сортирует слева с вызовом, затем сортирует справа, постоянно сортируя только левые справа. Это действительно смешное звучание, но в основном просто сортировка так много левых, что права становятся едиными элементами и их не нужно сортировать. Это эффективно удаляет правильную рекурсию, делая функцию менее рекурсивной (псевдорекурсивной, если хотите). Однако реальная реализация не выбирает только левую сторону каждый раз; он выбирает самую маленькую сторону. Идея все та же; в основном это рекурсивный вызов только с одной стороны, а не с обеих сторон. Выбор более короткой стороны гарантирует, что глубина стека никогда не может быть больше log2 (N), что является глубиной правильного бинарного дерева. Это связано с тем, что более короткая сторона всегда будет составлять не более половины нашего текущего массива. Однако реализация данной статьи не гарантирует этого, поскольку она может страдать от одного и того же наихудшего сценария «левое - это все дерево». Эта статья на самом деле дает довольно хорошее объяснение этому, если вы готовы сделать больше чтения: Efficient selection and partial sorting based on quicksort

Answer 2

Преимущество использования tail-recursion: = чтобы компилятор оптимизировал код и преобразовал его в нерекурсивный код.

Преимущество нерекурсивного кода над рекурсивным: = нерекурсивный код требует меньше памяти для выполнения, чем рекурсивный. Это происходит из-за свободных кадров стека, которые потребляет рекурсия.

Здесь идет интересная часть: - хотя составители могут теоретически выполнять эту оптимизацию, они на практике не делают. даже широко распространенные компиляторы, такие как dot-net и java, не выполняют эту оптимизацию.

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

см:

1. https://stackoverflow.com/q/340762/1043824
2. Why doesn't .NET/C# optimize for tail-call recursion?
3. https://stackoverflow.com/a/3682044/1043824

Answer 3

Преимущество, вся суть "смешанной рекурсивного/итерационного" версия, то есть версия, которая обрабатывает один суб -рейтинг путем рекурсии и другого поддиапазона путем итерации состоит в том, что, выбирая, какой из двух поддиапазонов обрабатывается рекурсивно, вы можете гарантировать t глубина рекурсии никогда не будет превышать log2 N, независимо от того, насколько плохим является выбор стержня.

Для TAIL-RECURSIVE-QUICKSORT псевдокода, представленного в этом вопросе, где рекурсивная обработка выполняется сначала буквальным рекурсивным вызовом, что рекурсивный вызов должен быть предоставлен короче поддиапазона. Это само по себе будет гарантировать, что глубина рекурсии будет ограничена log2 N. Таким образом, для достижения гарантии глубины рекурсии, код абсолютно должен сравнивать длины поддиапазонов, прежде чем решать, какой субдиапазон обрабатывается рекурсивным вызовом.

Надлежащая реализация такого подхода может выглядеть следующим образом (заимствование вашего псевдокода в качестве отправной точки)

HALF-RECURSIVE-QUICKSORT(A, p, r) 
    while p < r 
     q = PARTITION(A, p, r) 
     if (q - p < r - q) 
     HALF-RECURSIVE-QUICKSORT(A, p, q-1) 
     p = q+1 
     else 
     HALF-RECURSIVE-QUICKSORT(A, q+1, r) 
     r = q-1 

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

Если вы выполните поиск Google на условиях «qsort loguy higuy», вы легко найдете множество примеров другой популярной реализации QuickSort (стандартный стиль библиотеки C), основанный на той же идее использования рекурсии только для одного из два поддиапазона. Эта реализация для 32-разрядных платформ использует явный стек максимальной глубины ~ 32, потому что он может гарантировать, что глубина рекурсии никогда не будет выше. (Точно так же, 64-битные платформы нужно будет только стек глубины ~ 64.)

QUICKSORT версия, которая делает две буквенные рекурсивных вызовов значительно хуже в этом отношении, так как повторяющиеся плохой выбор поворота может сделать это, чтобы достичь очень высокой рекурсии глубина, до N в худшем случае. С двумя рекурсивными вызовами вы не можете гарантировать, что глубина рекурсии будет ограничена log2 N. Умный компилятор может заменить трейлинг-вызов на QUICKSORT с итерацией, т. Е. Превратить ваш QUICKSORT в ваш TAIL-RECURSIVE-QUICKSORT, но он не будет достаточно умен, чтобы выполнить сравнение длины субдиапазона.

Answer 4

Здесь, похоже, есть некоторая лексика.

Первая версия хвостовая рекурсии, потому что последнее утверждение является рекурсивным вызовом:

QUICKSORT(A, p, r) 
    q = PARTITION(A, p, r) 
    QUICKSORT(A, p, q-1) 
    QUICKSORT(A, q+1, r) 

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

TAIL-RECURSIVE-QUICKSORT(A, p, r) 
    while p < r 
    q = PARTITION(A, p, r) 
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1) 
    p = q+1 

преимущество этого в том, что обычно, вам потребуется меньше стека памяти. Почему это? Чтобы понять, представьте, что вы хотите отсортировать массив с 31 элементом. В очень маловероятном случае, когда все разделы идеальны, т. Е. Они разделяют массив прямо посередине, ваша глубина рекурсии будет равна 4. Действительно, первый раскол привел бы к двум разделам из 15 элементов, второй - к двум разделам из 7 элементов, третий из двух из трех предметов, а после четвертого все сортируется.

Но перегородки редко бывают идеальными. В результате не все рекурсии становятся одинаково глубокими. В нашем примере у вас могут быть некоторые, которые имеют только три уровня глубины, а некоторые из них 7 или более (наихудший случай - 30). Исключив половину рекурсий, у вас есть хороший шанс, что ваша максимальная глубина рекурсии будет меньше.

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

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

Answer 5

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

void print(int n) { 
    if (n < 0) return; 
    cout << " " << n; 
// The last executed statement is recursive call 
    print(n-1); 
    print(n-1); 
} 

Этот хвост рекурсивный?