Является ли эта реализация хвостовой рекурсивной?

Question

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

let Ackb m n =
  let rec rAck cont m n = 
    match (m, n) with
      | 0, n -> cont (n+1)
      | m, 0 -> rAck cont (m-1) 1
      | m, n -> rAck (fun x -> rAck cont (m-1) x) m (n-1)
  in rAck (fun x -> x) m n
;;

(это код OCaml / F #).

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

Спасибо!

Answer 1

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

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

Быть примитивно-рекурсивным - это совсем другое понятие, связанное с выразительностью определенной формы рекурсивного определения, которое используется в математической теории, но, вероятно, не очень уместно для компьютерной науки, как вы ее знаете: они имеют очень низкую выразительность, и системы с композицией функций (начиная с системы Геделя System T), такие как все современные языки программирования, гораздо более мощные.

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

Answer 2

Да.

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

Хвосто-рекурсивная функция может быть превращена в такую ​​итерацию, только если размер ее аргументов ограничен.В вашем примере (и почти в любой рекурсивной функции, использующей продолжения) параметр cont является для всех средств и целей стеком, который может вырасти до любого размера.Действительно, весь смысл стиля прохождения продолжения заключается в хранении данных, обычно присутствующих в стеке вызовов («что делать после того, как я вернусь?») В параметре продолжения.