1
$\begingroup$

So I was going through the idea behind dynamic programming (memoization), and thought of this question.

Can a compiler convert any recursion into a table filling DP solution, of course given the hint(like some keyword or macro) from the programmer that the following recursive function can be solved with DP (so programmer knows that it exhibits overlapping sub-problems and optimal substructure)?

If it's possible why don't many of them have it, if there exists anyone that does?

Improve this question
$\endgroup$
5
  • $\begingroup$ Python supports this using metaprogramming. It is questionable for a compiler to perform such an aggressive optimization, which is not necessarily advantageous in any given situation. $\endgroup$
    – Yuval Filmus
    Oct 17, 2018 at 4:04
  • $\begingroup$ @YuvalFilmus I would like to see a document how Python achieve this. Why not advantageous, I didn't get the idea. If a compiler turns an excessive recursion into at least memoization is a great job. Into tabling greater job, no recursion overhead. $\endgroup$
    – kelalaka
    Oct 17, 2018 at 6:54
  • 1
    $\begingroup$ Search for "@memoize" to see how Python handles this. $\endgroup$
    – Yuval Filmus
    Oct 17, 2018 at 7:43
  • 1
    $\begingroup$ Whether a recursion is excessive or not could depend on parameters which the compiler can't possibly know. Memoization uses memory, so there is a non-trivial time-space tradeoff which you probably don't want the compiler to decide on. $\endgroup$
    – Yuval Filmus
    Oct 17, 2018 at 7:44
  • $\begingroup$ @YuvalFilmus thank you that answers my question. I looked into this and apparently no compiler does this automatically. It's something a programmer can do, like define a macro/template. I guess the compilers have no such built-in macros. But I guess one can come up with a library. $\endgroup$
    – anon
    Oct 17, 2018 at 13:51

1 Answer 1

Reset to default
1
$\begingroup$

There is an easy way to implement dynamic programming, using a hash table. The idea is that the recursive procedure stores a huge giant table, containing all values computed so far. Whenever the recursive procedure is called, it first checks whether the value is already in the table, and if so, the value is immediately returned. Otherwise, the body of the procedure is executed, and the result is stored in the table.

This kind of memoization can be enabled, for a specific procedure, using the decorator @memoize in Python, and perhaps similar metaprogramming mechanisms are available in other languages.

Since the table takes up space, it is not clear that this kind of memoization is advantageous in every situation. For example, it might be that the function is easy to compute, and using a hash table would make it significantly slower (since memory access is small). Perhaps a certain code is trying to keep a certain table in cache, and using memoization would interfere with this effort. Perhaps using a table would interfere with security in some way, since it will reveal whether a function is called with the same value as before or not. There are probably many other reasons for the compiler not to perform such an optimization automatically.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.