尾递归探讨

earthengine

本文参考了如下帖子：http://topic.csdn.net/u/20071023 ... e-b2fb38fb0c38.html

递归我们都知道，就是在一个程序内部调用自身，就形成了递归。在实际情况里，不管是什么语言编写的程序，递归的程序执行时会反复在堆栈里创建局部变量框架。当递归深度很大的时候甚至能造成堆栈溢出。因此，递归往往是优化的重点。

但是，递归无疑能带来理解上的好处。如果不用递归，一般会用循环来改写。但这样一来，很多情况下代码的可读性会降低。

为此，尾递归诞生了。什么叫尾递归呢？如果一个递归程序只在最后的步骤调用自身，那么最后这个步骤可以直接返回给最初的调用者，而无须返回给上一级调用者。这就叫尾递归。

下面我们拿最常见的例子，计算阶乘n!的算法来分析，这里不用任何语言，只用中文写伪代码（类python）。

函数 阶乘 对给出的 整数 n
    如 n <= 0 返回 1
    否则 返回 n * 阶乘(n-1)


这个看起来像是尾递归，因为递归调用发生在计算(n-1)!时，而这好像是最后一步。但这对吗？不对。因为如果我们把上面的算法拆到最简单的操作，是这样的：

函数 阶乘 对给出的 整数 n
    如  n <= 0 返回 1
    否则
        计算 n - 1 保存到 寄存器0
        计算 阶乘(寄存器0) 保存到 寄存器1
        计算 n * 寄存器1 保存到 寄存器2
        返回 寄存器2

这样我们知道，递归的步骤其实并不是最后的步骤。那么要怎么样才能把它变成尾递归呢？

分析上面的程序，我们看出，妨碍以上程序成为尾递归的原因主要是调用完递归函数之后还要做一次乘法。如果能把乘法的动作移到前面，就能使递归动作发生在最后。但是，我们又需要知道两个乘数，才能完成这个乘法。

解决的思路，是另写一个帮助函数

函数 阶乘1 对给出的 整数 n 及 整数 m
    如 n<=0 返回 m
    否则 返回 阶乘1(n-1, m*n)

然后我们需要的阶乘函数可以写成

函数 阶乘 对给出的 整数 n
    返回 阶乘1(n,1)

你可以验证，这里的阶乘1这个函数的递归动作确实是发生在最后一步。

预告：下一次我们要来看看更复杂的斐波那契数列Fab(n)=Fab(n-1)+Fab(n-2)是怎么尾递归化的。

someonehappy

是我的思维比较怪么？

对这段文章的理解，最大的难点在那个阶乘１函数上面。似乎很不直观。

难道类似文章说的，递归带来程序编写和理解上的便利，但是为了解决因此带来的性能上的问题，最后的解决方法却又部分丢失了递归的这一优点，难以两全么？

coredump

尾递归版的阶乘只是把那个乘法的结果放在函数参数里，非尾递归的是放在函数本地堆栈里，仅此而已。

其实光把程序写成尾递归形式并不意味着就一定能够获得更好的性能了，还得有一个消除尾递归(TRE Tail Recursion Elimination)的过程，不过这个过程一般而言是由编译器来完成了。在《形式语言和自动机》这门计算机课程中，消除尾递归一般是一个经常用来做练习和考试题目的。所以，程序员们就尽量把递归弄成尾递归的形式，编译器开发者就研究怎么消除尾递归，使尾递归变成非递归。看看这个Python的作者的TRE的BLOG:http://neopythonic.blogspot.com/ ... on-elimination.html . 更聪明的编译器甚至能对某些非尾递归的程序自动转成尾递归，这样就又可以省掉程序员的麻烦了。不过，不是所有递归调用都能这么顺顺当当地，一目了然地 转成尾递归的。

earthengine

现在，我们想要写另一个函数，来计算有名的斐波那契数列。这个数列的一般递归定义是：

函数 Feb 对给出的 整数 n
     如果 n<2 返回1
     否则 返回 Feb(n-1) + Feb(n-2)

乍一看，这个函数似乎没有办法变成尾递归的。因为尾递归要求最后一步才调用自己，这意味着只能调用一次自己。但是上面的定义中，调用了两次自己。

不过，这只是假象。我们可以想象，虽然每次用较大的参数调用这个函数时，都要调用两次自己，但是我们可以让这些步骤一步一步来：
Feb(n) = Feb(n-1)+Feb(n-2)=(Feb(n-2)+Feb(n-3))+Feb(n-2)= 2*Feb(n-2) + Feb(n-3) = 2*(Feb(n-3)+Feb(n-4)) + Feb(n-3) ........

要彻底尾递归化，我们要把上述过程进行到底：

函数 Feb1 对给出的 整数 n, 整数a 和 整数 b
     如 n=0  返回 a
    否则 返回 Feb1(n-1, a+b, a)

要理解这个函数，可以想象，如果按照上面的展开过程，对Feb(m)展开到第n步时的式子是这样的：
Feb(m) = a*Feb(m-n) + b*Feb(m-n-1)
       = a*(Feb(m-n-1)+Feb(m-n-2)) + b*Feb(m-n-1)
       = (a+b)*Feb(m-n-1) + a*Feb(m-n-2)

这个时候，就可以给出尾递归版本的Feb函数了：

函数 Feb 对给出的 整数 n
     返回 Feb1(n,1,0)

可能有人要问，为什么是Feb(n,1,0)不是Feb(n,1,1)呢？这只要验证一下就够了：
Feb1(0,1,0) = 1
Feb1(1,1,0) = Feb1(0,1,1) = 1
Feb1(2,1,0) = Feb1(1,1,1) = Feb1(0,2,1) = 2
......

[ 本帖最后由 earthengine 于 20-8-2009 13:55 编辑 ]

kaile

好文，学习中

koumei

这是教程吗？

earthengine

原帖由 koumei 于 22-8-2009 23:33 发表

                               
登录/注册后可看大图

这是教程吗？

不算吧，只是一个简单介绍。可以理解为wiki词条。

someonehappy

还是觉得，如果用递归本来主要的目的就是为了简化程序的设计，方便代码的理解和维护，那么这个尾递归化就有点得不偿失了，因为两个例子里面都为了尾递归化而放弃了原始目的。

不过在确实要讲究性能的地方，确实值得一用。

yuba

有道理

讲究性能的话千万不要考虑递归

earthengine

原帖由 someonehappy 于 24-8-2009 09:14 发表

                               
登录/注册后可看大图

还是觉得，如果用递归本来主要的目的就是为了简化程序的设计，方便代码的理解和维护，那么这个尾递归化就有点得不偿失了，因为两个例子里面都为了尾递归化而放弃了原始目的。

不过在确实要讲究性能的地方，确实值 ...

这是本文的目的之一。讨论尾递归化的目的，是为了改进编译器和自动工具。如果自动工具能够自动把非尾递归的算法优化成尾递归算法，那么就可以同时达到方便代码理解和维护以及执行上的优化这两个目的了。

就以上两个例子来看，能不能抽象出一些共性？能不能开发出自动尾递归化的算法呢呢？

coredump

简单的递归可以转成非尾递归，要点就是把递归体中的临时变量(递归堆栈中的主要内容)，转变成递归函数的参数。

uni

以前公司明令要求不允许使用递归 。 所以把递归给戒了。