斐波那契函数结果混淆

Question

public class Fibonacci {
    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        for (int i = 1; i <= N; i++)
            System.out.println(i + ": " + fib(i));
    }
}

假设用户输入“java Fibonacci 7”，结果如下：

1:1

2:1

3:2

4:3

5:5

6:8

7:13

从参数 3 开始，我似乎对它的工作原理完全感到困惑。当 fib(i) 方法通过 3 时，它不应该返回 3 吗，因为如果 n = 3 那么 fib(n-1) 的总和/ n-1 是 2 / 而 fib(n-2) / n-2 是 1 / 是 3。以此类推其他数字。

原文由 Marz 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果您将 3 传递给您的函数，它将执行以下操作：

 fib(3) = fib(2) + fib(1) //so we we are into the else statement, because 3 > 1
= fib(2) + 1             //fib(1) = 1 because 1 <= 1 so you return it (if statement)
= (fib(1) + fib(0)) + 1  //2 > 1 => we go to the else statement
= (1 + 0) + 1            //0 <= 1 & 1 <= 1 so we are into the if and return the values
= 2

原文由 Alex VII 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是一个更简单的代码来生成像’0 1 1 2 3 …‘这样的斐波那契数列。

 public static void main (String[] args) {
    int f = 0;
    int g = 1;

    for (int i = 1; i <= 10; i++) {
        System.out.print(f + " ");
        f = f + g;
        g = f - g;
    }

    System.out.println();
}

原文由 J.K 发布，翻译遵循 CC BY-SA 3.0 许可协议