One of the most common reasons people fail tech interviews, is they just don’t really understand recursion. They’ve learned about recursion, used it to solve a few problems as required in their CS courses or self study, but they never really understood it fully. The best programmers will sense when to use recursion and use it to make problems easy.
Let’s imagine this job interview scenario to appreciate the power of recursive thinking:
Interviewer: “Problem solving is important in this job. I’d like you to try solving this puzzle. You have five minutes.”
You are presented with a Towers of Hanoi game with 8 disks:
| Towers of Hanoi (try it out) |
|---|
| Goal: Move all the disks to one of the empty pegs. Rules: 1. Only one disk can be moved at a time. 2. A larger disk can never be put on top of a smaller one. 3. Full rules on wikipedia |
After a bit of playing around, you realize there’s just not enough time to solve the puzzle. You’re not going to get the job. (It’s not fair! If only there were more time!).
What if you had a cheat code?
You: “I’d like to enter a cheat code.” (Hey, you’ve got nothing to lose).
Interviewer: “Ok, sure. What is it?” (Is this actually working?)
You: “Uh…‘recursion, recursion, recursion’?”
Interviewer: “Oh ok, nice cheat, let’s reset the puzzle and change the rules a bit. You won’t have to move one disk at a time anymore. We’ll let you pick up a whole stack of up to 7 disks and move them all at once. The only caveat is that when you move a stack you can’t have a smaller disk on either of the other two pegs.” (Did that really just happen?)
Now, it seems that you can solve the puzzle in just a few steps:
| Post cheat code solution |
|---|
| 1. Move the top 7 disks to the first free peg in one step. |
 |
| 2. Move the remaining disk to the second free peg. |
 |
| 3. Move the entire stack of 7 disks on top of the largest disk. |
 |
Is the interviewer really going to accept this? A 3 step solution?
You explain it, and play it out on the game board.
Interviewer: “Great. Looks like you’re an excellent problem solver. Let’s move on.”
This would never happen in a real interview, right?
It’s doubtful that anyone’s actually asked to enter a cheat code; but, in some sense, it happens every day.
In a technical software interview, the problem wouldn’t be to simply solve a game of towers of hanoi, the problem would be: “Write a program to solve towers of hanoi.” The ‘cheat code’ in the above example is really just the recursive assumption for the towers of hanoi problem (assume we can solve a game of towers of hanoi with n - 1 disks). Technical candidates who use the recursive assumption have that cheat code and those who don’t know about it struggle.
Tech Interview Tip: Let the recursive assumption guide you
The secret that the best technical interview candidates use is that they rely on the recursive assumption. Once they sense a problem might be solved recursively, they’ll clearly state the assumption (either in their minds or explicitly out loud) and they’ll persevere in finding ways to use it to make the solution simpler.
What is the recursive assumption anyways?
If you’ve never heard of the recursive assumption (aka inductive hypothesis), then check out the FAQ below for some resources to learn more about recursive problem solving.
As a reminder, or super quick intro:
The recursive assumption is when we assume that our program already works on smaller inputs.
Some examples:
| Sum the first n natural numbers |
|---|
| Problem: Define a function sum1upto(n) which takes an integer >= 1, n, and sums all the numbers from 1 up to n (i.e. computes 1 + 2 + 3 + .. + n). |
| Recursive assumption: When defining sum1upto(n), assume sum1upto(n - 1) correctly returns the result of 1 + 2 + … + (n - 1) |
| Compute permutations |
|---|
| Problem: Given a list of unique elements, define a function which will compute all permutations of those elements. |
| Recursive assumption: When defining permutations(listOfElements), assume that permutations(smallerListOfElements) will return all the permutations of smallerListOfElements. |
If you have trouble understanding what the recursive assumption is, or why the recursive assumption works, try learning about mathematical induction and its relation to recursion (resources given in FAQ at the end of the article).
So how would a top candidate handle Towers of Hanoi?
When a top candidate is asked to write a program to solve the towers of Hanoi, their thinking is similar to the following:
Solve the base case: They make sure the function has a terminating condition by hard coding the solution for n=1. (“if n = 1, I’ll just output ‘move from peg 1 to peg 2’ and be done.”)
Concretize: Rather than worry about a game of n disks, pick say n = 5 to make the problem easy to think about.
Use the recursive assumption: They imagine they had a program that would tell them the instructions to solve towers of Hanoi for n = 4 disks. They will be very clear about what the recursive assumption gives them, e.g. “SolveTowersOfHanoi(…) returns a list of moves (e.g. peg 1 -> peg 2, …) that will solve any instance of towers of hanoi with fewer than 5 disks.
Solve the problem: They come up with a solution to the simplified problem. After thinking similar to that from the interview above, they come up with something like:
“I’d use the solution for n = 4 disks to get the list of moves to move the top 4 disks to the first free peg.”
“Then, I’d move the last disk from the initial peg to the second free peg. So I’d add ‘move peg 1 -> peg 3’ to my list.”
“After that, I’d use the solver again to get the instructions to move the 4 disks on top of the larger one. (It would be ok to reuse the solver because the largest disk could never invalidate the solution the solver gives me. One key insight is that the solver can create instructions for moving the 4 disks from peg 2 to peg 3 by relabelling the instructions to move from peg 1 to peg 2 (take the instructions and change all 1s to 2s, all 2s to 3s, and all 3s to 1s).
I’d return the whole list of moves.
Re-generalize - Replace 5 with ‘n’ and 4 with ‘n - 1’. Replace ‘a program that would solve towers of Hanoi with n-1 disks’ with a recursive call to the same function being written.
FAQ
Where can I learn more about recursion and induction?
The most recommended books for learning about recursive problem solving are probably Structure and Interpretation of Computer Progams or How to Design Programs. The dynamic programming section of books like Introduction to Algorithms and Algorithm design manual are good too. Godel Escher Bach is an interesting non-textbook that might help you think recursively.
How do I know if I already understand recursion well enough?
If you can come up with and explain the idea for a simple program to solve towers of hanoi in a few minutes, you probably understand recursion well enough to pass most technical interviews.
Beyond that, a programmer who really understands recursion will:
- Know of the ‘recursive assumption’ (aka inductive hypothesis) and commonly consider using it when presented with a problem.
- Understand the relationship between mathematical induction and recursion.
- Describe algorithms recursively for the simplicity of description (even when the actual recursive algorithm is inefficient).
- Be able to trace recursive programs.
- Understand the drawbacks of recursion in practice.
- Have practice with and quickly be able to find solutions to recursive problems.
Where can I find practise problems?
The divide and conquer and dynamic programming sections of geekforgeek or hackerrank are useful for finding problems to practise this technique on. Since recursion is so closely related to induction, working through induction problem sets is also useful. The blue eyes problem is a good logic problem to test if you truly understand induction.
I could already come up with the idea for a towers of hanoi solution in a few minutes but I’m still not able to pass my interviews. What else could it be?
There could be many other reasons. Here’s a few things you can do:
- Read the rest of the articles in ‘Why you failed your tech interview’. The series is meant to help you prepare for interviews and to help you find out why you’re failing.
- Subscribe for future episodes, we’re still adding to the series.
- Comment here or contact @fizzbuzzed on twitter and share your interview story. Fizzbuzzed will try to help you identify the gap in your knowledge and might even end up writing an entire article just to help you.
What about this solution to the interviewer’s question post-cheat code:
1. Move the top disk to one of the free pegs.
2. Move the 7 remaining disks to the second free peg.
3. Move the 1st disk on top of the remaining disks.
Would it work?
This would not work because your second step violates the interviewer’s caveat. You’re not allowed to move all the 7 remaining disks onto the second free peg because the other free peg must not contain any disks that are smaller than the ones in the stack.
Why is recursion so important in an interview?
Recursion is fundamental in CS education.
During a traditional CS education at a top university, students will be taught how to think recursively in the first year. Over the next three to four years, they will consistently use this ability to solve problems. Upon graduation, the top students will have encountered and solved recursive problems so many times that it is second nature for them to consider a recursive solution as a starting point when they see a new problem.
You will more than likely be interviewed by at least one of these people when you apply for a Big 4 tech position. Recursion is one of the first things they try when they encounter a new problem. If you’re not immediately considering a recursive solution, they’re going to question your fundamentals. Even a hint of shaky fundamentals is enough to get someone rejected. At top tech firms, hiring a candidate who won’t perform is considered the ultimate hiring mistake.