int factorial(int n)
{
if(n==0)
return 1;
else
return n*factorial(n-1);
} 在上述的函数中，返回的值并不是一个完全独立的状态，而需要保存n这样一种额外需维护的变量，每层递归都需要这样一个变量，那么在下次调用的时候，就会重新创建新的栈帧来进行保存。每次都是这样。所以对于大数而言，就可能溢出了。那么仔细观察这种递归的本质，就是因为创建了很多中间过程需要存储，才导致了这样一种空间的浪费。那么我们在设计递归函数的时候，能不能直接省略中间变量，直接返回结果呢？下面就是尾递归的设计思路了。int factorial_tailcursion(int n,int acc)
{
if(n==0)
return acc;
else
return factorial_tailcursion(n-1,acc*n);
}
在调用的时候 factorial_tailcursion(n,1) 需要一个初始累计器acc=1。可以看出，在每次调用完毕尾递归形式的阶乘函数后，根本没有产生人中间过程，中间变量都通过参数传递给下一次调用。从而节省了栈的开销。因为对于某些编译器而言，会自动识别到这一动作，并且认为每次调用过程都是独立的，那么就不需要每次都开辟新的 栈帧来保存当前值，而是直接就地覆盖调之前的栈。那么其空间复杂度将为O(1)。这就是尾递归的本质。说白了，也就是在进行递归设计的时候，尽量省略中间过程。/***********************************************************************
two examples of tail recursion
1. factorial
2. fibonacci
*********************************************************************/
#include <iostream>
using namespace std;
int factorial(int n) // usual recursion call
{
if(n==0)
return 1;
else
return n*factorial(n-1);
}
int factorial_tailrecursion(int n,int acc) // tail recursion call
{
if(n==0)
return acc;
else
return factorial_tailrecursion(n-1,acc*n);
}
int fibinacci(int n)
{
if(n<2)
return n;
else
return fibinacci(n-1)+fibinacci(n-2);
}
int fibinacci_tailrecursion(int n,int acc1,int acc2)
{
if(n==0)
return acc1;
else
return fibinacci_tailrecursion(n-1,acc1+acc2,acc1);
}
int main()
{
puts("usual factor recursion 4!");
cout<<factorial(4)<<endl;
puts("tail recursion 4!");
cout<<factorial_tailrecursion(4,1)<<endl;
puts("usual fibinacc ");
for(int i=0;i<10;i++)
cout<<fibinacci(i)<<" ";
cout<<endl;
puts("tail recursion ");
for(int i=0;i<10;i++)
cout<<fibinacci_tailrecursion(i,0,1)<<" ";
return 0;
}
小结：
递归函数的使用，无疑对一些复杂的问题，可以清晰的反应其本质，使得易于理解。everything is banlance！有利必有弊，我们必须尽量减少这中弊。
尾递归(tail recursion) 的简单使用,布布扣,bubuko.com
原文：http://blog.csdn.net/lynnbest/article/details/22917517