Understanding recursion

Question

I am struggling to understand this recursion used in the dynamic programming example. Can anyone explain the working of this. The objective is to find the least number of coins for a value.

//f(n) = 1 + min f(n-d) for all denomimations d

Pseudocode:

int memo[128]; //initialized to -1

int min_coin(int n)
{
   if(n < 0) return INF;
   if(n == 0) return 0;
   if(memo[n] != -1)

   int ans = INF;
   for(int i = 0; i < num_denomination; ++i)
   {
      ans = min(ans, min_coin(n - denominations[i]));
   }
   return memo[n] = ans+1; //when does this get called?

}

Answer 1

This particular example is explained very well in this article at Topcoder.

Basically this recursion is using the solutions to smaller problems (least number of coins for a smaller n) to find the solution for the overall problem. The dynamic programming aspect of this is the memoization of the solutions to the sub-problems so they don't have to be recalculated every time.

And yes - there are {} missing as ring0 mentioned in his comment - the recursion should only be executed if the sub-problem has not been solved before.

Answer 2

To answer the owner's question when does this get called? : in a solution based on a recursive program, the same function is called by itself... but eventually returns... When does it return? from the time the function ceased to call itself

f(a) {
  if (a > 0) f(a-1);
  display "x" 
}

f(5);

f(5) would call f(4), in turns call f(3) that call f(2) which calls f(1) calling f(0).

f(0) has a being 0, so it does not call f(), and displays "x" then returns. It returns to the previous f(1) that, after calling f(0) - done - displays also "x". f(1) ends, f(2) displays "x", ... , until f(5). You get 6 "x".