What is wrong with this Fibonacci function?

Stumbled upon this example of bad C++ code in a blog post, without any explanation as to why it is considered "bad". I have my own ideas, but would like to hear experienced C++ devs on this.

unsigned int Fibonacci (unsigned int n)
{
    if (n == 0 || n ==开发者_如何学Python 1)
        return n;
    else
        return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}

Perhaps because it runs in exponential time?

To elaborate on the above statement: since you're not memoizing, you spawn 2 processes with the first call, and each of those spawns two processes, and so forth down the chain until you hit the base case.

Three ways to avoid this: 1) Memoize, 2) Do it iteratively, or 3) Use the closed form equation for the Fibonacci sequence. :D

Most values of Fibonnacci (n) are calculated twice.

For example, Fibonacci(5) calls Fibonacci(4) and Fibonacci(3).

That Fibonacci(4) in turn calls Fibonacci(3) and Fibonacci(2).

See how Fibonacci(3) in this example is called twice? That's where the memoize would help, but the algorithm, while interesting and recursive, is not efficient. It would be preferable to use a more efficient algorithm than to memoize an inefficient one.

Exponential running time (and may be even super-exponential - like in this case) is bearable if you have like eternity to wait until program finishes.

But nothing in the world can possibly handle exponential memory consumption - especially exponential program stack consumption (due to exponential depth of recursion). This program will just crash because of stack overflow with big enough input number.

It is not like "recursion is evil". Recursion is acceptable if the depth of recursion is limited by some small value (e.g. if it is logarithmic of the input size or not more than sizeof(int) or something). But not when proportional to the input value n.

Some people will say it's bad because it uses recursion or because it uses it without memoization, which is quite reasonable since there are approaches that only use iteration and save values that would be repeated in auxiliary variables, other will point to the fact that it can be calculated using Binet's Formula, to a certain degree of precision.

Other people will say it's the multiple return points, and even more strangely someone might say it's bad because the else is superfluous and it could be removed to save one line.