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

小鱼儿 2023-01-23 10:57 29阅读 0赞

**习题 使用函数输出指定范围内的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);
    
    
    }

###  ###

### 时间复杂度： ###

![20210715092823392.png][]

`总结：`

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

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

[20210715092823392.png]: /images/20221004/612a30f06ce740558cf4ef65508752c6.png