Kotlin
Java

Recursion
Java

Created By: Geoffrey Challen
/ Updated: 2021-10-24

This lesson introduces a new problem solving strategy called recursion. Recursion represents an exciting new addition to our algorithm toolbox. It can be hard to wrap your head around at first. But we'll go slow and, as always, use lots of examples. What are we waiting for?

What is Recursion?

So far we've looked exclusively at iterative algorithms that solve a problem by repeating a series of steps. The implementations of iterative algorithms are characterized by the use of looping constructs such as for and while.

Recursive algorithms work differently. They solve problems by breaking them down into smaller yet similar pieces, and the reassembling the solutions to the smaller problems into a solution to the larger problem. This will make more sense once we look at some examples!

But let's start by examining both the general definition of recursion and how recursion is used in computer science.

Go through the Wikipedia definitions of recursion—both the general case and the computer-science specific case.

Iteration v. Recursion

Learning to think recursively takes time and practice. You'll get both!

But let's start by comparing and contrasting an iterative and recursive solution to the same problem. That will both help us start to learn to think recursively, and identify the differences between the two approaches.

Is A Palindrome: Iterative

Let's write an algorithm to determine if a String is a palindrome, that is, whether it reads the same forwards and backwards. First, let's design an iterative algorithm:

Show how to implement palindrome iteratively using a for loop. (Don't just reverse the String and then compare them.)

Is A Palindrome: Recursive

Next, let's try and approach the problem recursively.

What does that mean? A recursive solution tries to make the problem smaller in each step until it is trivial to solve. Let's think about how to apply that to palindrome detection.

Set up and solve the recursive palindrome problem. Point out that the empty String or any String with length 1 is a palindrome. Next, point out that, if the first and last characters in a String are the same, it could be a palindrome. And to find out, we need to figure out if the string between the first and last characters is a palindrome, which is a smaller problem.

Compare and Contrast

To wrap up, let's put the two approaches side by side and discuss the differences.

Compare and contrast the two palindrome approaches.

Recursive Strategies

A recursive implementation contains a function that calls itself. At first, this may seem really weird. But the trick is not to not let that throw you, and to just consider what happens.

Successful recursive algorithms must do three things correctly:

  1. Make the problem smaller. If you don't do this, the problem never gets small enough to solve!
  2. Solve the smallest problem. This is known as the base case.
  3. Combine the results properly. This is required to arrive at a correct solution.

Let's examine another recursive implementation. We'll identify the three requirements enumerated above, and trace its execution.

Trace through the countLetter method.

Factorial

The next homework problem has you complete a recursive implementation of factorial. For reference, here is the iterative implementation that matches the homework problem:

To complete the recursive implementation, consider the following questions:

  1. What is the smallest problem, or the base case? (You know that the factorial of 0 is 1).
  2. How do you make the problem smaller and combine the results? (You know that the factorial of n is n * n - 1).

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough