在前面的学习，我们知道普通递归和尾递归的区别，而且在有些语言里是极力提倡尾递归的，如erlang，因为编译器会对其进行优化，不会因为递归次数的增加给函数栈带来巨大的开销。但是c++语言中，g++会对其进行优化吗？现在通过实例分析，看看结论会是什么？
斐波那契数列： 1，1，2，3，5，......
通过c++编程来求
斐波那契数列的第N项的值。试用两种方法，一种是普通递归，另一种是尾递归。
然后统计他们计算第N项的值所花费的时间，来比较两者间的效率。
#include <iostream>
#include <ctime>
using namespace std;
// Normal recusion for fibonacci
unsigned int fib_normal_rec(unsigned int n)
{
if (n <= 2)
return 1;
else
return fib_normal_rec(n-1) + fib_normal_rec(n-2);
}
// Rail recusion for fibonacci
unsigned int fib_rail_rec(unsigned int n, unsigned int first, unsigned int second)
{
if (n == 1) return first;
if (n == 2) return second;
return fib_rail_rec(n-1, second, second+first);
}
unsigned int fib_rail_rec(unsigned int n)
{
return fib_rail_rec(n, 1, 1);
}
// No recusion
unsigned int fib_no_rec(unsigned int n)
{
if (n <= 2)
return 1;
unsigned int x=1, y=1, y_tmp=0;
for (unsigned int i=0; i<n-2; i++)
{
y_tmp = y;
y = x+y;
x = y_tmp;
}
return y;
}
int main()
{
// fib NUM
unsigned int fib_num = 10000000000;
unsigned int t1 = time(NULL);
//cout <<"Normal fib:" << fib_num << " --> " << fib_normal_rec(fib_num) << endl;
unsigned int t2 = time(NULL);
cout << "Normal fib time cost:" << t2-t1 << endl;
cout << "----------------------------------------------------------" << endl;
//cout <<"Rail fib:" << fib_num << " --> " << fib_rail_rec(fib_num) << endl;
unsigned int t3 = time(NULL);
cout << "Rail fib time cost:" << t3-t2 << endl;
cout << "---------------------------------------------------------" << endl;
cout <<"No recusion fib:" << fib_num << " --> " << fib_no_rec(fib_num) << endl;
unsigned int t4 = time(NULL);
cout << "No recusion fib time cost:" << t4-t3 << endl;
return 0;
}
经过反复加注释编译，设置fib_num的大小，最后得出如下测试结果：
非尾递归：当fib_num=45，花费8秒左右得到正确值。
当fib_num设置成50时，运行时间有点长，就没继续等下去了。
尾递归：当fib_num=
100000时，0秒得到正确值。
当fib_num=1000000时，0秒得到段错误。
循环： 当fib_num=100000000 时，0秒得到正确值。
当fib_num=1000000000 时，4秒得到正确值。
当fib_num=10000000000 时，编译会出警告：
recursion.cpp: In function 'int main()':
recursion.cpp:45:
warning:
large integer implicitly truncated to unsigned type
个人得出的结论：
尾递归和循环的执行效率都非常高。但是尾递归的递归层数大到一定程度会出现段错误。
尾递归的函数栈开销比普通递归要小的多，执行效率也要大很多。
但是并不是说尾递归就没有函数栈开销。
正因为尾递归具有函数栈开销，其计算极限要比非递归（循环）小很多。
总之：如果只考虑计算能力，
实现一个功能，能不用递归就别用递归，能用尾递归就别用非尾递归。
