c++ - 斐波那契函数题

Question

我在计算斐波那契数列时，偶然发现了这段代码，我经常看到它:

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

我不明白它是如何工作的，尤其是最后的返回部分:它是否再次调用斐波那契函数？有人可以指导我完成此功能吗？

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 次。一般来说，朴素的递归斐波那契函数有 exponential running time ，这通常是一件坏事。