Что такое хвостовая рекурсия?

52

Я знаю общую концепцию рекурсии. Я наткнулся на концепцию хвостовой рекурсии при изучении алгоритма быстрой сортировки. В этом видео о алгоритме быстрой сортировки из MIT в 18:30 секунд профессор говорит, что это хвостовой рекурсивный алгоритм. Мне не ясно, что на самом деле означает хвостовая рекурсия.

Может ли кто-нибудь объяснить концепцию на соответствующем примере?

Некоторые ответы, предоставленные SO-сообществом здесь .

Компьютерщик
источник
Расскажите подробнее о контексте, в котором вы встретили термин хвостовая рекурсия . Ссылка? Цитирование?
А.Шульц
@ A.Schulz Я поставил ссылку на контекст.
Компьютерщик
5
Посмотрите на « Что такое хвостовая рекурсия? » На stackoverflow
Vor
2
@ajmartin Этот вопрос граничит с переполнением стека, но решительно относится к информатике , поэтому в принципе информатика должна дать лучшие ответы. Это не произошло здесь, но все еще можно переспросить здесь в надежде на лучший ответ. Гик, ты должен был упомянуть свой предыдущий вопрос о SO, чтобы люди не повторяли то, что уже было сказано.
Жиль "ТАК - перестань быть злым"
1
Также вы должны сказать, что является неоднозначной частью или почему вы не удовлетворены предыдущими ответами, я думаю, что ТАК люди дают хорошие ответы, но что заставило вас спросить это снова?

Ответы:

52

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

int f (int x, int y) {
  if (y == 0) {
    возврат х;
  }

  вернуть f (x * y, y-1);
}

является хвостовой рекурсивной (поскольку последняя инструкция является рекурсивным вызовом), тогда как эта функция не является хвостовой рекурсивной:

int g (int x) {
  if (x == 1) {
    возврат 1;
  }

  int y = g (x-1);

  возврат x * y;
}

так как он выполняет некоторые вычисления после возврата рекурсивного вызова.

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

Мэтт Льюис
источник
2
Вы написали: «Это означает, что нам вообще не нужен стек вызовов для всех рекурсивных вызовов». Стек вызовов всегда будет там, просто адрес возврата не нужно записывать в стек вызовов, верно?
Компьютерщик
2
Это в некоторой степени зависит от вашей модели вычислений :) Но да, на реальном компьютере стек вызовов все еще существует, мы просто не используем его.
Мэтт Льюис
Что делать, если это последний вызов, но для цикла for. Таким образом, вы делаете все свои вычисления выше, но некоторые из них в цикле for, какdef recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
thed0ctor
13

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

Иногда разработка хвостовой рекурсивной функции требует создания вспомогательной функции с дополнительными параметрами.

Например, это не хвостовая рекурсивная функция:

int factorial(int x) {
    if (x > 0) {
        return x * factorial(x - 1);
    }
    return 1;
}

Но это хвосто-рекурсивная функция:

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x > 0) {
        return tailfactorial(x - 1, x * multiplier);
    }
    return multiplier;
}

потому что компилятор может переписать рекурсивную функцию в нерекурсивную, используя что-то вроде этого (псевдокод):

int tailfactorial(int x, int multiplier) {
    start:
    if (x > 0) {
        multiplier = x * multiplier;
        x--;
        goto start;
    }
    return multiplier;
}

Правило для компилятора очень простое: когда вы найдете " return thisfunction(newparameters);", замените его на " parameters = newparameters; goto start;". Но это может быть сделано только в том случае, если значение, возвращаемое рекурсивным вызовом, возвращается напрямую.

Если все рекурсивные вызовы в функции можно заменить таким образом, то это хвостовая рекурсивная функция.

Вильям Бур
источник
13

Мой ответ основан на объяснении, приведенном в книге « Структура и интерпретация компьютерных программ» . Я очень рекомендую эту книгу ученым.

Подход A: Линейный рекурсивный процесс

(define (factorial n)
 (if (= n 1)
  1
  (* n (factorial (- n 1)))))

Форма процесса для подхода A выглядит следующим образом:

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

Подход B: Линейный итерационный процесс

(define (factorial n)
 (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
 (if (> counter max-count)
  product
  (fact-iter (* counter product)
             (+ counter 1)
             max-count)))

Форма процесса для подхода B выглядит следующим образом:

(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120

Линейный итеративный процесс (подход B) выполняется в постоянном пространстве, хотя процесс является рекурсивной процедурой. Следует также отметить, что в этом подходе набор переменных определяет состояние процесса в любой точке, а именно. {product, counter, max-count}, Это также методика, с помощью которой хвостовая рекурсия позволяет оптимизировать компилятор.

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

ajmartin
источник
5

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

QUICKSORT(A, p, r)
    if(p < r)
    then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q–1)
        QUICKSORT(A, q+1, r)

Вот итерационная версия:

QUICKSORT(A)
    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        r = q - 1

    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        p = q + 1
saadtaame
источник