黑马程序员技术交流社区

标题: 斐波那契数列的两种解法-[递归]-[递推] [打印本页]

---

作者: DadouBK    时间: 2016-8-18 22:03
标题: 斐波那契数列的两种解法-[递归]-[递推]
斐波那契数列指的是这样一个数列  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368。
简单地说就是从第三项开始每项的值等于前两项值的和，这样的数列叫做斐波那契数列；关于这个问题。常被我们当作递归来对待，其实它的高效解法是递推，不过这两种方式都可以做，差别在于算法的复杂度。这个稍后我会写帖子详说；
下面我给出两个方法的代码，mother1是递归的解法，mother2是递推的解法。

[Java] 纯文本查看 复制代码

/**

 * @author Dadou

 * Fibonacci数列的递归解法

 */

package cn.dadoubk.Fibonacci;



public class mother1 {

        public static void main(String[] args) {

                int n = 10;// 求第n项Fibonacci数值

                System.out.println(Fibonacci(n));

        }



        private static int Fibonacci(int n) {

                if (n <= 2)

                        return 1;

                return Fibonacci(n - 1) + Fibonacci(n - 2);

        }

}

[Java] 纯文本查看 复制代码

/**

 * @author Dadou

 * Fibonacci数列的递推解法

 */

package cn.dadoubk.Fibonacci;



public class mother2 {

        public static void main(String[] args) {

                int n = 10;// 求第n项Fibonacci数值

                int[] f = new int[100];

                f[1] = 1;

                f[2] = 1;

                for (int i = 3; i <= n; i++)

                        f = f[i - 1] + f[i - 2];

                System.out.println(f[n]);

        }

}

简单说下递归和递推两种算法思想；
递归：大问题转化成小问题
递推：小状态推出大状态

---

作者: x55555lg    时间: 2016-8-18 22:12
支持一个，顶一下

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2