[数据结构与算法]C语言之斐波那契（递归形式）

题目描述：

斐波那契数列定义为：f(1)=1，f(2)=1；当n>2时，f(n)=f(n-1)+f(n-2)。求斐波那契数列的第n项。

输入

输入一个正整数n（1<=n<=46）

输出

斐波那契数列的第n项

做题步骤：

下面是递归思想最重要的两步，理解了，其他递归也类似。

1.递归函数，斐波那契中为f(n)=f(n-1)+f(n-2)，return的时候f(n-1)+f(n-2)就行了，因为在f（）这个函数里面，就是f（）=返回值的意思

2.设置函数递归终点，递归就是不断调用自己，得给他一个停下来的条件，也就是代码中的n=1||n=2，有两个条件的原因是递归结果是两个递归相加，也就是说当调用自己直到n==1或者n==2就不能再执行n-1，n-2操作了

#include<stdio.h>
int f(int n)

{
	if(n==1||n==2) 
	return 1;
	else
	return f(n-1)+f(n-2); 
}

int main()
{
	int n;
	scanf("%d",&n); 
	printf("%d",f(n));
} 

C语言中递归与指针的地位相差不多，也是后面学习数据结构的基础，需要认真掌握，而

斐波那契也是递归中最基础的，需要熟练掌握！