欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言用递归求斐波那契数,让你发现递归的缺陷和效率瓶颈

程序员文章站 2022-07-04 11:49:18
递归是一种强有力的技巧,但和其他技巧一样,它也可能被误用。 一般需要递归解决的问题有两个特点: 存在限制条件,当符合这个条件时递归便不再继续;每次递归调用之后越来越接近...

递归是一种强有力的技巧,但和其他技巧一样,它也可能被误用。

一般需要递归解决的问题有两个特点:


存在限制条件,当符合这个条件时递归便不再继续;每次递归调用之后越来越接近这个限制条件。
递归使用最常见的一个例子就是求阶乘,具体描述和代码请看这里:c语言递归和迭代法求阶乘

但是,递归函数调用将涉及一些运行时开销——参数必须压到堆栈中,为局部变量分配内存空间(所有递归均如此,并非特指求阶乘这个例子),寄存器的值必须保存等。当递归函数的每次调用返回时,上述这些操作必须还原,恢复成原来的样子。所以, 基于这些开销,对于递归求阶乘而言,它并没有简化问题的解决方案。

迭代求阶乘使用简单循环的程序,看上去不甚符合前面阶乘的数学定义,但它却能更为有效地计算出结果。如果你仔细观察递归函数,你会发现递归调用是函数所执行的最后一项任务。这个函数是尾部递归(tail recursion)的一个例子。由于函数在递归调用返回之后不再执行任何任务,所以尾部递归可以很方便地转换成一个简单循环,完成相同的任务。

提示:许多问题是以递归的形式进行解释的,这只是因为它比非递归形式更为清晰。但是,这些问题的迭代实现往往比递归实现效率更高,虽然代码的可读性可能稍差一些,当一个问题相当复杂,难以用迭代形式实现时,此时递归实现的简洁性便可以补偿它所带来的运行时开销。

这里有一个更为极端的例子,菲波那契数就是一个数列,数列中每个数的值就是它前面两个数的和。 这种关系常常用递归的形式进行描述:
C语言用递归求斐波那契数,让你发现递归的缺陷和效率瓶颈

同样,这种递归形式的定义容易诱导人们使用递归形式来解决问题。这里有一个陷牌:它使用递归步骤计算fibonacci(n-1)和fibonacci(n-2)。但是,在计算fibonacci(n-1)时也将计算fibonacci(n-2)。这个额外的计算代价有多大呢?

答案是,它的代价远远不止一个冗余计算:每个递归调用都触发另外两个递归调用,而这两个调用的任何一个还将触发两个递归调用,再接下去的调用也是如此。这样,冗余计算的数量增长得非常快。例如,在递归计算fibonacci(10)时,fibonacci(3)的值被计算了21次。但是,在递归计算 fibonacci(30)时,fibonacci(3)的值被计算了317811次。当然,这317811次计算所产生的结果是完全一样的,除了其中之一外,其余的纯属浪费。这个额外的开销真是相当恐怖!

如果使用一个简单循环来代替递归,这个循环的形式肯定不如递归形式符合前面菲波那契数的抽象定义,但它的效率提高了几十万倍!

当你使用递归方式实现一个函数之前,先问问你自己使用递归带来的好处是否抵得上它的代价。 而且你必须小心:这个代价可能比初看上去要大得多。

不信请看下面的代码,分别用递归和迭代计算斐波那契数,效率差距真是大的惊人。

运行结果:
result of recursion: 1134903170
time: 7.494000 seconds
---------------------------------------
result of iteration: 1134903170
time: 0.000000 seconds

注意:上面的程序最好在gcc(linux下的gcc或windows下的code:blocks)下运行,vc下可能统计不到运行时间。

看吧,用递归花了将近7.5秒的时间,但是用迭代几乎不费吹灰之力,效率快到统计不到运行时间。
  1. #include
  2. #include
  3. #include
  4.  
  5. // 递归计算斐波那契数
  6. long fibonacci_recursion( int n )
  7. {
  8. if( n <= 2 )
  9. return 1;
  10.  
  11. return fibonacci_recursion(n-1) + fibonacci_recursion(n-2);
  12. }
  13.  
  14. // 迭代计算斐波那契数
  15. long fibonacci_iteration( int n )
  16. {
  17. long result;
  18. long previous_result;
  19. long next_older_result;
  20.  
  21. result = previous_result = 1;
  22.  
  23. while( n > 2 ){
  24. n -= 1;
  25. next_older_result = previous_result;
  26. previous_result = result;
  27. result = previous_result + next_older_result;
  28. }
  29. return result;
  30. }
  31.  
  32. int main(){
  33. int n = 45;
  34.  
  35. // 递归消耗的时间
  36. clock_t recursion_start_time = clock();
  37. long result_recursion = fibonacci_recursion(n);
  38. clock_t recursion_end_time = clock();
  39.  
  40. // 迭代消耗的时间
  41. clock_t iteration_start_time = clock();
  42. long result_iteration = fibonacci_iteration(n);
  43. clock_t iteration_end_time = clock();
  44.  
  45. // 输出递归消耗的时间
  46. printf("result of recursion: %ld \ntime: %fseconds",
  47. fibonacci_recursion(n),
  48. (double)(recursion_end_time-recursion_start_time)/clocks_per_sec
  49. );
  50. printf("\n-----------------------\n");
  51. // 输出迭代消耗的时间
  52. printf("result of iteration: %ld \ntime: %fseconds",
  53. fibonacci_iteration(n),
  54. (double)(iteration_end_time-iteration_start_time)/clocks_per_sec
  55. );
  56.  
  57. return 0;
  58. }