How to approach and think through recursion
I recently started searching for my next opportunity (hit me up if you love your workplace!), and noticed that many interview questions center around recursion. In fact, 4 out of 12 companies I have interviewed with recently have asked a recursive problem during the interview process.
Chances are that you have come across an interview question which should be solved recursively at some point in your career.
Though I understand recursion much better now, I struggled quite a bit with it when I was first learning it 3 years ago. Here are some tips I’ve gathered by working through dozens of recursion problems in preparation for my job search.
Before we begin, this article assumes a basic understanding of what recursion is. Note: any question that can be solved recursively CAN also be solved iteratively. However, for certain types of problems, the recursive solution is cleaner, more readable, and easier to implement. I’m here to talk about how I think through recursion in a way that makes sense to me, and hopefully some of you might find my approach helpful too.
I. How to identify problems for which a recursive solution makes sense
In a nutshell, recursion is a way of arriving at a solution by breaking down the input into smaller and smaller pieces until it can no longer be broken down. The final output is calculated by putting together the output of these calls with the “smaller” inputs.
If the input of a question consists of unequally nested values and the output requires traversing the input, it’s a good indication that recursion is needed.
Examples of interview questions I’ve seen include traversing a nested hash such as:
entertainment_materials = {romance: {comedy: {movies: ['50 first dates', 'eternal sunshine'],books: ["he's just not that into you :("],articles: ['How I automated dating with a Tinder Bot']}},action: {movies: ['LOTR', 'Transformers 1'],superhero: {movies: ['Wonder Woman'],books: ['Ironman comic', 'Batman comic'],batman: {movies: ['Lego Batman']},spiderman: {movies: ['Homecoming']}}}...}
or nested arrays such as:
[7,[[1]], [1,[2,[3]]], 3, [4, 5], 9]
Of course, this type of problem is by no means inclusive. Common algorithms like binary search, merge sort, and tree traversals are implemented with recursion.
To determine whether recursion is the right approach, I ask myself:
“Does it make sense to reach an output by calling a method over and over with some sort of ‘truncation’ to my original input?”
And
“Can this original input be ‘truncated’ in a reasonable way to reach an output?”
In this article, I will walk through a problem with nested hash as input. Let’s say that I’m supposed to find how many movies, books, and articles there are in the ‘entertainment_materials' directory. Also, let’s say our solution should be in the format of: {books: 0, movies: 0, articles: 0}.
II. How I write up my solution
When I encounter recursion, I ask myself:
- What’s the base case?
- How do I get to the base case?
- How do I aggregate data through the call stack?
1. What’s the base case?
I think of base case like this:
“The base case is when we reach an input for which we know what the output would be.”
The base case is thus the condition which terminates recursion.
In the example here, the base case is when the input has nothing for us to loop through. It could be because the input is nil (or an empty hash). When that happens, we know the output is {books: 0, movies: 0, articles: 0}.
In all recursive problems involving arrays that I have seen, the base case is when input_array.length <= 1.
Thus, the solution to this problem might start with something like:
def count_materials_by_type(directory)return { books: 0, movies: 0, articles: 0 } if directory.nil?
end
2. How do I get to the base case?
Getting to the base case is important. Otherwise, we’ll have infinite recursion.
In many array problems, the way to get to the base case is either removing the first element, last element, or splitting the array in half.
In this nested hash problem, it makes sense to loop through each key/value pair. If the value is another hash, we need to do a recursive call with that “smaller” hash.
def count_materials_by_type(directory)return { books: 0, movies: 0, articles: 0 } if directory.nil?
directory.each do |key, value|if value.is_a?(Hash)count_materials_by_type(value) # ensures that input into the recursive call keeps "shrinking" until it gets to the base caseendendend
Of course, our method doesn’t do anything yet besides returning the directory itself.
In our example, we need to increment the count of books, movies, and articles every time we encounter those keys in the directory. Let’s adjust the method to define a variable which tracks this information
def count_materials_by_type(directory)result = { books: 0, movies: 0, articles: 0 }
return result if directory.nil? || directory.empty?
directory.each do |key, value|if key == :books || key == :movies || key == :articlesresult[key] += value.lengthend
if value.is\_a?(Hash)
count\_materials\_by\_type(value)
end
end
resultend
This still doesn’t work, and if I run it, I get
{ books: 0, movies: 0, articles: 0 }
The reason is because I’m resetting the result to {books: 0, movies: 0, articles: 0} in each call stack. Thus, I’m not actually tracking or doing anything with the data across the call stack.
Now, we get to the meat of our problem.
3. How to aggregate data across the call stack**?**
Unfortunately, this one comes with practice. However, the good news is that the more you practice this type of problem, the more intuition you’ll build until you kinda just know.
The way to aggregate output from call stacks depends on the problem. Read this article for some good examples.
In this particular example, the way to do it is passing in the result hash back into the method.
def count_materials_by_type(directory, result = { movies: 0, books: 0, articles: 0})return result if directory.nil?
directory.each do |key, value|if key == :books || key == :movies || key == :articlesresult[key] += value.lengthend
if value.is\_a?(Hash)
count\_materials\_by\_type(value, result)
end
end
resultend
The return value is the result hash with count of movies, books, and articles. Whenever we encounter another hash as value in the loop, we pass in that smaller hash to the method again. We won’t hit the return value until the input has no nested hash. The result returned by each call stack contains updated count for movies, books, and articles.
Here you have it, my thought process for recursion:
- What’s the base case?
- How do I get to the base case?
- How do I aggregate data across the call stack?
Again, just like any other skills, practice makes perfect. So keep on coding and go nail that interview! :)