Recursion for Catalan number to Memoized

Question

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

Answer 1

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;
}