我想不通这个return1是怎么推理出来的
#include
int getn(int);
int getn(int n)
{
if(n==1 || n==2)
{
return 1; 关键是这里为什么返回1, 这个return1是怎么推理出来的?
}
else
{
return getn(n-1) + getn(n-2); 这里推理倒是很简单
}
}
void main()
{
printf("%d\n",getn(40));
}
为什么前两项返回1，因为费波拉契数列的定义就是这么规定的。
这个是费波拉契数列
其实就是数学归纳法。
费波拉契数列的第n项的值 =
如果n = 1或者2，那么结果是1
如果n > 2，那么结果是 费波拉契数列的第(n - 2)项的值 + 费波拉契数列的第(n - 1)项的值
n f(n)
1 1 f(1) = 1
2 1 f(2) = 1
3 2 f(1) + f(2)
4 3 f(2) + f(3)
5 5 f(3) + f(4)
6 8 f(4) + f(5)
7 13 ...
8 21 ...
9 34 ...
10 55 ...
...
斐波那契数列（1,1,2,3,5,8...）第一个和第二个数字为1
这个是费波拉契数列。然后这是一个递归的用法。将40传进去。然后再到执行getn(39),getn(38)。。。但是没有条件的话就会无限制的循环下去。知道传进去的参数是1或者是2的时候就会停止。至于返回什么，是由初始条件来决定的。正好这里是1就是1.没有为什么。也可以说这个是一个斐波那契数列。实际上是不推荐这样直接使用递归的。因为随着传进的参数的增大，时间的复杂度会加大，也就是说程序的运行时间会变长。可以选择用数组记录的方法去减少运行时间。
n < 1都属于非法的输入了。好比负数不能开平方。0不能被除，等等，你算 sqrt(-1) 显然程序应该报错才对。
1 1 2 3 5 8 f(n-2)+f(n-1),那一开始，当n=1或者2的时候，都是1
2 2 4 6 10 f(n-2)+f(n-1) ,那么当n=1和n=2的时候，就要return 2
1 3 4 7 11 f(n-2)+f(n-1),那么当n=1的时候，return1,当n=2的时候return 3
其实就是递归的跳出条件。
递归其实不太难，考试难的主要还是指针