尾递归 - Tail Recursion

一种算法,用于计算机编程技术.

尾递归是针对传统的递归算法而言的,传统的递归算法在很多时候被视为洪水猛兽.它的名声狼籍,好像永远和低效联系在一起.

尾递归就是从最后开始计算,每递归一次就算出相应的结果,也就是说,函数调用出现在调用者函数的尾部,因为是尾部,所以根本没有必要去保存任何局部变量.直接让被调用的函数返回时越过调用者,返回到调用者的调用者去.

以下是具体实例:

线性递归:

longRescuvie(longn){

return(n==1)?1:n*Rescuvie(n-1);

}

尾递归:

longTailRescuvie(longn,longa){

return(n==1)?a:TailRescuvie(n-1,a*n);

}

longTailRescuvie(longn){//封装用的

return(n==0)?1:TailRescuvie(n,1);

}

当n=5时

对于线性递归,他的递归过程如下:

Rescuvie(5)

{5*Rescuvie(4)}

{5*{4*Rescuvie(3)}}

{5*{4*{3*Rescuvie(2)}}}

{5*{4*{3*{2*Rescuvie(1)}}}}

{5*{4*{3*{2*1}}}}

{5*{4*{3*2}}}

{5*{4*6}}

{5*24}

120

对于尾递归,他的递归过程如下:

TailRescuvie(5)

TailRescuvie(5,1)

TailRescuvie(4,5)

TailRescuvie(3,20)

TailRescuvie(2,60)

TailRescuvie(1,120)

120

很容易看出,普通的线性递归比尾递归更加消耗资源,在实现上说,每次重复的过程

调用都使得调用链条不断加长.系统不得不使用栈进行数据保存和恢复.而尾递归就

不存在这样的问题,因为他的状态完全由n和a保存.

//

首先：尾递归是线性递归的子集，属于线性递归。具体概念请参阅各大高校出版的书籍。作者把概念搞错了

其次，上文所举的第二个例子中在TailRescuvie(n-1,1)没有计算出来之前，是不能return的。也就是说递归过程和第一个例子是差不多的，根本没有节约资源，甚至更浪费。

其实，编译器会很容易的对尾递归使用跳转语句进行优化，其实是可以return的。