注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C语言以尾递归的形式计算阶乘的一个函数实现

OC/C/C++ 水墨上仙 2866次浏览 已收录 手机上查看

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

当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。因此,只要有可能我们就需要将递归函数写成尾递归的形式。

为了理解尾递归是如何工作的,让我们再次以递归的形式计算阶乘。首先,这可以很容易让我们理解为什么之前所定义的递归不是尾递归。回忆之前对计算n!的定义:在每个活跃期计算n倍的(n-1)!的值,让n=n-1并持续这个过程直到n=1为止。这种定义不是尾递归的,因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值,因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。现在让我们考虑以尾递归的形式来定义计算n!的过程。

这种定义还需要接受第二个参数a,除此之外并没有太大区别。a(初始化为1)维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而,在每次递归调用中,令a=na并且n=n-1。继续递归调用,直到n=1,这满足结束条件,此时直接返回a即可。

代码实例3-2给出了一个C函数facttail,它接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数a,a的初始值为1。facttail使用a来维护递归层次的深度,除此之外它和fact很相似。读者可以注意一下函数的具体实现和尾递归定义的相似之处。

代码和说明来自百度百科

/* facttail.c */
#include "facttail.h"
/* facttail  */
 
int facttail(int n, int a) 
{
    /* Compute a factorial in a 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);
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C语言以尾递归的形式计算阶乘的一个函数实现
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……