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

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

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 #).

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

Спасибо!

8
задан Clément 12 December 2010 в 22:42
поделиться