我的Java递归fibonacci函数有什么问题？

I've just written this piece but for some reason in the console I get some numbers which look right but are in the wrong order, and some numbers are repeated. What is the problem?

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

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;
        }
    }
}

5 个解决方案

#1

Your program calculates the Fibonacci number correctly. It's the last number printed, in the top-level call to fibonacci.

您的程序正确计算斐波纳契数。这是斐波纳契*调用中打印的最后一个数字。

Some numbers are repeatedly printed because they are being calculated more than once. fibonacci(5) calls fibonacci(4) + fibonacci(3), which calls fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1), and we already have two separate recursive calls that have the same argument. There are more repeated calls as the recursive calls descend further.

一些数字被重复打印,因为它们被计算不止一次。 fibonacci(5)称为fibonacci(4)+ fibonacci(3),它称为fibonacci(3)+ fibonacci(2)+ fibonacci(2)+ fibonacci(1),我们已经有两个具有相同参数的单独递归调用。随着递归调用进一步下降,会有更多重复调用。

For a low input such as 5, this is ok, but for higher numbers, you will have performance problems, because this algorithm is exponential in nature. The complexity is O(2ⁿ). Your current print statements are highlighting all the extra calculations that are being performed. You can remove them, but the algorithm is still exponential in complexity.

对于低输入(如5),这是可以的,但是对于更高的数字,您将遇到性能问题,因为此算法本质上是指数级的。复杂度为O(2n)。您当前的打印语句突出显示正在执行的所有额外计算。您可以删除它们,但算法的复杂性仍然是指数级的。

Even though your program is currently correct, it is possible to eliminate the exponential complexity, replacing it with linear complexity (O(n)), by storing the results of intermediate calls to fibonacci in an array. This way, each intermediate step is only calculated once.

即使您的程序当前是正确的,也可以通过将中间调用的结果存储到数组中的fibonacci来消除指数复杂性,将其替换为线性复杂度(O(n))。这样,每个中间步骤仅计算一次。

#2

If you're wanting to see the Fibonacci sequence up to the set term, remove all outputs from your fibonacci(int n) method and just have one print method in main that is in a for loop from 1 up to your set term.

如果您想要查看斐波纳契序列达到设定项,请从fibonacci(int n)方法中删除所有输出,并在main中使用一个打印方法,该方法位于从1到您的设定项的for循环中。

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);
    }
}

Results:

#3

I'd advise that you remove those print statements. They are confusing you.

我建议你删除那些打印声明。他们让你很困惑。

This is the way recursion works: you pop method calls off the stack to evaluate them.

这是递归的工作方式:您从堆栈中弹出方法调用来评估它们。

This looks fine to me:

这对我来说很好看:

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);
        }
    }
}

#4

Since your function is recursive, there are multiple prints per fibonacci number. If you don't want this, move the printing outside the function

由于您的函数是递归的,因此每个斐波纳契数有多个打印件。如果您不想这样,请将打印移到功能外部

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;
        }
    }
}

If, however, you intended the prints for tracing what the function does, then it is already behaving as expected. Recursive fibonacci computes the same values multiple times, which is why it is so inefficient.

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

#5

Your method is perfectly fine, the extra prints are from the recursive calls to your fibonacci method. The call stack of fib for 4 is:

你的方法非常好,额外的打印来自你的斐波那契方法的递归调用。 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

(Note: f is short for fibonacci)

(注意:f是斐波那契的缩写)

Each one of the calls prints to the console, resulting in the extra and out of order numbers.

每个调用都会打印到控制台,从而产生额外和无序数字。