8

我在一本算法书中读到 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# 代码）。

我的问题是，我不确定这实际上是尾递归。你能确认是吗？如果不是，为什么？最后，当人们说阿克曼函数不是原始递归时，这是什么意思？

谢谢！

4

2 回答 2

15

是的，它是尾递归的。每个函数都可以通过显式转换为Continuation Passing Style来进行 tail-rec 。

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

作为原始递归是一个非常不同的概念，与数学理论中使用的某种形式的递归定义的表达性有关，但可能与你所知道的计算机科学不太相关：它们的表达性非常低，并且系统具有功能组合（从哥德尔的 System T 开始），例如所有当前的编程语言，都更加强大。

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

于 2010-12-12T23:25:58.993 回答
2

是的。

根据定义，任何递归函数都可以转换为迭代，只要它可以访问无界的类似堆栈的构造。有趣的问题是它是否可以在没有堆栈或任何其他无限数据存储的情况下完成。

只有当参数的大小有界时，尾递归函数才能变成这样的迭代。在您的示例（以及几乎所有使用延续的递归函数）中，该cont参数用于所有手段和目的的堆栈，可以增长到任何大小。实际上，延续传递风格的全部意义在于将通常存在于调用堆栈上的数据（“我返回后要做什么？”）存储在延续参数中。

于 2010-12-13T14:54:11.653 回答