# Can the compiler convert recursive algorithm into a dynamic programming

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?

• 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. – Yuval Filmus Oct 17 '18 at 4:04
• @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. – kelalaka Oct 17 '18 at 6:54
• Search for "@memoize" to see how Python handles this. – Yuval Filmus Oct 17 '18 at 7:43
• 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. – Yuval Filmus Oct 17 '18 at 7:44
• @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. – anon Oct 17 '18 at 13:51

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.