Please enable JavaScript to use CodeHS

Basic Recursion

This tutorial covers basic recursion in Java. The principles of recursion can be applied to any language.

By David Burnham

What is Recursion?

Recursion is a process in which a method calls itself to help accomplish a task. Recursion is essentially another control structure that can often be used in place of a loop.

You will find that nearly all recursive methods can be written as a loop. So why do we use recursion? Even though recursive methods can be written as a loop, there are times when the recursive method is far simpler than a loop.

The idea behind a recursive method is that you try to solve a problem by making the problem progressively easier until it is so easy that the solution becomes trivial. A classic example of this is when solving a factorial problem.

Recall that the factorial of a number is that number times all the numbers below it. For example, 5! can be written as:
5 * 4 * 3 * 2 * 1

Since 4! is 4 * 3 * 2 * 1, you could right 5! as 5 * 4!.

Check out the example below to see how we can use a recursive function to solve factorial problems.

Recursive Method Format

In the example above, you will notice that the method had two parts. The first part was the solution to the simplest case, when n = 1, you can simply solve 1 factorial as 1. This part of the method is called the base case. The base case is the part of the recursive method where you reach the simplest problem and the solution is trivial. Each recursive method will have at least one base case, but some may have more (such as a success base case and a fail base case).

The other part of the method above is the recursive call. This is the part of the method where you call the one simpler version of the problem. In this case, the problem is simplified by calling the number times the factorial of one less. For example 5! can be simplified as 5 * 4!.

Recursion Walkthrough

Let’s take a look at what happens in the recursive call. The first call that is made to the method is factorial(5). Since n is 5, the base case is not met and the second return statement of 5 * factorial(4) is called. Before it can return a value, Java needs to complete the factorial(4) call.

factorial(4) follows the same process as the previous call, this time returning 4 * factorial(3). factorial(3) returns 3 * factorial(2), which returns 2 * factorial(1). When you get to factorial(1), the base case is reached and simply returns 1.

The value of 1 is plugged into the 2 * factorial(1) to complete that return statement and return 2 to the 3 * factorial(2) return statement. In turn, these return statements continue to get satisfied until the final return statement of 120 is hit.

Check out the same example as above with additional print statements.

Finding the Base Case

One of the challenges of recursion is finding the base case. Finding the simplest case may not always jump out at you, but here are a few things to consider.

Oftentimes the base case for mathematical problems is zero or one. You can start by looking at solving that problem.
When looking at other things such as strings or sequences, you still want to think about zero or one, but now it is the length of a string. You will see an example of this in the next example.
Sometimes, there may be more than one base case. You will see this is especially true when looking at solving puzzles, as there will be a success base case and a fail base case.

Your Turn to Try

See if you can set up a recursive method to print a countdown. The method should take a number and when the number gets to zero, print blast off. If it is not zero, print the number and then recursively call the next lower integer.