这个c语言递归详解尾递归能改成普通递归吗？

来源：蜘蛛抓取(WebSpider) 时间：2022-11-04 09:54 标签： c语言递归详解

最近看到一个系统，递归运用规则，用ocaml写的， 说到为了避免堆栈溢出，采用了CPS（Continuation_passing_style）风格。

于是深入了解一下递归与CPS的关系。

递归大家都熟悉，例如阶乘函数，递归写法如下（ocaml语法）：

递归是语言的重要特性。 例如，在无类型的lambda演算中，可以这样写：

当然，也可以采用大名鼎鼎的Y combinator不动点算子来计算，例如

不同，虽然看上去很象，因为fact2 没有使用不动点，所以采用了一种比较原始的方式来达到递归的目的。

Haskell就是这种风格，但大多数语言，例如C/JAVA等，是严格的语言，也就是说函数参数必须要在函数调用前先求出来，也就是call by value的方式。

而且这个方法只适合无类型的语言，对于Ocaml这样的带类型的严格的语言，以上方法是无法行得通的。那么， Ocaml中的不动点算子如何做呢？

这个版本是无法跑通的，会出现堆栈溢出，因为fix f会无限展开。 要避免这个问题，

多了一个x，即可完全行得通，有点神奇。 因为改进版的fix带两个参数，不会针对第一个参数（fix f）一直展开，（因为这个参数（fix f），返回类型也是一个函数），所以能够求出阶乘。另外一个神奇的地方是factabs需要一个参数f，但是我们没有定义，实际上也没有用到，只是利用其作为函数类型调用（x-1）.

这个只是利用了带类型的不动点算子来计算递归，实际上不需要这么复杂，用本文开头提到的fact函数就可以。 但这个函数不是尾递归的，因为最后是乘法，不是函数调用，所以不能优化，所以需要改成尾递归版本，如下：

而c++/java目前还没有良好的闭包支持，所以如果要写类似的尾递归函数是很费劲的。

这里可以看出，闭包本质上是一个环境，并与函数计算绑定的计算环境。我们一般的函数调用是用堆栈来实现的，包括递归也是。 但是，采用闭包，我们可以使用堆来计算，而堆一般要比栈大很多，如果觉得函数递归层次太多，那么可以转化为闭包计算，也就是采用CPS风格。不但可以转化为尾递归，而且可以提供更大函数调用层次。 这也就是本文开头提到的为什么采用CPS风格的原因了。

身份认证 购VIP最低享 7

领优惠券(最高得80元）

本篇文章主要介绍了python使用递归、尾递归、循环三种方式实现斐波那契数列，非常具有实用价值，需要的朋友可以参考下

我要回帖

更多关于 c语言递归详解 的文章

 

随机推荐