Можно ли переписать все рекурсивные функции в виде хвостовых рекурсий?

Ответ 1

Это зависит от того, что вы просите.

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

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

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

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

Ответ 2

Да и нет.

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

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

Ответ 3

Я не знаю, можно ли переписать все рекурсивные функции как хвост-рекурсивные, но многие из них могут. Один из стандартных способов сделать это - использовать аккумулятор. Например, факториальную функцию можно записать (в Common Lisp) следующим образом:

(defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (1- n)))))

Это рекурсивный, но не хвостовой рекурсивный. Его можно сделать хвостовым рекурсивом, добавив аргумент аккумулятора:

(defun factorial-accum (accum n)
   (if (<= n 1)
       accum
       (factorial-accum (* n accum) (1- n))))

Факториалы можно рассчитать, установив аккумулятор на 1. Например, факториал 3 равен:

(factorial-accum 1 3)

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

Ответ 4

Рекурсивный алгоритм - это алгоритм, реализованный в соответствии с стратегией Divide и Conquer, где решение каждой промежуточной подзадачи создает 0, 1 или более новых меньших подзадач. Если эти подзадачи решаются в порядке LIFO, вы получаете классический рекурсивный алгоритм.

Теперь, если ваш алгоритм, как известно, создает только 0 или 1 суб-проблему на каждом шаге, тогда этот алгоритм может быть легко реализован через хвостовую рекурсию. Фактически, такой алгоритм можно легко переписать как итеративный алгоритм и реализовать простым циклом. (Излишне добавлять хвостовую рекурсию - это еще один менее явный способ реализации итерации.)

Пример такого рекурсивного алгоритма в школьной книге был бы рекурсивным подходом к факториальному вычислению: для вычисления n! вам нужно сначала рассчитать (n-1)!, то есть на каждом рекурсивном шаге вы обнаружите только одну меньшую подзадачу. Это свойство, которое делает так легко превратить алгоритм факториала в истинно итеративный (или хвостовой рекурсивный).

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

Например, такая простая проблема, как обход двоичного дерева с родительскими → дочерними ссылками (и дочерние → родительские ссылки), является, по существу, рекурсивной проблемой. Это не может быть сделано с помощью алгоритма с хвостом рекурсивности, это не может быть сделано с помощью итеративного алгоритма.

Ответ 5

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

Так просто. Независимо от того, что система времени выполнения выполняет во время выполнения неявно, мы можем сделать это самостоятельно. Здесь нет большой тайны. ПК изготовлены из кремния, меди и стали.

Тривиально реализовать DFS как цикл с явной очередью состояний/позиций/узлов для обработки. Фактически это определено - DFS заменяет выбитую первую запись в очереди всеми дугами, исходящими из нее; BFS добавляет эти дуги в конец очереди.

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

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

Ответ 6

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

Любой язык Turning complete выполняет то же преобразование, что и предоставление продолжения - создает номер Gödel для программы и входные параметры, возвращаемые не-хвостовым вызовом, и передают это как параметр для хвостового вызова - хотя, очевидно, среды где это делается для вас с продолжением, совместным подходом или другой первоклассной конструкцией, делает это намного проще.

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

Ответ 7

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

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