这个实现是否是递归的

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

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

谢谢！

来源

2010-12-12 Clément

当您传递该lambda表达式时，您仍然在构建函数调用的“堆栈”。 – 2010-12-12 22:47:22

是的，它是尾递归的。你可以用'-dlinear'选项用ocamlopt编译文件。这应该可以帮助您确定您的功能是否使用尾部呼叫。 – nlucaroni 2010-12-13 16:36:11

是的，它是尾递归的。通过对Continuation Passing Style进行显式转换，可以使每个功能都可以进行尾部记录。

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

正在primitive recursive是一个非常不同的概念，与数学理论中使用的某种形式的递归定义的表达有关，但可能与您所了解的计算机科学不太相关：它们的表达性非常低，和具有功能组成的系统（从哥德尔的System T开始），比如所有当前的编程语言，功能更强大。

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

来源

2010-12-12 23:25:58 gasche

关于原始递归，我认为重要的是，原始递归函数可以在恒定空间中实现（假设您想计算的数量可以存储在恒定空间中），而Ackermann函数不能。 – sepp2k 2010-12-12 23:30:22

很酷，非常感谢！ – 2010-12-14 05:47:48

是的。

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

只有在参数大小有界的情况下，尾递归函数才能转化为这样的迭代。在你的例子中（以及几乎任何使用continuations的递归函数），cont参数适用于所有手段和目的，可以增长到任意大小。事实上，continuation-passing风格的整个方面是将通常存在于调用堆栈中的数据（“我返回后该做什么？”）存储在连续参数中。

来源

2010-12-13 14:54:11

这里“按照定义”是什么意思？你在这里使用什么“递归函数”的定义？ – 2015-11-22 12:45:20

这个实现是否是递归的

回答

相关问题