Why does the fibonacci recursive sequence work?

Question

I am wondering why this Fibonacci recursive function works:

int fibRec(int n)
{
    if ((n == 1) || (n == 0))
    {
        return n;
    }

    int i = fibRec(n - 1) + fibRec(n - 2);
    return i;
}

I understand what the Fibonacci sequence is and I understand what a recursive function does and how this function is working. I'm just having troubles understanding why it works. I know that when you break it down, you are essentially adding a bunch of 0s and 1s, as this image depicts.

fibonacci recursive

But why is it that when I pass a 5 to the function and all the 0 and 1s are added that it will equal the 5th sequence number in the Fibonacci sequence? I've seen this question asked before but never really explained. The responses are all just "because recursion". Yes, I know what a recursive function is and how this one is working. But WHY does this recursive function give you the correct Fibonacci sequence number?

Maybe it would help if you annotated the fib(n) nodes with the results the nodes return; or if you worked out fib(5) fully on paper. Another way of looking at it is: the sum of those carefully constructed(!) 0s and 1s results in fib-5 because that is how fib-5 is ultimately defined; akin to the sum of '1' and '2' being defined as '3'. — Lars

William Rosenbloom William Rosenbloom · Accepted Answer · 2016-02-25T03:42:57

In the Fibonacci sequence the first two numbers are zero and one. Every number after these is the sum of the previous 2 numbers. So the first few numbers are

F(0) ≡ 0
F(1) ≡ 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
...
F(n) = F(n - 1) + F(n - 2) ∀ n > 1

Therefore when we calculate a Fibonacci number recursively we have to practice the following logical procedure (in pseudo-code out of respect to StackOverflow).

Integer NthFibonacci(Integer n) {
    if (n < 0) {
        return undefined;
    } else if (n < 2) {
        return n;
    } else {
        return NthFibonacci(n - 1) + NthFibonacci(n - 2);
    }
}

I'm sure you know all this but I think it will help my explanation to have this part as a reference.

Where the Ones and Zeros Come In

The best way to explain this is probably with an example.

Imagine that, as above, we are trying to recursively calculate F(6). Try following the procedure given above. Remember that we will perform recursion only if n > 1.

First we start with F(6) = F(5) + F(4).
Then we find F(5) = F(4) + F(3).
Then we find F(4) = F(3) + F(2).
Then we find F(3) = F(2) + F(1).
Then we find F(2) = F(1) + F(0).

This is where things start to work out!

We have now gotten F(2) in terms of F(1) ≡ 1 and F(0) ≡ 0 (both of which are known), and so we are able to calculate an actual value instead of performing more recursion.

We can now find F(2) = F(1) + F(0) = 1 + 0 = 1.

NOTICE THE 1 AND 0 Those are what people are talking about when they say the whole thing comes down to ones and zeros. Every time we recurse down to find a base value we will end up finding F(2) = 1 + 0. This leads to more ones and zeros as we move back up our recursion tree being able to calculate higher and higher values, as follows.

F(3) = F(2) + F(1) = (1 + 0) + 1
F(4) = F(3) + F(2) = ((1 + 0) + 1) + (1 + 0)
F(5) = F(4) + F(3) = (((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)
F(6) = F(5) + F(4) = ((((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)) + (((1 + 0) + 1) + (1 + 0))

Now if you add up all the 1's you get a sum of 8, and so F(6) = 8, which is correct!

This is how it works, and this is how it breaks down to ones and zeros.

Why does the fibonacci recursive sequence work?

2 Answers

Where the Ones and Zeros Come In