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?