我的 Java 递归斐波那契函数有什么问题？

Question

我刚刚写了这篇文章，但出于某种原因，在控制台中我得到了一些看起来正确但顺序错误的数字，并且有些数字是重复的。有什么问题？

public class Fibonacci {
    public static void main(String[] args) {
        int n = 5;

        fibonacci(n);
    }

    public static int fibonacci(int n) {
        if(n == 0) {
            System.out.println(0);
            return 0;
        } else if(n == 1) {
            System.out.println(1);
            return 1;
        } else {
            int result = fibonacci(n - 1) + fibonacci(n - 2);
            System.out.println(result);
            return result;
        }
    }
}

Answer 1

您的程序正确计算了斐波那契数列。这是最后打印的数字，在对 fibonacci.

的顶级调用中

有些数字被重复打印，因为它们被计算了不止一次。 fibonacci(5) 调用 fibonacci(4) + fibonacci(3)，后者调用 fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1)，并且我们已经有两个具有相同参数的独立递归调用。随着递归调用的进一步下降，重复调用越来越多。

对于像 5 这样的低输入，这是可以的，但是对于更高的数字，你会有性能问题，因为这个算法本质上是指数的。复杂度为 O(2ⁿ)。您当前的打印语句突出显示了所有正在执行的额外计算。您可以删除它们，但算法的复杂度仍然呈指数级增长。

即使您的程序目前是正确的，也可以消除指数复杂度，将其替换为线性复杂度 (O(n))，方法是将对 fibonacci 的中间调用结果存储在数组中.这样，每个中间步骤只计算一次。

Answer 2

我建议您删除那些打印语句。他们让你感到困惑。

这就是递归的工作方式：将方法调用弹出堆栈以对其求值。

我觉得不错：

public class Fibonacci {
    public static void main(String[] args) {
        int n = 10;

        for (int i = 0; i < n; ++i) {
            System.out.println(String.format("i: %5d fib(i): %10d", i, fibonacci(i)));
        }
    }

    public static int fibonacci(int n) {
        if(n == 0) {
            return 0;
        } else if(n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

Answer 3

由于您的函数是递归的，因此每个斐波那契数有多个输出。如果你不想这样，把打印移到函数外

public class Fibonacci {
    public static void main(String[] args) {
        int n = 5;

        System.out.println(fibonacci(n));
    }

    public static int fibonacci(int n) {
        if(n == 0) {
            return 0;
        } else if(n == 1) {
            return 1;
        } else {
            int result = fibonacci(n - 1) + fibonacci(n - 2);
            return result;
        }
    }
}

但是，如果您打算通过打印来跟踪函数的作用，那么它已经按预期运行。递归斐波那契多次计算相同的值，这就是它如此低效的原因。

Answer 4

如果您想查看设定项之前的斐波那契数列，请从您的 fibonacci(int n) 方法中删除所有输出，并在 for 从 1 循环到你设定的任期。

public static void main(String[] args) {
    int n = 5;

    for (int i = 1; i <= n ; i++) {
        System.out.print(fibonacci(i) + " ");
    }
}

public static int fibonacci(int n) {
    if(n == 0) {
       return 0;
    } else if(n == 1) {
       return 1;
    } else {
       return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

结果：

Answer 5

您的方法非常好，额外的打印来自对您的 fibonacci 方法的递归调用。 fib for 4的调用栈为：

                         f(4)
                  /                 \
          f(4-1)          +            f(4-2)
        /          \                /         \
   f(3-1)   +     f(3-2)  +      f(2-1)  +  f(2-2)
    /      \        |               |          |
 f(2-1) + f(2-2)    |               |          |
    |        |      |               |          |
    1   +    0  +   1      +        1     +    0
                        3

(注：f是fibonacci的缩写)

每个调用都会打印到控制台，从而导致额外的和乱序的数字。

我的 Java 递归斐波那契函数有什么问题？

What is wrong with my Java recursive fibonacci function?

java

recursion

fibonacci