- 注册时间
- 2006-6-19
- 最后登录
- 2010-1-23
⑥精研
- 积分
- 2223
|
发表于 2007-9-26 20:08:37
|
显示全部楼层
fib数列要递归做也没有必要用静态变量,除了那个数组外.如果只是为了输出而没有其它需求的话,那不用数组更好.说到底如果只要求一次fib数列的话最好不要递归,如果要多次求值且范围预先能估计到,那么最有效的方法是程序一开始就算一张表出来,后面运行时查表.
对应LZ的递归算法,应该这样才对:- /*
- * fib.c
- * 简单递归fibonacci数列算法演示
- */
- #include <stdio.h>
- int array[10] = { 0, 1 };
- int fib(int x) {
- switch (x) {
- case 0:
- return 0;
- case 1:
- return 1;
- default:
- array[x] = fib( x - 1 ) + fib( x - 2 );
- return array[x];
- /* basically you should just return the result
- instead of assigning the value into the array
- return fib( x - 1 ) + fib( x - 2 ); */
- }
- }
- void main() {
- int i;
- fib( 5 );
- for ( i = 0; i < 5; ++i ) {
- printf("%d ", array[i]);
- }
- }
复制代码
但实际上这么做效率很低,估计LZ只需要这样就行了:- /*
- * fib.c
- * 简单循环fibonacci数列算法演示
- */
- #include <stdio.h>
- int array[10] = { 0, 1 };
- void fib(int x) {
- int i;
- for ( i = 2; i < x; ++i ) {
- array[ i ] = array[ i - 1] + array[ i - 2];
- }
- }
- void main() {
- int i;
- fib( 5 );
- for ( i = 0; i < 5; ++i ) {
- printf("%d ", array[i]);
- }
- }
复制代码
尾递归是低效的,除非在特定的场景使用递归使语义特别清晰,否则还是避免使用尾递归的好.现代高级语言编译器一般会做尾递归消除的优化,但是不要太依赖这样的优化. |
|