尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

基本信息

中文名
尾递归
检测到时
它就覆盖当前的活动记录
而不是
在栈中去创建一个新的
编译器
可以做到这点

基本内容

尾递归 - Tail Recursion

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

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

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

以下是具体实例:

线性递归:

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

尾递归:

long TailRescuvie(long n, long a)
{
　　return(n == 1) ? a : TailRescuvie(n - 1, a * n);
}
　　long TailRescuvie(long n) 
　　{
　　    //封装用的
　　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}}}