这是一到面试题,相信大家都知道,但我不知道这到底是如何进行的. 忘路过的高手们解释一下。1

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); 
} 
} 

Answer 1

public class MainClass&nbsp;{&nbsp;public static void Main()&nbsp;&nbsp;{&nbsp;Console.WriteLine(Foo(30)); //调用Foo函数，参数是30}&nbsp;public static int Foo(int i)&nbsp;{ //Foo函数的函数体if (i <= 0)&nbsp;return 0;&nbsp;else if(i > 0 && i <= 2)//i为1和2的时候，返回1&nbsp;return 1;&nbsp;else return Foo(i -1) + Foo(i - 2);&nbsp;//i从3开始，返回值为前2个值相加//其实就是斐波那契数列//1 1 2 3 5 8 13 21 ......每个数等于前2个数的和}&nbsp;}

Answer 2

这是用C#写的Console.WriteLine(Foo(30));&nbsp;意为输出第30个数if (i <= 0)&nbsp;return 0; 当i<=0的时候 就返回0 就是说Foo(0)=0else if(i > 0 && i <= 2)&nbsp;return 1; 当i > 0 && i <= 2的时候 就返回1 就是说Foo(1)=1，Foo(2)=1else return Foo(i -1) + Foo(i - 2);&nbsp;&nbsp;这里 我就举个例子 当i=3 ，Foo(3)=Foo(2)+Foo(1)=2 知道Foo（30)