斐波那契数列

基础

如果我们需要重复地多次计算相同的问题，则通常可以选择用递归或者循环两种不同的方法。递归是在一个函数的内部调用这个函数自身。而循环则是通过设置计算的初始值及终止条件，在一个范围内重复运算。比如求1+2+-+ « ，我们可以用递归或者循环两种方式求出结果。

通常递归的代码会比较简洁。在上面的例子中，递归的代码只有一条语句，而循环则需要4 条语句。在树的前序、中序、后序遍历算法的代码中，递归的实现明显要比循环简单得多。在面试的时候，如果面试官没有特别的要求，则应聘者可以尽量多采用递归的方法编程。

虽然有简洁的优点，但它同时也有显著的缺点。递归由于是函数调用自身，Ifl]'函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解h述的例子中递归实现的效率不如循环。

另外，递归中冇可能很多计算都是重复的，从而对性能带来很大的负面影响。递归的本质是把一个问题分解成两个或者多个小问题。如果多个小问题存在相互重叠的部分，就存在重复的计算。在面试题10 “斐波那契数列”及面试题 60 个骰子的点数”中，我们将详细地分析递归和循环的性能R 别。

通常应用动态规划解决问题时我们都是用递归的思路分析问题，但出于递归分解的子问题中存在大量的重复，因此我们总是用自下而上的循环来实现代码。我们将在面试题14 “剪绳子”、面试题47 “礼物的最大价值”及面试题48 “最长不含重复字符的子字符串”中详细讨论如何用递归分析问题并基于循环写代码。

除效率之外，递归还有可能引起更严重的问题：调用栈溢出。在前面的分析中提到需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。在上述例子中，如果输入的参数比较小，如 10,则它们都能返回结果55。但如果输入的参数很大，如 5000,那么递归代码在运行

的时候就会出错，但运行循环的代码能得到正确的结果丨2502500。

题目

思路

代码

思路1 
public static void main(String[] args) {
    System.out.println("请输入n");
    Scanner sc = new Scanner(System.in);
    System.out.println(fib(sc.nextInt()));
}
public static int fib(int N) {
    if(N == 0 || N ==1){
        return N;
    }
    return fib(N-1)+fib(N-2);
}

思路2
public static int fib(int N) {
    if(N == 0 || N ==1){
        return N;
    }
    int fibOne = 0;
    int fibTwo = 1;
    int fibN =0;
    for(int i =2;i<= N;i++){
        fibN = fibOne + fibTwo;
        fibOne = fibTwo;
        fibTwo = fibN;
    }
    return fibTwo;
}
思路3
动态规划
class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }
        int[] dp = new int[N + 1];
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
}

LeetCode

示例 1：

输入：2

输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2

输入：3

输出：2

解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

输入：4

输出：3

解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示：

0 ≤ N ≤ 30