What is wrong with this Fibonacci function?

Question

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

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 works in exponential time?

Answer 2

To think through the above statement: since you are not imaginary, you create 2 processes with the first call, and each of them spawns two processes, etc. down the chain until you click on the base case.

Three ways to avoid this: 1) Remember, 2) Do iteratively, or 3) use a closed-form equation for the Fibonacci sequence .: D

Answer 3

Most Fibonnacci (n) values ​​are calculated twice.

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

The fact that Fibonacci (4), in turn, causes Fibonacci (3) and Fibonacci (2).

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

Answer 4

The exponential work time (and maybe even superexponential - as in this case) is tolerable if you have an eternity to wait for the program to finish.

But nothing in the world can handle exponential memory consumption - especially the exponential consumption of the program stack (due to the exponential depth of recursion). This program will simply crash due to a lot of input.

This does not mean that "recursion is evil." Recursion is acceptable if the recursion depth is limited to some small value (for example, if it is logarithmic to the input size or not larger than sizeof (int) or something else). But not proportional to the input value of n .

Answer 5

Some people will say this badly because it uses recursion or because it uses it without memoization, which is quite reasonable, because there are approaches that use only iteration and store values ​​that will be repeated in auxiliary variables, others indicate the fact that it can be calculated using the Binet formula with a certain degree of accuracy.

Other people will say that these are multiple return points, and even more strange, someone might say it badly because the other is superfluous and can be deleted to save one line.