斐波那契函数问题

Question

我正在计算Fibonacci序列,偶然发现了这段代码,我看到了很多:

    int Fibonacci (int x)
{
    if (x<=1) {
        return 1;
    }
    return Fibonacci (x-1)+Fibonacci (x-2);
}

我不明白它是如何工作的,特别是最后的返回部分:它是否再次调用Fibonacci函数？有人能引导我完成这个功能吗？

Answer 1

是的,该函数调用自身.例如,

Fibonacci(4)
= Fibonacci(3) + Fibonacci(2)
= (Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0))
= ((Fibonacci(1) + Fibonacci(0)) + 1) + (1 + 1)
= ((1 + 1) + 1) + 2
= (2 + 1) + 2
= 3 + 2
= 5

请注意,Fibonacci函数在此处调用了9次.一般来说,天真的递归斐波纳契函数具有指数运行时间,这通常是一件坏事.

Answer 2

这是递归函数的经典示例,它是一个调用自身的函数.

如果你仔细阅读它,你会看到它会自己调用,或者一遍又一遍地重复,直到它到达所谓的基本情况,x <= 1此时它将开始"回溯"并总结计算值.

以下代码清楚地打印出算法的跟踪:

public class Test {

    static String indent = "";

    public static int fibonacci(int x) {

        indent += "    ";
        System.out.println(indent + "invoked with " + x);

        if (x <= 1) {

            System.out.println(indent + "x = " + x + ", base case reached.");
            indent = indent.substring(4);

            return 1;
        }

        System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2));
        int retVal = fibonacci(x-1) + fibonacci(x-2);
        System.out.println(indent + "returning " + retVal);
        indent = indent.substring(4);
        return retVal; 

    }


    public static void main(String... args) {
        System.out.println("Fibonacci of 3: " + fibonacci(3));
    }
}

输出如下:

invoked with 3
Recursing on 2 and 1
    invoked with 2
    Recursing on 1 and 0
        invoked with 1
        x = 1, base case reached.
        invoked with 0
        x = 0, base case reached.
    returning 2
    invoked with 1
    x = 1, base case reached.
returning 3

Fibonacci of 3: 3

跟踪的树形描绘看起来像

                               fib 4
               fib 3             +           fib 2
    fib 2        +    fib 1              fib 1 + fib 0
fib 1 + fib 0           1                  1       1
  1       1

编写递归函数时要考虑的重要部分是:

1.照顾基础案例

如果我们if (x<=1) return 1;在上面的例子中忘记了会发生什么 ？

2.确保递归调用以某种方式减少朝向基本情况

如果我们不小心修改了算法返回会发生什么 fibonacci(x)+fibonacci(x-1);