Я прочитал в алгоритмической книге, что функцию Аккермана нельзя сделать хвостовой рекурсией (они говорят, что «ее нельзя преобразовать в итерацию» ). Я очень озадачен этим, поэтому я попытался придумать следующее:
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 #).
Моя проблема в том, что я не уверен, что это действительно хвостовая рекурсия. Не могли бы вы подтвердить, что это так? Если нет, то почему? И, в конце концов, что означает, когда люди говорят, что функция Аккермана не является примитивно рекурсивной?
Спасибо!