递推万岁！PY万岁！

方法1

#include<bits/stdc++.h>
using namespace std;

int dg(int a,int b,int n)
{
	if(n>2)
	{
		dg(b,a+b,n-1);
	}
	else
	{
		cout<<b;
	}
}

int main()
{
	int n;
	cin>>n;
	dg(1,1,n);
	return 0;
}

方法2

#include<bits/stdc++.h>
using namespace std;

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