中企动力网站建设方案,设计公司名字创意,手机移动开发技术,appapp下载安装官方免费下载原文#xff1a;尾递归_百度百科
尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾#xff0c;我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时#xff0c;这个递归调用就是尾递归。尾递归函数的特点…原文尾递归_百度百科
尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作这个特性很重要因为大多数现代的编译器会利用这种特点自动生成优化的代码。
目录
1 原理2 实例原理
当编译器检测到一个函数调用是尾递归的时候它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点因为递归调用是当前活跃期内最后一条待执行的语句于是当这个调用返回时栈帧中并没有其他事情可做因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个这样所使用的栈空间就大大缩减了这使得实际的运行效率会变得更高。 实例
为了理解尾递归是如何工作的让我们再次以递归的形式计算阶乘。首先这可以很容易让我们理解为什么之前所定义的递归不是尾递归。回忆之前对计算n!的定义在每个活跃期计算n倍的(n1)!的值让nn1并持续这个过程直到n1为止。这种定义不是尾递归的因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。现在让我们考虑以尾递归的形式来定义计算n!的过 [1] 程。
这种定义还需要接受第二个参数a除此之外并没有太大区别。a初始化为1维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而在每次递归调用中令ana并且nn1。继续递归调用直到n1这满足结束条件此时直接返回a即可。
代码实例3-2给出了一个C函数facttail它接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数aa的初始值为1。facttail使用a来维护递归层次的深度除此之外它和fact很相似。读者可以注意一下函数的具体实现和尾递归定义的相似之处。
示例3-2以尾递归的形式计算阶乘的一个函数实现 [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 /*facttail.c*/ #includefacttail.h /*facttail*/ int facttail(int n, int a) { /*Compute a factorialina tail - recursive manner.*/ if (n 0) return 0; else if (n 0) return 1; else if (n 1) return a; else return facttail(n - 1, n * a); }
示例3-2中的函数是尾递归的因为对facttail的单次递归调用是函数返回前最后执行的一条语句。在facttail中碰巧最后一条语句也是对facttail的调用但这并不是必需的。换句话说在递归调用之后还可以有其他的语句执行只是它们只能在递归调用没有执行时才可以执行 [1] 。
尾递归是极其重要的不用尾递归函数的堆栈耗用难以估量需要保存很多中间函数的堆栈。比如f(n, sum) f(n-1) value(n) sum; 会保存n个函数调用堆栈而使用尾递归f(n, sum) f(n-1, sumvalue(n)); 这样则只保留后一个函数堆栈即可之前的可优化删去。
也许在C语言中有很多的特例但编程语言不只有C语言在函数式语言Erlang中亦是栈语言如果想要保持语言的高并发特性就必须用尾递归来替代传统的递归。
原文的说法是错误的原文如下
一种算法, 用于计算机编程技术.
尾递归是针对传统的递归算法而言的, 传统的递归算法在很多时候被视为洪水猛兽. 它的名声狼籍, 好像永远和低效联系在一起.
尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.
以下是具体实例:
线性递归: 1 2 3 4 5 long Rescuvie(long n) { return (n 1) ? 1 : n * Rescuvie(n - 1); }
尾递归: 1 2 3 4 5 6 7 8 9 10 11 12 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}}}
{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保存.
