详解斐波那契数列的递归与非递归实现（C语言版）

男娘i 2022-04-23 07:26 203阅读 0赞

1.斐波那契数列是什么：简单说，斐波那契数列就是一个数列从第3项开始，每一项都等于前两项之和。  
例子：0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…

2.非递归算法设计：采用for(当然while，do while也可以)循环，小编一开始定义的 数组大小为40，因此在for循环的时候将中止条件设置成了i<40(数组最后一个元素的下标为39)，因为斐波那契数列的前两项是给定的，因此for循环的开始条件自然就是i=2(即从第三项开始进行循环打印)，在最开始直接定义前两项的值并且将其打印出来。然后直接进入 for循环进行循环计算，每计算一次就进行一次元素的打印 **如果只是单纯的打印了0和1这两个数字，而没有进行数列前两项元素的定义的话会导致在第三项计算的时候出现严重的后果，以至于后面的计算全部出错。**  
*迭代函数部分*：代码中采用了标准库中的puts函数，对于只打印字符串来讲，用puts函数的话不需要在末尾加上换行符。\*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]

3.递归算法的设计：为了代码的简单起见 ，小编在自定义函数中直接利用了三目运算符（?:）来当做递归的基准条件，即就是当i<2的时候进行判断，如果i=0的话返回0，如果i=1的话返回1。因为**此自定义函数的返回值就是斐波那契数列对应的每一项**，因此在传入参数的时候直接把数列的项数传进去就ok了，主函数中用for循环来控制每一个项数的传入并在for循环中利用printf对自定义函数的返回值进行打印即可。

*递归调用的图形表示*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
*递归函数部分*  
![在这里插入图片描述][20190125145244431.png]

*整体代码及测试数据*  
\#include<stdio.h>  
\#define N 40 //宏定义来定义数组大小

int Fbi(int i)  // 斐波那契的递归函数 
        {
        	if( i < 2 )
        		return i == 0 ? 0 : 1;  
            return Fbi(i - 1) + Fbi(i - 2);  // 这里Fbi就是函数自己，等于在调用自己 
        }  
        
        int main()
        {
        	int i, a[N]; 
        	a[0] = 0;
        	a[1] = 1; 
        	puts("迭代显示斐波那契数列:");
        	printf("%d ", a[0]);  		//数列的第一项为0 
        	printf("%d ", a[1]);		//数列的第二项为1 
        	for(i = 2;i < N;i++)  
        	{ 
        		a[i] = a[i-1] + a[i-2];  
        		printf("%d ",a[i]);  
        	} 
        	printf("\n");
        	
        	puts("递归显示斐波那契数列:");
        	for(i = 0;i < N;i++)  
        		printf("%d ", Fbi(i));  
        
            return 0;
        }

![在这里插入图片描述][20190124235214292.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220323/4ac4b63cd7fd4115bc94c1bec5e58f1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20220323/56500039003b4cec90be32b39348ec57.png
[20190125145244431.png]: /images/20220323/eba81768c510436cb072c3360b6d17cb.png
[20190124235214292.png]: /images/20220323/07aaa0b0f9014289abfd5a11fe5bedf0.png