My point is that the naive approach to the problem doesn't even need to use recursion, nor does the final solution, even if the path towards reasoning about the

My point is that the naive approach to the problem doesn't even need to use recursion, nor does the final solution, even if the path towards reasoning about the complexity calls on recursion. I prefer a narrower scope in definition for memoization, but I accept that there are many who would prefer the broader definition. I think perhaps there is even a grey area around the term, and cache, and working memory, and more. Is it no longer memoising if you're using it to build an index table? Is a cache implementation of an @memoize function decorator still memoising? IDK, it's not my intention to split hairs here. For what it's worth, I reread the 1975 paper about the linear-space version of LCS, they do not mention memoization, even though recursion is used in both the algorithm pseudocode and in the complexity analysis. The term memoisation was coined in 1968. https://dl.acm.org/doi/10.1145/360825.360861 https://dl.acm.org/doi/10.1145/360825.360861