斐波那契数列的实现--递归和迭代法

习题 使用函数输出指定范围内的Fibonacci数 

本题要求实现一个计算Fibonacci数的简单函数，并利用其实现另一个函数，输出两正整数m和n（0<m≤n≤10000）之间的所有Fibonacci数。所谓Fibonacci数列就是满足任一项数字是前两项的和（最开始两项均定义为1）的数列。

函数接口定义：
int fib( int n ); void PrintFN( int m, int n );

其中函数fib须返回第n项Fibonacci数；函数PrintFN要在一行中输出给定范围[m,
n]内的所有Fibonacci数，相邻数字间有一个空格，行末不得有多余空格。如果给定区间内没有Fibonacci数，则输出一行“No Fibonacci
number”。

迭代法：使用循环结构
#include <stdio.h>   int fib( int n ); void PrintFN( int m, int n );   int
main() {     int m, n, t;       scanf("%d %d %d", &m, &n, &t);    
printf("fib(%d) = %d\n", t, fib(t));     PrintFN(m, n);       return 0; } int
fib( int n ) {     int front=1,back=1,sum=0;         if(n==1||n==2)        
return 1;     for(int i=3;i<=n;i++)     {         sum=front+back;        
front=back;      //相当于两个指针，往后移         back=sum;     }     return sum;    
 //若用递归，则很快：return fib(n-1)+fib(n-2) }      void PrintFN( int m, int n ) {    
int i=1;     int count=0;     while(fib(i)<=n)              
 //使用fib(i)判断可以大大减少检验的数      {         if(fib(i)>=m&&fib(i)<=n)               
  {             count++;             if(count==1)                
printf("%d",fib(i));             else                 printf(" %d",fib(i));    
    }            i++;     }          if(count==0)         printf("No Fibonacci
number\n"); }
递归法：
//省区main函数和print函数 int fib(int n) { /*if(n==0) return 0; else if(n==1) return
1; */ if(n<2) return n==0?0:1; return fib(n-1)+fib(n-2); }

时间复杂度：

总结：

对比两种实现斐波那契的代码----迭代法和递归法
两者的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更消晰、更简洁、更容易让人理解，从而减少读懂代码的时间。

但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

• « 上一篇：Hive常见面试题汇总
• » 下一篇：时间复杂度（详解）