It depends a little bit on what the acceptable answer is. If it's "stream/generate a list of possible strings", then the length of that list is probably O(2^n),

It depends a little bit on what the acceptable answer is. If it's "stream/generate a list of possible strings", then the length of that list is probably O(2^n), so the fact that my recursive descent thing is exponential doesn't actually matter that much asymptotically. If you memoized it, the memo structure caching the suffixes would become massive and you'd spend just almost as much time looping the results from it as you would just walking down the tree, so you might as well save yourself the memory and just walk down the tree. Like, the length of the cached answer is more or less the same as the runtime of just doing the recursion, so you're not actually saving much of anything by memoization, and you're wasting a whole lot of memory. I guess you could instead return some kind of fancy "prefix DAG" containing all possible strings, and that would be faster. But then you're just making the caller walk that tree instead of you doing it yourself, so you're really just shuffling the runtime around, not really saving much. However, if the answer is "count the solutions", then yeah, memoizing would speed it up MASSIVELY. That's a good little Project Euler style problem, actually (though not a terribly tricky one), because you could make the input large enough that naive recursive descent wouldn't work. I haven't quite thought through what going full-on DP and turning the recursion upside down would do, but I assume it would work just fine. But given that the number of possible solutions is a massive O(2^n) (probably, anyway), that puts a floor on the runtime you can't algorithm your way out of. Might as well go with the cheap recursive descent. I think, anyway :)