现在的位置: 首页 > 综合 > 正文

尾递归

2017年08月21日 ⁄ 综合 ⁄ 共 879字 ⁄ 字号 评论关闭

尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数,如果在递归函数中,递归调用返回的结果总被直接返回,则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言,而且从编译器角度来说,亦容易优化成为普通循环。这是因为从电脑的基本面来说,所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递,就只需要叠套一个堆栈,因为电脑只需要将函数的参数改变再重新调用一次。利用尾部递归最主要的目的是要优化,例如在Scheme语言中,明确规定必须针对尾部递归作优化。可见尾部递归的作用,是非常依赖于具体实现的。

举个例子来说,阶乘的经典递归解法:

long FactorialCal( long x){
      if(x== 1 ) return x; 
      return FactorialCal(x- 1)* x;
} 

还可以怎么写呢?

long FactorialCal2( int x, int ncount, long lresult){
    if(x> ncount) return lresult; 
   return FactorialCal2(x+ 1, ncount, x* lresult);
}

FactorialCal2则是尾递归调用,因为这种调用总是在函数末尾执行,并且不会用到调用函数里的任何局部变量。所以有些编译器对此进行优化,在被调用函数执行时,直接利用调用函数的堆栈,不需要重新开辟堆栈空间,所以一般不会导致递归中出现的栈溢出。而一般递归因为调用过程中会存储局部变量,所以调用次数太多时就会发生溢出

还可以怎么写呢?

int FactorialTailRecursion(int n, int acc)
{
    if (n == 0) return acc;
    return FactorialTailRecursion(n - 1, acc * n);
}

由于递归在方法的末尾,因此方法中的局部变量已经毫无用处,编译器完全可以将其“复用”,并把尾递归优化为“循环”方式:(我们的确可以这样干)

int FactorialLoopOptimized(int n, int acc)
{
    while (true)
    {
        if (n == 0) return acc;

        acc *= n;
        n--;
    }
}

抱歉!评论已关闭.