Recursion
‘To understand recursion, you must first understand recursion’ — a recursive joke
Learning Objectives
By the end of this lesson, you should be able to:
- Identify the main elements that make up a recursive algorithm.
- Analyze how a complex problem can be solved recursively.
The concept of recursion is a little bit mind-blowing when you first hear about it. It is this idea of solving a problem by continually breaking it down into smaller versions of the same problem. At some point, the smallest version of the problem becomes trivial to solve, and the solution from that simpler problem can be passed back up (to help solve the more difficult problem). As each successively more difficult problem is solved, the original complex problem can be solved!
In particular, we solve a complex problem recursively by breaking it down into simpler pieces that involves the following steps:
- Reduction: reducing the problem into a simpler problem of the same type.
- Base case: solving the simplest version of that problem.
If all of this is hurting your head, do not fear! We will walk you through some intuitive examples to show you how it works.
Before walking you through some intuitive example problems, I want you to have the following three questions in the back of your mind whenever you see a problem that you are trying to solve recursively:
- How do I break down this problem into a smaller version of itself?
- How do I use the answer from the smaller problem to solve the larger problem?
- What is the base case (the simplest version of the problem) and its solution?
In the next section, we are going to walk you through some examples of recursive problem-solving so you begin to get a feel for how it works!
Example 1: Movie Theater Seating
Suppose you are seated in a seat in a movie theater, but the movie theater for some strange reason is missing seat numbers. You want to figure out what your seat number is. Suppose the people in the theater are seated as follows (and you are in the seat indicated by the dark orange circle):
So, how do you figure out your seat number in a recursive fashion? Let's start by answering the three essential questions for solving problems recursively...
- How do I break down this problem into a smaller version of itself?
Ask the person diagonally in front of you their seat number. This is the same problem for that person, but it should be simpler to solve, since that person is closer to the start of the row. - How do I use the answer from the smaller problem to solve the larger problem?
If you know the person in front of you's seat number, you know that your seat number is that person's seat number + 1. - What is the base case (the simplest version of the problem) and its solution?
If the person is at the end of the row, they know their seat number is 1.
Breaking the Problem Into Simpler Problems Until Base Case
To solve this problem recursively, each person asks the person diagonal (in front and to the left) to them what their seat number is—all the way to the person who is seated at the end. The person seated at the end knows their seat number is 1!
Using Solution from Simpler Problem to Solve More Complex Ones
The person at the end reports their seat number to the person that asked them. The person who asked the question knows that their seat number is 1 more than the seat number of the person they asked. This process goes on until the first person who asked the question can solve for what their seat number!
the Complete Animation
We can see the whole recursive process for solving this problem in the following animation!
Some Pseudocode
The following is some psudeocode that shows how this problem would be solved in code. The code itself is not functional (will not work if you run it) but is meant to give you a sense of how to translate the above solution into code.
def findSeatNumber(person):
if person.isAtEnd():
return 1
return findSeatNumber(person_diagonally_in_front) + 1
Example 2: Delegation of Tasks (Needle in a Haystack)
Suppose there is a 'needle' within a haystack that you are searching for. Also suppose that you have a bunch of friends who are offering to help you search for this needle.
How do you recursively determine whether or not the needle is in your haystack? Let's start by answering the three essential questions for solving problems recursively...
- How do I break down this problem into a smaller version of itself?
Split the haystack in half and delegate the task to two others to solve this smaller version of the same problem. - How do I use the answer from the smaller problem to solve the larger problem?
If any person you delegated the smaller task to reports they found it, then you can report you found it too! If not, then you report you did not find it. - What is the base case (the simplest version of the problem) and its solution?
The haystack has only one or two hays in it. If one of the two pieces in the haystack are the need, then the person can report they found it. If not, they report they have not found it.
Breaking the Problem Into Simpler Problems Until Base Case
From the answer to the first question, we see each person splitting the haystack into half and delegating the work of searching to two other volunteers. Presumably, the haystacks at the bottom are tiny enough (1 or 2 hays large) that it is easy for the individuals to find/not find the needle.
Using Solution from Simpler Problem to Solve More Complex Ones
According to the second answer to the questions above, as soon as the volunteers who have been assigned work know their answer, they report their answer to those who assigned them the task. The person knows that they have found the haystack if any one of the people they delegated the task to reports that they have found the needle. This goes upward the chain of command.
the Complete Animation
We can see the whole recursive process for solving this problem in the following animation!
Some Pseudocode
The following is some psudeocode that shows how this problem would be solved in code. The code itself is not functional (will not work if you run it) but is meant to give you a sense of how to translate the above solution into code.
def searchNeedleInHaystack(haystack, needle):
if len(haystack) == 1 or len(haystack) == 2:
return needle in haystack
flag = searchNeedleInHaystack(haystack[0:len/2]) or searchNeedleInHaystack(deck[len/2:len])
return flag Some Related Questions
Here are some important, relevant questions that will be addressed in future articles:Summary
In summary,
- Recursion is a powerful programming tool where complex problems can be solved by breaking the problem into smaller versions of itself.
- You can solve a problem recursively by figuring out 1) how to break down a problem into simpler problems of itself, 2) how to use the solution from the simpler problem to solve the more complex problem and 3) the solution to the base case (simplest version of the problem).
Some Exercises
Hopefully you have started to see how recursion works through the above example problems! Thinking recursively is quite challenging, and it takes quite a bit of practice to think in this way. The following are a few practice problems for you to solve to give it a try!
Exercise 1: Climbing stairs.
https://leetcode.com/problems/climbing-stairs/Suppose you can either take 1 stair or 2 stairs at a time. Count the number of different ways you can take n stairs.
Exercise 2: Computing the factorial.
Write a recursive function that takes in an integer n and returns n!.References
Karena Cai
Technical blog writer
I am on a mission to explain complex ideas with tons of pictures, intuitive explanations, and examples.
