TL;DR: re-write the recursive function so that the 1st call doesn’t need to wait for the result from the remaining calls, all the way down to the base case, before returning.
Recursive functions continue calling themselves until the base case is hit - and then they return. The continued calls keep pushing frames onto the stack and can lead to a stack overflow for large inputs. Some languages include an optimization that cleans this up, provided that the function is written in a way that it doesn’t need to wait for the results for all the other recursive calls to resolve to return.
Overview Memoization or memoisation is a method used to optimize programs. Usually, at least in my experience, it’s one of the first topics introduced when dynamic programming algorithms are being discussed. With a quick google search you can find the Wiki or a trillion other blogs about it - most will show the canonical example - the “hello world” of the topic - that is, using memoization to optimize a recursive implementation of a function that generates the n-th Fibonacci number (or sometimes a function computing factorials).
We’ve all got a little more time on our hands lately due to social distancing and COVID-19 (unless you have young children). I’ve been partly entertaining myself by learning new programming languages and frameworks, and also with some programming puzzles on sites like HackerRank.
I found one problem I ran into recently particularly interesting, and I enjoyed figuring it out (read: drove me crazy for a bit). This post is a write up of the problem and the solution that I ended up with.