我们看到的参考书中，当讲到递归时基本上都是使用“阶乘”和“斐波那契数列”来举例子，确实可以帮助我们了解递归，但却导致我们在平时编写类似程序时，总是使用递归来实现。那么在实际项目中，使用递归来实现到底是否合适？答案是否定 的。
《C和指针》的作者Kenneth A. Reek说，他认为这是很不幸的：“计算阶乘时不能提供任何优越之处；在斐波那契数列中，使用递归效率非常非常低”。 尤其对于计算斐波那契数，使用递归和使用迭代的效率有可能相差几十万倍，下面有代码分析。
1.1 “尾部递归”可以使用“迭代”来替换。 学过数据结构之后，对这个应该不陌生。
1.2 递归 的优点在于易于理解 ；迭代 的优点在于效率高 。如何选择取决于你在“易于理解”和“效率”中如何作出权衡。
递归 函数调用涉及一些运行时开销，包括参数必须压到堆栈中、为局部变量分配内存、寄存器的值必须保存等等，并且在每次调用返回时，上述保存操作必须还原，恢复成调用前的样子。迭代 的实现方式开销显然要小。所以在可理解性相差不大的情况下，为了保证效率应该优先选择迭代 。
阶乘的一种定义方式为：
F(n) = 1 当 n<=0 F(n) = n * F(n-1) 当n>02.1 递归实现
实现代码如下 ：
/* 利用 递归 来计算整数n的阶乘 */ long factorial_recursion( int n ){ if( n<=0 ){ return 1; }else{ return n*factorial_recutsion( n-1 ); } }很明显是“尾部递归”，所以我们可以很轻松的改写为“迭代”的形式。
2.2 迭代实现
迭代实现代码如下 ：
/* 利用 迭代 来计算整数n的阶乘 */ long factorial_iteration( int n ){ int result = 1; while( n>1 ){ result *=n; n--; } return result; }2.3 两种方式的比较
很明显，两种实现方式都非常简单易懂，在实际项目中，为了效率，应该优先选择 迭代 。
斐波那契数列中的每个数，都是它前面两个数的和。其计算公式如下：
F(0) = 0 F(1) = 1 F(n)= F(n-1) + F(n-2)3.1 递归实现
递归实现代码如下 ：
/* 计算斐波那契数列的第num个数 */ int fibonacci_count( int num ){ if( num<=2 ){ return 1; }else{ return fibonacci_count(num-1) + fibonacci_count(num-2); } }3.2 迭代实现
迭代实现代码如下 ：
/* 利用 迭代 计算 斐波那契数 其形式为： 1, 1, 2, 3, 5, 8, 13, 21, 34 … */ long fibonacci(int n){ long result; long previous; long next; result = previous = 1; if(n<=2){ return 1; } int i =3; /* 用于计算已经计算到第几个 */ while( i<=n ){ next = result; result = previous + next; previous = next; i++; } return result; }3.3 两种方式比较
下面一个程序反映了，利用递归方式计算斐波那契函数时，调用fibonacci函数的次数，以及计算fibonacci(3)的次数。
#include <stdio.h> #include <stdlib.h> int fibonacci_count( int num ); long count; /* 用来记录斐波那契数列中计算调用 fibonacci_rec_count函数 的次数 */ int num_three; /* 计算 fibonacci_rec_count(3)的次数 */ int main(){ printf("Fibonacci(num)/t/tNumber of Calls/t/tnumbers of Call fibonacci_rec_count(3) /n"); int i; for( i=1; i<=30; i++ ){ int result = fibonacci_rec_count(i); printf("num: %d/t/t/tcount: %ld /t/t%d/n", i, count, num_three); count = 0; num_three = 0; } getchar(); return EXIT_SUCCESS; } /* 计算斐波那契数列的第num个数 */ int fibonacci_rec_count( int num ){ count++; /* 每调用一次fibonacci_rec_count函数，count的值便加1 */ if( num==3 ){ num_three++; } if( num<=2 ){ return 1; }else{ return fibonacci_rec_count(num-1) + fibonacci_rec_count(num-2); } }运行结果为：
Fibonacci(num) Number of Calls numbers of fibonacci(3) num: 1 count: 1 0 num: 2 count: 1 0 num: 3 count: 3 1 num: 4 count: 5 1 num: 5 count: 9 2 num: 6 count: 15 3 num: 7 count: 25 5 num: 8 count: 41 8 num: 9 count: 67 13 num: 10 count: 109 21 num: 11 count: 177 34 num: 12 count: 287 55 num: 13 count: 465 89 num: 14 count: 753 144 num: 15 count: 1219 233 num: 16 count: 1973 377 num: 17 count: 3193 610 num: 18 count: 5167 987 num: 19 count: 8361 1597 num: 20 count: 13529 2584 num: 21 count: 21891 4181 num: 22 count: 35421 6765 num: 23 count: 57313 10946 num: 24 count: 92735 17711 num: 25 count: 150049 28657 num: 26 count: 242785 46368 num: 27 count: 392835 75025 num: 28 count: 635621 121393 num: 29 count: 1028457 196418 num: 30 count: 1664079 317811在递归实现方式中，每次递归调用都会触发另外两个递归调用，而且这两个调用的任何一个又会触发两个递归调用，依次越来越多。冗余的计算增长迅速。例如：在 计算fibonacci(10) 时，fibonacci(3)被计算了21次；但在计算fibonacci(30) 时，fibonacci(3)被计算了 317811 次；这 317811 次计算结果完全一样，除了一次有用外，其余都是浪费。
