An Introduction to Recursion
Recursion happens when a method calls itself. This is a repetitive process that continues and progresses until a base case is reached.
There are two critical parts to a recursive method.
- A base case.
- A recursive call with a progression toward the base case.
Without a proper progression towards the base case, the code could result in infinite recursion. This is where the program continues to call the recursive method without a stopping point.
Consider the following example of a recursive method and a call to that method.
When evaluating a recursive method call, it can be helpful to trace through the method to determine the result and visualize the way the recursive method is functioning. At first, we are unable to evaluate what sum(3) will return, since it is dependent on the value of sum(2), which is dependent on the value of sum(1). Once we have reached the base case, sum(1), the return value of this call can be used to evaluate the return value of sum(2) and so on until we have computed the return value of sum(3) which is 6.
To further illustrate:
sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1
Now, we can work our way from the bottom back to the top to complete the trace.
sum(2) = 2 + sum(1) = 2 + 1 = 3
sum(3) = 3 + sum(2) = 3 + 3 = 6
Your Turn
Let's try it in the Java Playground.
- Predict the output.
- Run the code to determine if your prediction is correct.
- Experiment with this code.
- What happens when you change the initial call to
sum(5)?
- What happens when you change the initial call to
sum(1)?
- What happens when you change the initial call to
sum(0)?
- How can you modify the code to prevent an infinite recursion (a recursive call that doesn't stop)?
- What happens if you change the return statement with the recursive call to
return sum(n - 1)?
- What happens if you change the return statement with the recursive call to
return n + sum(n - 2)?
Complete List of Recursion Tutorials
Resources