I can't understand this Fibonacci program flow

Question

so Im new to the world of programming and thought Id pick up a book to start learning. I bought A Players Guide to C# 3rd Edition and one of the little homework assignments it gives you has me pretty stumped. I was debugging it step by step to help me understand, but the flow of the program makes no sense to me. Here it is.

      static void Main(string[] args)
        {
            for (int index = 1; index <= 10; index++)
            {
                Console.WriteLine(Fibonacci(index));
            }

            Console.ReadKey();
        }

        /// <summary>
        /// Returns a number from the Fibonacci sequence, starting at 1.
        /// Note that this implementation is not very optimized, and can
        /// take a very long time if you're looking up large numbers.
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        static ulong Fibonacci(int number)
        {
            if (number == 1) { return 1; }
            if (number == 2) { return 1; }

            return Fibonacci(number - 1) + Fibonacci(number - 2);
        }

the first two times it runs through the for loop it prints out '1' and '1' because the first time through the index is '1' making that first if statement true and the second time through the index is '2' making the second if statement true. But when it runs a 3rd time and the index turns to 3 it goes to that return statement, and if my math is right (3-1) + (3-2) equates to 3, which makes sense right. So I expect it to break from the method return 3 and write that to the Console window, but it doesnt. Instead it runs through the method again this time saying the value of the number is 2.(ok??) well at least it should stop at that 2nd if statement and reprint '1' again. Nope it ignores that line hits the return statement again. What the hell is going on? Please explain this logic.

Answer 1

There is a nice illustration of this kind of recursive hell.

Note that the illustration is for one iteration of your loop

And also, it is drawn for this code :

return Fibonacci(number - 2) + Fibonacci(number - 1);

as you have the reversed addition, the correct program flow would be the opposite as the one shown by the diagram below.

Image was taken here : http://composingprograms.com/pages/28-efficiency.html

I call it hell for two reasons :

Difficult to read for the developper

The first time the fibfunction is called, with parameter 6, it first calls fib(4), (the left part of the tree), then, when it's over, calls fib(5) (the right part of the tree).

Recursion can however be very useful for some case, but this school-one is absolutely not fitted for this recursion. The purpose of code is not to be read only by compilers, it is to be read by developers as well.

Inefficient

As you can see, some fib(n) are called several time with the same n.

At the end, this recursive algorithm is O(2^n), which is quite bad for this problem

Even more inefficient in a loop

Remember, the illustration is for only one iteration ! You can draw a diagram for fib(n) like this for each n.

With this method, you lose each previously calculated values, instead of reusing them to calculate the next value. This loop has then complexity O(n * 2^n)

Answer 2

Well, it's a not so simple example of recursion, and to makes matters worst, it's being executed inside a loop... Hardly what I would use to teach people what recursion is.

So, the point of recursion is that a function will execute itself over and over again until it's stopping condition is met (And if it's never met or doesn't even exists it will create an infinite recursion, that most of the times is not a good thing).

A classic example of recursion would be to calculate factorial (and in case you don't remember how it works, 5! = 5 * 4 * 3* 2 * 1).

So an implementation of a factorial recursive method would be something like this:

Int64 Factorial(int input)
{
    if(input < 0) 
    {
         throw new ArgumentOutOfRangeException("Input must be 0 or higher.");
    }
    if(input < 2) 
    {
        return 1;
    }
    return input * Factorial(input - 1);
}

(0! = 1, and -3! is invalid...)

Now, let's say you call this method with the number 3:
Factorial(3) will return 3 * Factorial(3-1).
Similarly, Factorial(2) will return 2 * Factorial(2-1).
Factorial(1) will simply return 1.
Putting it all together Factorial(3) will return 3 * 2 * 1 which is 3!.

Now, in your case, The Fibonacci recursive method stopping condition is number is either 1 or 2, but it calls itself twice: Fibonacci(number - 1) + Fibonacci(number - 2);. To make matters worst it's being executed from inside a for loop, calculating the number on the Fibonacci sequences by indexes (from 1 to 10).

Let's examine what Fibonacci(3) does:

Fibonacci(3) will return Fibonacci(3-1) + Fibonacci(3-2).
Fibonacci(2) will return 1.
Fibonacci(1) will return 1.

So, Fibonacci(3) will return 1 + 1.

Let's take the next number:

Fibonacci(4) will return Fibonacci(4-1) + Fibonacci(4-2).
We already calculated that Fibonacci(3) returns 2, and we know that Fibonacci(2) will return 1, so Fibonacci(4) will return 3
(or 1+1+1 if you want to step into every call).

Similarly, Fibonacci(5) will return Fibonacci(5-1) + Fibonacci(5-2) - So it's 3 + 2 and so on (Fibonacci(6) will return 5+3, Fibonacci(7) will return 8+5).