This is a question I read on some lectures about dynamic programming I randomly found on the internet. (I am graduated and I know the basic of dynamic programming already)
In the section of explaining why memoization is needed, i.e.
// psuedo code
int F[100000] = {0};
int fibonacci(int x){
if(x <= 1) return x;
if(F[x]>0) return F[x];
return F[x] = fibonacci(x-1) + fibonacci(x-2);
}
If memoization is not used, then many subproblems will be re-calculated many time that makes the complexity very high.
Then on one page, the notes have a question without answer, which is exactly what I want to ask. Here I am using exact wordings and the examples it show:
Automated memoization: Many functional programming languages (e.g. Lisp) have built-in support for memoization.
Why not in imperative languages (e.g. Java)?
LISP example the note provides (which it claims it is efficient):
(defun F (n)
(if
(<= n 1)
n
(+ (F (- n 1)) (F (- n 2)))))
Java example it provides (which it claims it is exponential)
static int F(int n) {
if (n <= 1) return n;
else return F(n-1) + F(n-2);
}
Before reading this, I do not even know there is built-in support of memoization in some programming languages.
Is the claim in the notes true? If yes, then why imperative languages not supporting it?
The claims about "LISP" are very vague, they don't even mention which LISP dialect or implementation they mean. None of LISP dialects I'm familiar with do automatic memoization, but LISP makes it easy to write a wrapper function which transforms any existing function into a memoized one.
Fully automatic, unconditional memoization would be a very dangerous practice and would lead to out-of-memory errors. In imperative languages it would be even worse because return values are often mutable, therefore not reusable. Imperative languages don't usually support tail-recursion optimization, further reducing the applicability of memoization.