Recursion and the call stack

Why does recursion feel harder than a loop?

Because a loop keeps one set of variables and recursion keeps one set per call, and the second set is invisible in the source. The fix is to stop tracing the calls in your head. Look at the picture of the stack instead: each frame holds its own copy of the arguments and locals, the call that is running is the top one, and everything below it is paused mid-line waiting for a value. Once you believe the recursive call returns the right answer for a smaller input, the only line you have to reason about is the one in front of you.

How deep can Python recurse?

About a thousand frames by default. sys.getrecursionlimit() reports the exact figure and sys.setrecursionlimit() changes it, but raising it to walk a huge structure trades a clean exception for a possible crash of the interpreter, because the real C stack has its own limit. In practice: recursion over a balanced tree is fine, because ten thousand balanced nodes are only fourteen levels deep. Recursion over a linked list or a path-shaped graph is not, because there the depth is the length of the input.

When should I convert recursion to an explicit stack?

When the depth can reach the input size, and when an interviewer asks for it. The conversion is mechanical: the frames become entries you push onto a list of your own, and the loop pops one at a time. You pay for it in readability, and you have to add a guard the recursive version does not need, because the same node can be pushed twice before it is ever popped. Say that you can do it, and do it if the input can be a chain of a hundred thousand nodes.

Does memoisation change the complexity or just the constant?

The complexity. Naive Fibonacci makes a number of calls that roughly doubles with each step of n, because the two branches never learn anything from each other. Caching answers turns the tree into one call per distinct argument, so the work becomes linear in the number of distinct subproblems. That is also the definition of dynamic programming, which is why the two ideas are taught together: memoised recursion is top-down DP.

What does an interviewer actually listen for?

Three things, and they are all sentences rather than code. The base case, stated before you write the recursive call. The cost, argued from the shape of the recursion tree rather than asserted. And the space, named as the maximum depth of the stack, not the number of calls. A candidate who says “this is O(n) time and O(h) space, where h is the height of the tree, and on a skewed tree h is n” has answered the follow-up before it was asked.