Recursively calling the same method twice

Question

In the Fibonacci sequence, I have seen conventional implementations which recursively call the same method twice:

public void fibonacci(int i)
{
fibonacci(1) + fibonacci(2);
}

Now this method is not the exact copy of what I have seen or the right way of solving the problem, but I've seen the two methods added together like above. So the method isn't recursively called, but recursively called twice. What exactly happens when writing code like this in C#? Are the two methods run on seperate threads? What is happening under the hood?

Answer 1

This is one of those times when it's useful to think about the way the computer does it.

Let's start with the function. I'm going to write it in Python flavored pseudocode because I want you to get away from thinking about the LANGUAGE for a second.

def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    if n >  1: return fib(n-2) + fib(n-1)

Now let's walk through this for fib(2)

fib(2) has n>1, so it takes the third branch,

   return fib(2-2) + fib(2-1)

so it calls fib() with 0, which is 0

   return 0 + fib(2-1)

calls fib() with 1

   return 0 + 1

and we see the result 1. Now consider fib(3):

n>1, so

return fib(3-2)+fib(3-1)

and since 3-2 is 1, we get fib(1) for the first term, which is 1:

return 1 + fib(3-1)

and now when we call fib(3-1), which is to say fib(2), we don't have the direct answer yet; n>1. So it becomes

return 1 +
    return fib(2-2) + fib(2-1)

which becomes

    return 0 + 1

ans we pop back to the earlier call

return 1 + 1

and get the value 2. So, you see, there's no separate thread, it just works its way across the expression. I'll leave it as an exercise to work out an example for fib(4); I bet if you do, though, you'll have it nailed.

Pop quiz: why is the iterative version so dramatically more efficient?

Answer 2

No, they are called one after another. No additional threads are made unless you explicitly ask for it (with System.Threading stuff). I'm not sure on the order they are called, but I would guess that from left to the right. C# specification definately has it in it.

Answer 3

They are valued sequentially. i.e. fibonacci(1) is valuated before fibonacci(2) is. If you want to visualise it, it's a case of going down the first calling tree (with it's own "split recursion"), back up, before going down the second three.

As an aside, this is often used as an example on how not to use recursion, as it is an obvious but inefficient manner to valuated the fibonacci sequence. The preferred option is either the iterative approach (working out the first number, then the next one etc. until the desired one), or, even better, the closed form equation.

Answer 4

In C# you can easily implement the method as you suggest - it could look something like this

public static int Fib(int i) {
   if (i == 0) return 0;
   if (i == 1) return 1;
   return Fib(i - 2) + Fib(i - 1);
}

However, there's no magic here. It is just once recursive call followed by another. I.e. all the code run sequentially on the same thread.

The performance is also really bad due to the two recursive calls for each iteration, so even for quite small values of i this implementation may not be useful. If you need the performance you're better off avoiding the recursive calls by just handling the state yourself.