递归算法2——简单递归之斐波那契数列（递归法）

斐波那契数列指的是这样的一个数列：

0，1，1，2，3，5，8，13，21，......从第3个数起，每个数都是前两个数之和。编写算法，输出斐波那契数列的前n项。

【分析】
斐波那契数列可以写成如下公式：

$fibibacci(n)= begin{cases} 0 & n=0 \ 1 & n=1 \ fibibacci(n-1) + fibibacci(n-2) & n=2,3,4,... end{cases}$

当n=4时，求fibibacci(4)的值过程如下图所示。

其中，图中阴影部分为对应的函数值。求fibibacci(4)的值，需要知道fibibacci(3)与fibibacci(2)的值，而求fibibacci(3)的值需要知道fibibacci(2)和fibibacci(1)的值，求fibibacci(2)的值需要知道fibibacci(1)和fibibacci(0)的值。fibibacci(1)=1，fibibacci(0)=0，所以直接返回。

code:

#include<stdio.h>
#include <iostream>
int fib(int n);
void main()
{
	int n;
	printf("请输入项数:");
	scanf("%d", &n);
	printf("第%d项的值:%dn", n, fib(n));
	system("pause");
}
int fib(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (n > 1)
		return fib(n - 1) + fib(n - 2);
	
}

结果：

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/baidu_36669549/article/details/104133121
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-03-01 21:19:21
阅读 ( 1176 )
分类：算法

递归算法2——简单递归之斐波那契数列（递归法）

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看