One of the most intuitive ways to solve problems is through recursion - a way of solving problems by breaking them down into smaller and smaller problems, until you reach a problem that's trivial to solve. Unfortunately, as you know, recursion can be a real pain in the stack, so a lot of work went into rewriting them using iterative style, where instead of using implicit function call stack as in
we are using explicit stack
It doesn’t look too bad for such a simple algorithm, but it’s certainly not as readable as a recursive solution. To address the readability concerns, many developers adopted generator-style implementations that look almost identical to recursive solutions but promised iterative-style performance
Great readability and performance, sounds too good to be true! Let’s try using all of these candidates with
Before checking out the measurement numbers, take a second to guess which implementation is going to be the fastest.
And the results are:
So our naive recursive solution is the winner. It’s actually not that surprising since implicit stack operations are fairly optimized. What’s unfortunate though is that generator solution is significantly slower than iterative approach, so improved readability comes at a high cost.
What does all of this mean? Should we always prefer good old recursion? As always, the answer is “it depends”. Recursion is still susceptible to famous StackOverflow issues and is generally more cumbersome to integrate with algorithms in a way that gives them control over when to stop/resume the traversal. Iterative solutions avoid StackOverflow issues but are harder to write and understand. So unless there is a very good reason for the optimization, generators, thanks to their readability, are a good default choice.
You can play with the code in this article on colab.