Question

一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第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 Test {  

    public static void main(String[] args) {  

        System.out.println("结果是："+Test.foo(30));  

    }  

    /** 

     * 常见解法 

     */  

    public static int foo(int i){  

    int a=1,b=1;

    int c=0;

    for(int k=2;k<i;k++){//注意循环次数

    c=a+b;

    a=b;//注意这句要放在b=c之前

    b=c;

    }

    return c;

   }  

}

扩展资料

递归思想的内涵：

递归就是有去（递去）有回（归来）。“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就像上面例子中的钥匙可以打开后面所有门上的锁一样。

“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，就不用再往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题解决。

更直接地说，递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。

格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。

Answer 2

先看题目：数列的规律是从第3个数开始，每个数是前两个数的和。
“public static int Foo(int i)”即定义一个公共静态函数体，输入一个整数（第X位数），返回值；
“if (i <= 0) return 0;”预防输入0或负数，输入则返回“0”；
“else if (i > 0 && i <= 2) return 1;”如果输入第1位或第2位，则返回“1”（如题）；
“else return Foo(i - 1) + Foo(i - 2);”输入其它的数则返回前两个数的值。注意：因为求数列中每一个值都是调用该函数，所以求前两个数的值就又要调用2个这个函数。这就是递归（调用自身）。
eg：求Foo（30）的值，则返回Foo(29) + Foo(28)的值，其中又要调用Foo(29) 和Foo(28)求它们的值，Foo(29)又要调用Foo(28)和Foo(27)，Foo(28)又要调用Foo(27)和Foo(26)……直到调用Foo(2)和Foo(1)会返回“1”，又一层层代回去，最后加出正确答案。

追问

我好想明白一点.

追答

以下是解Foo（5）的逻辑过程，你看看能否有点感觉

Answer 3

上面用的是java程序写的代码，通常是学计算机的人写的，其实，你可以看到，第三个数据就是前面两个相加得到，第四个数据就是第二个和第三个相加得到的，就是这样递归啦

追问

我就是搞程序的 看不懂 哭

追答

搞程序的，你应该多看写C语言啦，这些好难说得懂的，关键靠自己，你数学基础还可以的吧。呵呵

Answer 4

Foo(int i)就是计算数列的第 i 项
小于2的时候就是1
否则就是前两项之和~~
计算前两项，用相同的方法去算~~~

追问

不明白- - 计算前两项的和? 1+2?

追答

数组规则是
除了一开始的两项以外，每个元素等于前两个元素之和。
即f(x)=f(x-1)+f(x-2)~
所以就用递归计算前两项，再求和。。。

Answer 5

它的意思就是先把初始值（第一、二项的）定好，然后计算。