Memoization and Interfaces

Question

1. Does a memoized recursive solution has the same complexity as a non-recursive solution? I think that most of the times the recursive solution will cost more but with the memoization technique I don't really understand why I should not always use recursion? It's shorter and more understandable to me

2. Interfaces question - is it possible to declare a function that will force whoever uses the interface to apply parts of the code in it? Or I can only declare the functions' signature and that's it? Because in android for example I can implement listeners and inside the methods I see lines of code that I can't change and this is different than the normal implementation I'm used to

Answer 1

Regarding dynamic programming, you have two options: top-bottom approach (recursion with memorization), and bottom-up approach. Bottom-up approach builds a lookup array using loops, so it is more efficient than recursion which costs stack allocation and consumes time. With recursive memorization, you simply "remember" what solutions you have found so that you don't recalculate the same problem again and again. So you check if the current problem is solved first before going solve it. This is the difference between it and backtracking, which repeat solving the same problem and thus takes duplicate times.