CODEWITHSUNDEEP
c++debuggingrecursiondynamic-programming
ERJAN
ERJAN

Reputation: 24500

Simple recursion/dp - help trace

This is from dp tutorial on CodeChef, I'm tracing it.

Details: when I enter if clause - i print "STEP 1"/step2/step3. The program works fine.

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))

int memo[10 + 1] ;
void reset_memo()
{
    cout << endl ;
    cout << "RESETTING MEMO" << endl ;
    for (int i = 0 ; i < 11 ; i++) {
        memo[i] = -1 ;
    }
}

int getMinSteps(int n)
{
    cout << "======current n : " << n <<  " ===============" << endl ;
    if (n == 1) {
        cout << "BASE CASE n = 1 and returning 0..." << endl ;
        return 0;
    }  // base case

    if (memo[n] != -1) {
        return memo[n];
    } // we have solved it already :)

    cout << "STEP 1 " << endl ;
    int r = 1 + getMinSteps(n - 1);    // '-1' step .  'r' will contain the optimal answer finally

    if (n % 2 == 0) {
        cout << " STEP 2: "  << endl ;
        r = min(r , 1 + getMinSteps(n / 2)) ;
    }  //  '/2' step

    if (n % 3 == 0) {
        cout << " STEP 3: "   << endl ;
        r =  min(r , 1 + getMinSteps(n / 3)) ;
    }  //  '/3' step

    memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.
    return r;
}

I spent 5 hours trying to understand one little detail:

OUTPUT:

RESETTING MEMO

enter next number

2

===============current n 2 ===============

STEP 1:

===============current n 1 ===============

BASE CASE n = 1 and returning 0...

STEP 2:

===============current n 1 ===============

BASE CASE n = 1 and returning 0...

===============current n 1 ===============

BASE CASE n = 1 and returning 0...

RESULT 1

RESETTING MEMO enter next number

why does it call the black highlighted last piece of code "BASE CASE ...." ?

I clearly don't see it! it should only be there once please help figure out - I don't see where exactly additional call happens!

Upvotes: 1

Views: 117

Answers (1)

lwi
lwi

Reputation: 1712

I tested the program under the debugger and min( ) causes the getMinSteps(n / 2)to be called twice. This is because of the macro definition you have that is using b two times #define min(a,b) ( (a) < (b) ? (a) : (b)) causing a side effect. Try to use std:min instead.

Here is another workaround for the case n % 2 == 0

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))

int memo[10 + 1] ;



void reset_memo()
{
    cout << endl ;
    cout << "RESETTING MEMO" << endl ;
    for (int i = 0 ; i < 11 ; i++) {
        memo[i] = -1 ;
    }
}

int getMinSteps(int n)
{
    cout << "======current n : " << n <<  " ===============" << endl ;
    if (n == 1) {
        cout << "BASE CASE n = 1 and returning 0..." << endl ;
        return 0;
    }  // base case

    if (memo[n] != -1) {
        return memo[n];
    } // we have solved it already :)

    cout << "STEP 1 " << endl ;
    int r = 1 + getMinSteps(n - 1);    // '-1' step .  'r' will contain the optimal answer finally

    if (n % 2 == 0) {
        cout << " STEP 2: "  << endl ;
        int v =  getMinSteps(n / 2); // <--- so getMinSteps will be called only once!
        r = min(r , 1 + v) ;
    }  //  '/2' step

    if (n % 3 == 0) {
        cout << " STEP 3: "   << endl ;
        r =  min(r , 1 + getMinSteps(n / 3)) ;
    }  //  '/3' step

    memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.
    return r;
}

int main(){
    reset_memo();
    getMinSteps(2);
    getchar();
    getchar();

}

Upvotes: 1

Related Questions