斐波纳契函数问题

问题描述

我在计算Fibonacci序列，偶然发现这个代码，我看到了很多：

I was calculating the Fibonacci sequence, and stumbled across this code, which I saw a lot:

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

我不明白是如何工作的，结束：它是否再次调用Fibonacci函数？

What I don't understand is how it works, especially the return part at the end: Does it call the Fibonacci function again? Could someone step me through this function?

推荐答案

是的，函数调用自身。例如，

Yes, the function calls itself. For example,

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次。一般来说，幼稚的递归fibonacci函数具有，它是通常是坏事。

Note that the Fibonacci function is called 9 times here. In general, the naïve recursive fibonacci function has exponential running time, which is usually a Bad Thing.

这篇关于斐波纳契函数问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！