CODEWITHSUNDEEP
recursion
Neerad
Neerad

Reputation: 101

Understanding recursion

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?

}

Upvotes: 2

Views: 475

Answers (3)

Shiva
Shiva

Reputation: 651

In another terms from what ring0 has already mentioned - when the program reaches the base case and starts to unwind by going up the stack (call frames). For similar case using factorial example see this.

#!/usr/bin/env  perl

use strict;
use IO::Handle;
use Carp qw(cluck);

STDOUT->autoflush(1);
STDERR->autoflush(1);

sub factorial {
    my $v = shift;

    dummy_func();
    return 1 if $v == 1;
    print "Variable v value: $v and it's address:", \$v, "\ncurrent sub factorial addr:", \&factorial, "\n","-"x40;
    return $v * factorial($v - 1);
}

sub dummy_func {
    cluck;
}

factorial(5);

Upvotes: 0

D&#233;j&#224; vu
D&#233;j&#224; vu

Reputation: 28830

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".

Upvotes: 1

BrokenGlass
BrokenGlass

Reputation: 160852

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.

Upvotes: 1

Related Questions