尾递归浅析

2013-12-26

在学一些函数式语言的时候，经常遇到尾递归。总结一下:

什么是尾递归

递归是指一个函数直接或者间接调用其本身。递归会造成什么问题呢，每次函数调用，肯定需要一个方法栈来保存相关信息的。如果递归深度太深的话，必然导致栈溢出。举一个例子，斐波那契函数吧

public int fib(int n)
{
    if(n<2){
        return n;
    }
    return fib(n-1)+fib(n-2);
}

上面代码就是传统的递归.如果n太大，就可能导致栈溢出了。用尾递归来实现：

public int fib(int n,int acc1,int acc2)
{
    if(n==0) {
        return acc1;
    }
    return fib(n-1,acc2,acc1+acc2);
}

将单次计算的结果缓存起来，传递给下次调用，相当于自动累积。

很多人可能会有疑问，为什么尾递归也是递归，却不会造成栈溢出呢？因为编译器通常都会对尾递归进行优化。编译器会发现根本没有必要存储栈信息了，因而会在函数尾直接清空相关的栈。