What is wrong with this Fibonacci function?

Question

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 == 1)
        return n;
    else
        return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}

Answer 1

Perhaps because it runs in exponential time?

Answer 2

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

Answer 3

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.