Overview

Recursion is a topic that you will use from when you begin to learn how to code to when you are building complex programs to serve millions of people. Therefore, it's essential to have a fundamental understanding of how it works!

What is Recursion

The above method will print out "This method will never end!", before then calling itself, printing out the message and the call itself again, and so on. This is known as infinite recursion, where the recursive method never ends. This is because no base case is identified. Take a look at the method below: In the method above, the recursive function has a way to stop. The recursion stops when n is equal to 0. This is known as a BASE CASE. We can set more than one base case for when to stop the recursion.

Why Use Recursion?

We would want to use recursion to solve a problem where the solution to the problem involves a repetitive process.

For example, let's say you wanted to predict the interest you would gain on an fixed-interest investment over x number of years? We would make a recursive call to the method for each year as the investment compounds, with the base case being when we reach the last year to forecast for.

How to Trace Recursive Methods

Tracing recursive methods is an important part of understanding how recursion works, how to design a recursive function, and is extremely valuable when errors are found in your methods.

In Java, we use something called the call stack to keep track of all method calls made since the recursive method was first called. In programming, a stack is how we organize data, where we can only add/remove items from the top of the stack.The same applies to call stacks for recursive methods.

When we are executing a method a, which calls another method b, the previous method a is placed on this call stack along with information about where it was called from. This allows the run-time compiler to know where to return to when the current method b is finishing executing. When method b is finished, the run-time "pops" method b off the call stack and executes the next method on the stack, method a.

As shown above, when a method calls itself, the new method call is added to the top of the call stack, like stacking dishes in the sink to clean. When each recursive call is being processed, all execution of the current method is paused, resuming only after the previous method is executed and no other recursive call is made.

But how can we show whats happening in a recursive call? We can use a diagram to trace the factorial() method as shown below: The diagram shows the tracing, with the call stack upside down, where the bottom of the stack is the beginning of the top, and the most recent recusrive call in the bottom box for a call made to factorial(5). Once factorial(0) executes, it matches the base case and returns 1. The value is substituted back into the previous method call as we work our way back to the bottom of the stack, or to the first call, factorial(5).

Whew! Nice job getting through that! Here's a funny recursion meme to remind you to always set up a base case in your methods!