# Recursion

Amy Lee
Greenhorn
Posts: 25
Could someone please explain to me, as simply as possible, why the following:

...prints out:

7 performing recursive step
5 performing recursive step
3 performing recursive step
1 performing recursive step
-1 at base case.
1 done with recursive step
3 done with recursive step
5 done with recursive step
7 done with recursive step

...when b(7) is called? I understand how it it from 7 to -1, but I thought it would stop there since there was no return statement after the if statement. What causes it to wrap back up and perform the "done with recursive step" S.O.P. method?

Thanks!!!

Keith Lynn
Ranch Hand
Posts: 2409
Basically, when the recursive call is made, the current state of the method is frozen until the method is finished executing. So the method freezes after n is 7, waiting for b(5) to finish, etc. When you finally reach the base case, then each of the method on the stack that have been frozen, can now complete.

Amy Lee
Greenhorn
Posts: 25
OK, so if it was instead:

...then it would only print to the base case since there is no System.out.println() method after the recursive call anymore, right? In other words, since there's no print or return method, there is no place for the method to "unleash itself" visually, right?

Thanks.

Keith Lynn
Ranch Hand
Posts: 2409
Right. After the recursive call returns, it won't print anything.

Amy Lee
Greenhorn
Posts: 25
Beautiful - thanks for helping me to understand!

David Harkness
Ranch Hand
Posts: 1646
Originally posted by Amy Lee:
I thought it would stop there since there was no return statement after the if statement.
Just to be clear, every method returns to the method that called it (or throws an exception, another form of returning). You only need to use the return keyword if you want to return a value or return early.

If you don't specify a return anywhere in your method, it returns when the end of the method is reached. In your case above, when n <= 0 the if test passes, the message is printed, the else block is skipped, and finally the method returns to the calling method.

As each method invocation is kept on the stack, recursive calls are considered to be different method calls in the preceding discussion.

Removing the third println() call doesn't change this fact. It only means that after the recursive call returns to the b(n-2) line, there's nothing more for the method to do so it returns to its caller. The same call chain is performed, however.

For kicks, add another recursive call to b(n-1) immediately after the call to b(n-2).