CODEWITHSUNDEEP
javacatalan
UFC Insider
UFC Insider

Reputation: 838

Recursion for Catalan number to Memoized

I have been asked to write a recursive function that will calculate the Catalan number of monotonic lattice paths along the edges of a grid with n × n square cells, which do not pass above the diagonal (pic)

I was not allowed to use for-loops, only recursive calls... This is what I did:

public long C(int n) {
    if (n == 1)
        return 0;
    return C(n, 0, 0);
}

private long C(int n, int i, int j) {

    // CAN MOVE UP & RIGHT
    if (j - i > 0 && j + 1 <= n)
        return paths(n, i + 1, j) + paths(n, i, j + 1);
    // CAN MOVE UP
    else if (j - i > 0)
        return paths(n, i + 1, j);
    // CAN MOVE RIGHT
    else if (j + 1 <= n)
        return paths(n, i, j + 1);
    // CAN'T MOVE
    else
        return 1;
}

I don't know if this code is the best but it works... I want to convert this function to be a Memoized function. But I can't understand how & also why it would make the function more efficient. I understand why Fibonnaci in memoized is more efficient, but here I will always have to get to the end of the path and then return 1 or 0 so what does it matter if I store 1 / 0 inside an array for say?

Thanks for any kind of help

Upvotes: 2

Views: 863

Answers (2)

gabbar0x
gabbar0x

Reputation: 4266

It seems like you know what Memoization is. Basically, all you do is create a table memo which stores a value once you reach it so you don't have to calculate it in the recursion again. Something similar to why fibonacci(5) won't have to go into recursion to find fibonacci(3), if we have already calculated, say fibonacci(6), because we have memoized it. I hope you get it. Here is the code, memoized in the same spirit. Andrea's question has great visuals to understand.

long[][]memo;  //Memo table

public long C(int n)
{
    if (n == 1)
        return 0;

    memo=new int[n+1][n+1]; //Increase to n+1 and won't crash!

    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            memo[j][i]=-1;

    return C(n, 0, 0, memo);
}

private long C(int n, int i, int j, it) {

    // CAN MOVE UP & RIGHT
    if (j - i > 0 && j + 1 <= n)
    {
        if(memo[i+1][j]==-1)
            memo[i+1][j]=paths(n, i + 1, j);

        if(memo[i][j+1]==-1)
            memo[i][j+1]=paths(n, i, j + 1);

        return memo[i+1][j]+memo[i][j+1];
    }
    // CAN MOVE UP
    else if (j - i > 0)
    {
        if(memo[i+1][j]==-1)
            memo[i+1][j]=paths(n, i + 1, j);
        return memo[i+1][j];
    }
    // CAN MOVE RIGHT
    else if (j + 1 <= n)
    {
        if(memo[i][j+1]==-1)
            memo[i][j+1]=paths(n, i, j + 1);
        return memo[i][j+1];
    }
    // CAN'T MOVE
    else
        return 1;
}

Upvotes: 1

Andreas
Andreas

Reputation: 159135

But I can't understand [...] why it would make the function more efficient.

Looking at the image, numbering the pictures starting with 1, and (x,y) coordinates with (0,0) in lower left corner, you can see that pictures 2,3,4, 5,6,7,8,10, 12, are all going through the point at (3,1).

Paths from (3,1):

  • (3,1) → (4,1) ↑ (4,2) ↑ (4,3) ↑ (4,4)
    • Picture 2, 4, 5
  • (3,1) ↑ (3,2) → (4,2) ↑ (4,3) ↑ (4,4)
    • Picture 3, 6, 8
  • (3,1) ↑ (3,2) ↑ (3,3) → (4,3) ↑ (4,4)
    • Picture 7, 10, 12

As you can see, you're walking the same path multiple (3) times. If you could cache (memoize) the fact that there are 3 paths from (3,1) to the end, you're saving time.

Time savings will grow as the grid gets bigger.

Catalan number 4x4 grid example

So, what you do, is that first time you get to a point, you calculate the result using recursion, as you already do, then save the number for that point, and when getting to the point again, you just use the cached value:

public static long paths(int n) {
    if (n == 1)
        return 0;
    return paths(n, 0, 0, new long[n][n]);
}
private static long paths(int n, int y, int x, long[][] cache) {
    long result = cache[y][x];
    if (result == 0) {
        if (y < x && x < n) // CAN MOVE UP & RIGHT
            result = paths(n, y + 1, x, cache) + paths(n, y, x + 1, cache);
        else if (y < x) // CAN MOVE UP
            result = paths(n, y + 1, x, cache);
        else if (x < n) // CAN MOVE RIGHT
            result = paths(n, y, x + 1, cache);
        else // CAN'T MOVE
            result = 1;
        cache[y][x] = result;
    }
    return result;
}

Upvotes: 3

Related Questions