关于递归调用的问题

Question

例如问题是这样的:一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少， 用递归算法实现。
 
正确答案是：public class MainClass 
{ 
public static void Main() 
{ 
Console.WriteLine(Foo(30)); 
} 
public static int Foo(int i) 
{ 
if (i <= 0) 
return 0; 
else if(i > 0 && i <= 2) 
return 1; 
else return Foo(i -1) + Foo(i - 2); 
} 
}
请问 最后一个else中的 Foo(i -1) + Foo(i - 2)中的 i-1 和 i-2是什么意思？谢谢

Answer 1

这个数列规律第三位起，每个数是前两个数的和
 Foo(i -1) + Foo(i - 2) 求前两位的和Foo(30) = Foo(29) + Foo(28)
Foo(29) = Foo(28) + Foo(27)
.....
.....
Foo(2) = 1
Foo(1) = 1
递归开始
Foo(1) = 1
Foo(2) = 1Foo(3) = Foo(2) + Foo(1) = 2 
Foo(4) = Foo(3) + Foo(2) = 3
....
...

Answer 2

public static int Foo(int i) 
{ 
  if (i <= 0) 
     return 0; 
  else if(i > 0 && i <= 2) 
     return 1; 
  else 
     return Foo(i -1) + Foo(i - 2); 
} 
}
能走到这一步，说明至少i>=3.i>=3数组的规律是 i位的数=i-1位数+i-2位数

Answer 3

这个，是菲波拉契数列吧？
这个是实现数列中前前两项之和等于第三项，
那么 如果你递归的项小于3都直接跳出函数。
如果不满足前面两个条件（就是最后一个else）
就继续执行 直到I满足前面两个条件中任意一个为止。
i-1 ,i-2分别是第i个数字的前面一个和前面第二个。

Answer 4

这就是递归代码如此精简的原因所在 呵呵执行的时候Console.WriteLine(Foo(30)); 
进入Foo传进来的值是30 
因为不是0,1,2 
所以会执行到return Foo(i -1) + Foo(i - 2); 
Foo(i-1)+Foo(i-2) 就相当于Foo(29)+Foo(28);这样就再一次的进入 我开始分析的阶段   Foo(29) 里面又会有Foo(28)+Foo(27)    Foo(28)同理 以此类推不断的进入新的Foo
直到进入的数由2,1,0  就开始分别返回1,1,0   在这个过程中进了很多次Foo  所以就有很多1，1,1相加 直到最终得到结果
对于初学的你 可以一开始不要带入30这么大数  带入一个4  自己用笔算算就推敲出其中的奥妙了 
 

Answer 5

初始i=30,i满足i>=3
Foo(30) = Foo(29) + Foo(28)
Foo(29) = Foo(28) + Foo(27)
.....
.....
直到
Foo(3) = Foo(2) + Foo(1)
以上都是未知量
Foo(2)当i=2满足i<=2且i>0得到Foo(2)=1
Foo(1)当i=1满足i<=2且i>0得到Foo(1)=1
代入以上公式最终获取Foo(30)的值。