Recursion confusion with multiple return

Question

I'm still wrapping my mind around recursion, and I think I get basic ones like factorial. But I'd like further clarification when the return statement is a little more complex like on the following snippet:

/**
 * @param n >= 0
 * @return the nth Fibonacci number 
 */
public static int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return 1; // base cases
    } else {
        return fibonacci(n-1) + fibonacci(n-2); // recursive step
    }
}

In the return statement, does the fibonacci(n-1) completely recur through, before going down the fibonacci(n-2) step (does that make sense)? If so, this seems very difficult to envision.

Answer 1

Yes, one invocation will recurse all the way down and return, before the other one starts executing.

The order of invocation in Java is well-defined: fibonacci(n-1) goes before fibonacci(n-2).

Edit: Since the question originally included [C++] tag, here is the C++ part of the story: one of the two invocations still has to complete before the other one starts to run, but which one, fibonacci(n-1) or fibonacci(n-2), is unspecified.

Since the function has no side effects, it does not matter which of the two invocations gets to run first. The only thing that is important for understanding of recursion is that both invocations must complete, and their results must be added together, before the invocation at the current level returns.

Answer 2

It isn't much more different than calling a different function than itself. It needs to finish before the calling function can do anything with the result.

finobacci(0); // ==> 1 (since n is zero, the base case is to return 1)
fibonacci(1); // ==> 1 (since n is one, the base case is to return 1)

Now lets try 2 which is not the base case:

fibonacci(2);                // == (since it's not the base case)
fibonacci(1) + fibonacci(0); // == (both calls to fibonacci we already haver done above)
1 + 1                        // ==> 2

So in reality what happens is that the call to fibonacci2 waits while each of the two recursive calls to finish, just like a function that does System.out.println would wait until it had printed the argument before continuing to the next line. Recursion isn't that special.

Trivia: This is the original series from Fibonacci himself. Modern mathematicians start the series with n as the base case result making the series 0, 1, 1, 2, ... rather than 1, 1, 2, 3, ....