# Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $$i$$, you'll incur an operating cost of $$N(i)$$ if you run the business out of NY; you'll incur an operating cost of $$S(i)$$ if you run the business out of SF. There is a moving cost $$M$$ if you decide to switch offices. The goal is to minimize total cost. According to the solutions, a DP solution would look like this:

$$OPT(i, N) = N(i) + \min(OPT(i-1, N), OPT(i-1, S) + M), \\ OPT(i, S) = S(i) + \min(OPT(i-1, S), OPT(i-1, N) + M).$$

I'm trying to figure out how one can use recursion as opposed to DP to solve this solution. My understanding is that recursion works from top to bottom and DP works bottom up. I'm just having trouble actually figuring out a viable top to bottom recursive algorithm would look like in this case.

The recursive solution is to use the recurrence directly.

It corresponds to the following algorithm:

Function OPT(i, site):
If i = 0, return 0
If i > 0 and site = N, return N(i) + min(OPT(i-1, N), OPT(i-1, S) + M)
If i > 0 and site = S, return S(i) + min(OPT(i-1, S), OPT(i-1, N) + M)


If you run this algorithm using memoization (not recomputing the value for the same input), then you get essentially the dynamic programming solution.

One way to implement this kind of approach is like so:

Function OPTm(i, site):
If i = 0, return 0
If (i, site) in Database, return Database(i, site)
If site = N, answer = N(i) + min(OPTm(i-1, N), OPTm(i-1, S) + M)
If site = S, answer = S(i) + min(OPTm(i-1, S), OPTm(i-1, N) + M)