[数据结构与算法]1159：斐波那契数列(C++递归）

首先，理解题意：

用递归的方法算出斐波那契数列(0.1.1.2.3.5.8.13......)的第n项是多少。

很简单，是不是？所以抛出以下程序：

#include<iostream>
#include<cstdio>
using namespace std;
int d(int n)
{

    if(n==1) 
	{
		return 1;
	}
	else 
	{
		return d(n-2)+d(n-1);
	}
}
int main()
{
	int a;
	cin>>a;
	cout<<d(a); 
	return 0;
}

看起来没错，对不对？

但是 ，超时了

哪错了？

首先，我们要知道，递归有两大要素：

1.递归关系式

2.停止的条件

这两大要素在递归中一定要搞清楚。

回看一下程序，就可以知道

return d(n-2)+d(n-1)

?是递归关系式，而

if(n==1) 
	{
		return 1;
	}

则是停止的条件。

仔细看一看，关系式没错，

既然关系式没错，那就是停止的条件错了，

在递归中，停止的条件是一个固定不变的数，在斐波那契数列中，不变的数是最前面的0，不是1。

但是，因为数列中的下一个数需要前面两个数加起来才能得出来，所以停止的条件一共有两个，如下：

if(n==1)
	{
		return 0;
	}
	else if(n==2)
	{
		return 1;
	}

所以整段代码是这样的：

#include<iostream>
#include<cstdio>
using namespace std;
int d(int n)
{
	if(n==1)//停止的条件 
	{
		return 0;
	}
	else if(n==2)//停止的条件 
	{
		return 1;
	}
	else 
	{
		return d(n-2)+d(n-1);//递归关系式 
	}
}
int main()
{
	int a;
	cin>>a;
	cout<<d(a);//输出结果 
	return 0;
}

END