Какое преимущество здесь использует рекурсию хвоста?

Question 1

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

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

Вот страница вики, если вам нужна дополнительная информация о том, как на самом деле работает эта «экономия пространства» и повторное использование стека, а также примеры: Хвостовый звонок

РЕДАКТИРОВАТЬ: Я не объяснил, как это относится к Quicksort, не так ли? Что ж, в этой статье брошены некоторые термины, которые делают все запутанным (и некоторые из них просто неправильно). Первая выполненная функция (QuickSort) делает рекурсивный вызов слева, рекурсивный вызов справа, а затем выходит. Обратите внимание, что рекурсивный вызов справа - это самое последнее, что происходит в функции. Если компилятор поддерживает хвостовую рекурсивную оптимизацию (объясняется выше), только левые вызовы создают новые кадры стека; Все правильные вызовы просто повторно используют текущую кадр. Это может сохранить немного Кадры стека, но все еще могут страдать от случая, когда разделение создает последовательность вызовов, где оптимизация рекурсии хвоста не имеет значения. Плюс, хотя вызовы правой стороны используют ту же кадр, вызовы левой стороны вызывают в пределах Правые вызовы по-прежнему используют стек. В худшем случае глубина стека - Н.

Вторая описанная версия нет хвостовая рекурсивная QuickSort, а скорее QuickSort, где только левая сортировка выполняется рекурсивно, а правая сортировка выполняется с использованием цикла. Фактически, этот QuickSort (как описано ранее другим пользователем) не может применять оптимизацию рецирсии хвостовой рекурсии, потому что рекурсивный вызов не является последним, чтобы выполнить. Как это работает? При правильном внедрении первый вызов QuickSort такой же, как левый вызов в исходном алгоритме. Тем не менее, рекурсивные вызовы правой стороны даже не называются. Как это работает? Что ж, петля позаботится об этом: вместо сортировки «влево, справа», он сортирует слева с вызовом, а затем сортирует правую, постоянно сортируя только левые. Анкет Это действительно смешно звучит, но в основном это просто сортирует так много левтов, что права становятся единичными элементами и не должны быть отсортированы. Это эффективно удаляет правильную рекурсию, делая функцию менее рекурсивной (псевдо рекурсивным, если хотите). Однако реальная реализация не выбирает только левую сторону каждый раз; он выбирает самую маленькую сторону. Идея все же; В основном он только рекурсивный вызов с одной стороны вместо обеих. Выбор более короткой стороны гарантирует, что глубина стека никогда не может быть больше, чем log2 (n), что является глубиной правильного двоичного дерева. Это связано с тем, что более короткая сторона всегда будет в половине половины размера нашей текущей секции массива. Реализация, данная статьей, не гарантирует это, однако, потому что она может страдать от того же самого наихудшего сценария «левая-это целое дерево». Эта статья на самом деле дает довольно хорошее объяснение этого, если вы хотите больше читать: Эффективный отбор и частичная сортировка на основе QuickSort

Question 2

Преимущество, весь смысл «смешанной рекурсивной/итерационной» версии, т.е. версии, которая обрабатывает один подражание путем рекурсии и другой подразделение по итерации, заключается гарантировать, что глубина рекурсии никогда не превысит 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, но это не будет достаточно умным, чтобы провести сравнение длины подражания.

Question 3

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

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

Вот и интересная часть:- хотя компиляторы Можно Теоретичная выполняет эту оптимизацию, они на практике не делают. Даже широко распространенные компиляторы, такие как Dot-Net и Java, не выполняют эту оптимизацию.

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

посмотри пожалуйста:

Question 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 элементов, Третий два из 3 предметов, и после четвертого все отсортировано.

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

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

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

Question 5

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



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

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

Question 6

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

Пример: наша версия -> Отпечатки n до 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

После оптимизации->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

Преимущества этой оптимизации: 1. Употребляет очень мало стеков-кадров для хвостовых рекурсивных вызовов 2. Особы меньше памяти 3. Нет необходимости сохранять запись активации процедуры, что уменьшает накладные расходы функции. 3. Нет больше ошибок сегментации - это C/C ++ и переполнение стека в Java.