What does a recursion interview question actually test, beyond knowing the syntax?
It tests three things. Whether you can turn a problem into a smaller version of itself. Whether you can write the stopping condition so the recursion actually stops. And whether you can see how much work your solution is really doing.
So the first one is the shape of the thinking. A recursive solution has three parts. There is the part that does a little work, there is the part that calls the function again on something smaller, and there is the part that says when to stop. If you cannot say out loud what gets smaller each time, then the recursion will not finish.
def flatten(nested):
output = []
for item in nested:
if isinstance(item, list):
output.extend(flatten(item))
else:
output.append(item)
return output
So the second one is the stopping condition. It is the part that people get wrong most often. It has to cover every case that should not recurse, including the empty case. A function that sums a list and only stops when the list has one item left will fail on an empty list, and an empty list is a real thing that callers pass in.
And the third one is the work. Most recursion questions are really complexity questions in disguise. A naive recursive solution to the number of paths in a grid does an enormous amount of repeated work, and the interviewer's real question is whether you notice that and use a table instead.
So here are the things an interviewer is listening for.
what they are listening for what a bad answer sounds like
---------------------------- -----------------------------------
the base case a function that never returns
the smaller argument a function that calls itself with the
same input
the order of the work a function that forgets to do the
work after the recursive call
the cost a solution that does the same job twice
And the thing that makes recursion interesting is that it maps onto the shape of the data. A list that holds lists, a tree, a folder that holds folders, and a graph are all naturally recursive, because each one contains smaller copies of itself. So the code is short because the idea is short.
And the thing that makes it dangerous is the same thing. The call stack has a limited size, and Python has a limit of about a thousand calls by default, so a recursion that goes a thousand deep will stop with an error.
So the rule to remember is this. Before you write a recursive function, say out loud what gets smaller and what the stopping condition is.
The next two questions in this topic show the simple version and the way to stop the repeated work.