这个实现是尾递归的吗？

Question

我在算法书中读到Ackermann函数不能被尾递归(他们说的是"它不能转化为迭代").我对此非常困惑,所以我试着想出这个:

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

我的问题是,我不确定这实际上是尾递归.你能确认一下吗？如果没有,为什么？最终,当人们说Ackermann函数不是原始递归时,它意味着什么？

谢谢!

Answer 1

是的,它是尾递归的.通过对Continuation Passing Style的显式转换,可以对每个函数进行尾部调整.

这并不意味着函数将在常量内存中执行:您构建必须分配的延续堆栈.对连续进行去功能化以将该数据表示为简单的代数数据类型可能更有效.

作为原始递归是一个非常不同的概念,涉及到递归定义的某种形式在数学理论中的表现,但可能不是很相关的计算机科学,你知道:他们是非常降低的表现力,并与系统功能组合(从Gödel的System T开始),例如所有当前的编程语言,功能更强大.

就计算机语言而言,初始递归函数大致对应于没有一般递归的程序,其中所有循环/迭代都是静态有界的(可能的重复次数是已知的).