Re:Tail recursion, but modulo cons
by seanhunter on Wednesday March 02, 2022 @10:09AM
(#30528189)
This is probably the most "hackernews" conversation I've ever had but as far as I've ever seen the term used, "memoization" is not restricted to temporarily tabling the results during a single run of the algorithm but used to mean any caching of results of an expensive pure function for future use. You seem to call that a "semi-permanent database of answers". Here is the original memoization paper [1] where he is using a constant-time table lookup exactly as I envisage in this case rather than only tabling results during a single invocation of the algorithm. Ironically he uses it to memoize a recursively-defined factorial function.
[1] https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...
At the risk of stumbling into the No True Memoization fallacy, I wouldn't consider that memoizing -- at least not in the dynamic programming sense. To get O(1), you're not temporarily tabling the results during a single run of the algorithm; rather you're building a semi-permanent database of answers and (effectively, in an amortized sense) discarding the algorithm altogether. I think that's formally known as the "just Google it" approach to optimization. :) From a DP perspective you can get O(N) from memoization on open-form Fibonacci, and no gain on open-form factorial, because the lookup table is ephemeral.