递归——斐波那契数列多种求解方法

刺骨的言语ヽ痛彻心扉 2022-12-23 03:23 134阅读 0赞

## 斐波那契数列 ##

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：  
0、1、1、2、3、5、8、13、21、34、……  
在数学上，斐波那契数列以如下被以递推的方法定义：  
F(0)=0，  
F(1)=1,  
F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N\*）  
在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

## **用循环法：** ##

#define _CRT_SECURE_NO_WARNINGS 1
    //构建斐波那契数列
    //{0,1,1,2,3,5,8,13,...}即：F(n=F(n-1)+F(n-2）
    //循环法
    #include<stdio.h>
    int main()
    { 
    	int n = 0;
    	int a = 0;
    	int c = 0;
    	printf("请输入你要输出第几个斐波那契数(大于0)：\n");
    	scanf("%d", &n);
    	if (n < 0)
    	{ 
    		printf("请输入一个大于1的数\n");
    	}
    	else if (n==1)
    	{ 
    		a = 0;
    		printf("斐波那契数为：%d\n", a);
    	}
    	else if (n == 2)
    	{ 
    		a = 1;
    		printf("斐波那契数为：%d\n", a);
    	}
    	else
    	{ 
    		int a = 0;
    		int b = 1;
    		
    		while (n > 2)
    		{ 			
    			c = a + b;
    			a = b;
    			b = c;	
    			n--;
    		}		
    	}
    	printf("斐波那契数为：%d\n", c);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center]

## **用函数的方法：** ##

### 非递归方式 ###

//非递归的方法求斐波那契数列
    #include<stdio.h>
    int Fib(int x)
    { 
    	if (x == 1)//当x等于1时候，直接返回0
    		return 0;
    	else if (x == 2)//当x等于2时候，直接返回1
    		return 1;
    	else
    	{ 
    		int first = 0;//定义第1个斐波那契数为0
    		int second = 1;//定义第2个斐波那契数为0
    		int ret = 0;//定义一个整形接收值
    		while (x>2)//当x大于2的时候进入循环
    		{ 
    			ret = first + second;
    			first= second;
    			second = ret;
    			x--;
    		}
    		return ret;//返回ret的值
    	}		
    }
    int main()
    { 
    	int n = 0;
    	
    	printf("请输入你要输出第几个斐波那契数(大于0)：\n");
    	scanf("%d", &n);
    	if (n > 0)
    	{ 
    		printf("第%d个斐波那契数为：%d\n",n, Fib(n));
    	}
    	else
    	{ 
    		printf("请输入一个大于1的数\n");
    	}	
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 1]

### 递归方式 ###

//递归的方法求斐波那契数列
    #include<stdio.h>
    int Fib(int x)
    { 
    	if (x == 1)
    	{ 
    		return 0;//第一个斐波那契数为0
    	}
    		
    	else if (x == 2)
    	{ 
    		return 1;//第二个斐波那契数为1
    	}	
    	else
    	{ 
    		return Fib(x - 1) + Fib(x - 2);//从第三个数开始就回去找Fib（2）和Fib（1）
    		                               //不断回去找直到找到为止
    	}	
    }
    int main()
    { 
    	int n = 0;
    	printf("请输入你要输出第几个斐波那契数(大于0)：\n");
    	scanf("%d", &n);
    	if (n > 0)
    		{ 
    			printf("第%d个斐波那契数为：%d\n",n, Fib(n));
    		}
    		else
    		{ 
    			printf("请输入一个大于1的数\n");
    		}	
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 2]

## 求斐波那契数列前几项的和 ##

代码1：

#include<stdio.h>
    int FibSum(int x)
    { 
    	if (x == 1)//前1项的和为0
    	{ 
    		return 0;
    	}
    	else if (x == 2)//前2项的和为1
    	{ 
    		return  1;
    	}
    	else
    	{ 
    		int first = 0;
    		int second = 1;
    		int sum = 1;//从第3项开始计算和，没有加前两项的和，所以sum初始化为1
    		int ret = 0;
    		while (x > 2)
    		{ 
    			ret = first + second;
    			first = second;
    			second = ret;
    			sum += ret;//每次求出的斐波那契数加在sum上
    			x--;
    		}
    		return sum;
    	}
    }
    int main()
    { 
    	int  n = 0;
    	printf("请输入你要求前几项的和：\n");
    	scanf("%d", &n);
    	if (n > 0)
    	{ 
    		printf("前%d项斐波那契数的和为：%d\n",n,FibSum(n));
    	}
    	else
    	{ 
    		printf("请输入一个大于0的数\n");
    	}
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 3]  
代码2：

//求菲波那切数列前几项的和
    //递归方法
    #include<stdio.h>
    int Fib(int x)
    { 
    	if (x == 1)
    	{ 
    		return 0;
    	}
    	else if (x == 2)
    	{ 
    		return 1;
    	}
    	else
    	{ 
    		return  Fib(x-1) + Fib(x - 2);
    		
    	}
    
    }
    int main()
    { 
    	int  n = 0;
    	printf("请输入你要求前几项的和：\n");
    	scanf("%d", &n);
    	if (n > 0)
    	{ 
    		int sum = 0;
    		for (int i = 1; i <= n; i++)//利用for循环求和
    		{ 
    			sum += Fib(i);
    
    		}
    		printf("前%d项斐波那契数的和为：%d\n", n,sum );
    	}
    	else
    	{ 
    		printf("请输入一个大于0的数\n");
    	}
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 4]  
总结：  
如果所求的斐波那契数或前n项和数字比较小的话，可能使用递归和不使用区别不大，但是当数字特别大的时候，使用递归的话，速度会非常慢，因为做了很多的重复计算（因为要不停的回去找前面的数）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/b580181dd5f446ee99f825f673790ff3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/8a898635ea674525b59a55649022c666.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/736950487a274d7182f85bec24287177.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201121235915691.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2020112200011867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70#pic_center