Question

Modify the following code to count the number of recursive calls made for the Manhattan-path problem we studied earlier. Next, modify to include stored values and see how that reduces the number of calls made.

public class ManhattanWithCallCount {

    public static void main (String[] argv)
    {
        // Test case 1: go from (2,2) to (0,0)
        int r = 2;
        int c = 2;
        int n = countPaths (r, c);
        System.out.println ("r=" + r + " c=" + c + " => n=" + n);

        // Test case 2: go from (5,7) to (0,0)
        r = 5;
        c = 7;
        n = countPaths (r, c);
        System.out.println ("r=" + r + " c=" + c + " => n=" + n);
    }


    static int countPaths (int numRows, int numCols)
    {
        // Bottom-out case:
        if ( (numRows == 0) || (numCols == 0) ) {
            return 1;
        }

        // Otherwise, reduce to two sub-problems and add.
        int downCount = countPaths (numRows-1, numCols);
        int rightCount = countPaths (numRows, numCols-1);
        return (downCount + rightCount);
    }
}

Answer 1

Added static count variable to the program

Program Screenshot :

Program Code :

public class ManhattanWithCallCount {
   public static int count = 0;

public static void main (String[] argv)
{
// Test case 1: go from (2,2) to (0,0)
  
int r = 2;
int c = 2;
int n = countPaths (r, c);
System.out.println ("r=" + r + " c=" + c + " => n=" + n);

// Test case 2: go from (5,7) to (0,0)
r = 5;
c = 7;
n = countPaths (r, c);
System.out.println ("r=" + r + " c=" + c + " => n=" + n);
System.out.println("the number of recursive calls made for the Manhattan-path problem : " + count);
}

static int countPaths (int numRows, int numCols)
{
   count++;
// Bottom-out case:
if ( (numRows == 0) || (numCols == 0) ) {
return 1;
}

// Otherwise, reduce to two sub-problems and add.
int downCount = countPaths (numRows-1, numCols);
int rightCount = countPaths (numRows, numCols-1);
return (downCount + rightCount);
}
}

Program output:

Modified the stored values like below

Sample Output: