Recursion

Vocab Bar
Recursion Recursion is a programming technique in which a method calls itself in order to accomplish a goal.
Termination Condition The condition that causes the method to end.

Recursion is a very popular programming technique that can be used to solve large/complex problems. A recursive method has two key elements:

  1. A recursive method calls itself (sometimes multiple times, depending on the scenario).

  2. A recursive method has a termination condition (or multiple, depending on the scenario).

For example, let’s say you wanted to print the factorial of a number (which is the product of an integer and all the positive integers below it). The iterative implementation (using a for loop) for this problem would look like this:

    public static int factorialIterative(int n) {

        int value = 1;

        for (int i = n; i > 0; i--) {

            value *= i;

        }

    }

Now, the recursive implementation for this problem would look like this:

    public static int factorial(int n) {

        // termination condition

        if (n == 0) { 	

            return 1;

        }

        // re-calls method

        return n * factorial(n-1);

    }

The above two statements output the same value. What happens if we make the method call factorial(5) (the recursive method)? Let’s walk through it step by step.

Value of n Return statement
5 return 5 * factorial(4)
4 return 4 * factorial(3)
3 return 3 * factorial(2)
2 return 2 * factorial(1)
1 return 1 * factorial(0)
0 return 1

The above table still has lots of method calls, which means it is not fully simplified. Here is a simplification of the table:

Value of n Return statement
5 return 5 * 4 * 3 * 2 * 1 * 1
4 return 4 * 3 * 2 * 1 * 1
3 return 3 * 2 * 1 * 1
2 return 2 * 1 * 1
1 return 1 * 1
0 return 1

Finally, let’s simplify one more time:

Value of n Return statement
5 return 120
4 return 24
3 return 6
2 return 2
1 return 1
0 return 1

Based on the above table, factorial(5) returns 120. The reason the method did not continue calling itself was the termination condition, which returned 1 when n == 0. The termination condition is crucial to recursion – without the termination condition, the code results in an infinite loop.

One important usage of recursion is recursive backtracking – when you continue to try solutions until you reach an issue, at which point you return to a simpler solution and continue the program. For example, let’s say you wanted to test if a maze was solvable. A program could test multiple routes through the maze, and determine whether or not the maze had a solution. A maze-solving recursive method would contain the following parts:

  1. A termination condition to see if the end of the maze has been reached.

  2. Multiple if statements, each containing a recursive call checking whether the next space is open. (You check whether you can move up, down, left, or right.) If true, return true (thus the method returns a boolean).

  3. A “flag” that marks the positions that you visited with a special icon so you don’t revisit a path twice.

  4. A backtrack statement at the end of the method that allows you to backtrack from a dead-end path (shown in below gif).

  5. Multiple parameters to keep track of the current x position, the current y position, and the current maze.


A program solving a maze recursively. Source

Although recursion is often difficult to understand at first, with enough practice, you can master this useful technique.

Lesson Quiz

1. What happens if a recursive method doesn’t have a termination condition?

a. The method results in an infinite loop.
b. Nothing – it works normally.
c. The method causes a null pointer exception.
d. The method stops at compile-time.

2. Is it possible for a recursive method to have multiple termination conditions?

a. Yes
b. No

Written by Chris Elliott

Notice any mistakes? Please email us at [email protected] so that we can fix any inaccuracies.