How does the recursion here work?

Question

Code 1:

public static int fibonacci (int n){ 
    if (n == 0 || n == 1) { 
        return 1; 
    } else { 
        return fibonacci (n-1) + fibonacci (n-2); 
    }        
} 

How can you use fibonacci if you haven't gotten done explaining what it is yet? I've been able to understand using recursion in other cases like this:

Code 2:

class two 
{
    public static void two (int n) 
    {
        if (n>0) 
        {
            System.out.println (n) ;
            two (n-1) ;
        }
        else
        {
            return ;
        }
    } 

    public static void main (String[] arg) 
    {
        two (12) ;
    }
}

In the case of code 2, though, n will eventually reach a point at which it doesn't satisfy n>0 and the method will stop calling itself recursively. In the case of code 2, though, I don't see how it would be able to get itself from 1 if n=1 was the starting point to 2 and 3 and 5 and so on. Also, I don't see how the line return fibonacci (n-1) + fibonacci (n-2) would work since fibonacci (n-2) has to contain in some sense fibonacci (n-1) in order to work, but it isn't there yet.

The book I'm looking at says it will work. How does it work?

Answer 1

Well, putting aside what a compiler actually does to your code (it's horrible, yet beautiful) and what how a CPU actually interprets your code (likewise), there's a fairly simple solution.

Consider these text instructions:

To sort numbered blocks:

1. pick a random block.
2. if it is the only block, stop.
3. move the blocks with lower numbers to the left side, higher numbers to the right.
4. sort the lower-numbered blocks.
5. sort the higher-numbered blocks.

When you get to instructions 4 and 5, you are being asked to start the whole process over again. However, this isn't a problem, because you still know how to start the process, and when it all works out in the end, you've got a bunch of sorted blocks. You could cover the instructions with slips of paper and they wouldn't be any harder to follow.

Answer 2

In the case of code 2 though n will eventualy reach a point at which it doesnt satisfy n>0 and the method will stop calling itself recursivly

to make it look similar you can replace condition if (n == 0 || n == 1) with if (n < 2)

Also i don't see how the line `return fibonacci (n-1) + fibonacci (n-2) would work since fibbonacci n-2 has to contain in some sense fibonacci n-1 in order to wrok but it isn't there yet.

I suspect you wanted to write: "since fibbonacci n-1 has to contain in some sense fibonacci n-2"
If I'm right, then you will see from the example below, that actually fibonacci (n-2) will be called twice for every recursion level (fibonacci(1) in the example):
1. when executing fibonacci (n-2) on the current step
2. when executing fibonacci ((n-1)-1) on the next step

(Also take a closer look at the Spike's comment)

Suppose you call fibonacci(3), then call stack for fibonacci will be like this:
(Veer provided more detailed explanation)

n=3. fibonacci(3)  
n=3. fibonacci(2) // call to fibonacci(n-1)
   n=2. fibonacci(1) // call to fibonacci(n-1)
      n=1. returns 1
   n=2. fibonacci(0) // call to fibonacci(n-2)
      n=0. returns 1
   n=2. add up, returns 2
n=3. fibonacci(1) //call to fibonacci(n-2)
   n=1. returns 1
n=3. add up, returns 2 + 1

Note, that adding up in fibonacci(n) takes place only after all functions for smaller args return (i.e. fibonacci(n-1), fibonacci(n-2)... fibonacci(2), fibonacci(1), fibonacci(0))

To see what is going on with call stack for bigger numbers you could run this code.

public static String doIndent( int tabCount ){
    String one_tab = new String("   ");
    String result = new String("");
    for( int i=0; i < tabCount; ++i )
       result += one_tab;
    return result;
}

public static int fibonacci( int n, int recursion_level )
{
    String prefix = doIndent(recursion_level) + "n=" + n + ". ";

    if (n == 0 || n == 1){
        System.out.println( prefix + "bottommost level, returning 1" );
        return 1;
    }
    else{
        System.out.println( prefix + "left fibonacci(" + (n-1) + ")" );
        int n_1 = fibonacci( n-1, recursion_level + 1 );

        System.out.println( prefix + "right fibonacci(" + (n-2) + ")" );
        int n_2 = fibonacci( n-2, recursion_level + 1 );

        System.out.println( prefix + "returning " + (n_1 + n_2) );
        return n_1 + n_2;
    }
}

public static void main( String[] args )
{
    fibonacci(5, 0);
}