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

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

Да, это хвостовая рекурсия. Каждая функция может быть сделана tail-rec путем явного преобразования в Continuation Passing Style.

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

Будучи primitive recursive, это совсем другое понятие, связанное с выражением определенной формы рекурсивного определения, которое используется в математической теории, но, вероятно, не очень важно для компьютерной науки, как вы ее знаете: они имеют очень низкую выразительность, и системы с функциональным составом (начиная с системы Gödel System T), такие как все современные языки программирования, намного эффективнее.

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

Answer 2

Да.

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

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