It is possible to make a catalan number in C with tail recursion?

Question

I have the job of verifying and if it is possible to calculate the catalan number by means of the tail recursion, I could do the calculation with the stack recursion using the definition, but I could not do it by means of the tail recursion

int catalan(int n){
    if(n==0){
        return 1;
    }
    else{
        return 2*(2*n-1)*Catalan(n-1)/(n+1);
    }
}

Answer 1

Specify the multiplier and the divisor as parameters to the function,

unsigned long  catalan_tail(unsigned long  n,
                            unsigned long  multiplier,
                            unsigned long  divisor)
{
    /* Optional TODO: Divide multiplier and divisor by
                      their greatest common divisor? */

    if (n < 2)
        return multiplier / divisor;
    else
        return catalan_tail(n - 1, multiplier * 2*(2*n - 1), divisor * (n + 1));
}

and a wrapper function

unsigned long  catalan(unsigned long  n)
{
    return catalan_tail(n, 1, 1);
}

which supplies initial values for the extra parameters. Basically, we postpone the calculation done on the return value, by supplying the intermediate result as extra parameters, so that the deepest iteration can do it.

We have to supply the multiplier and the divisor as separate values, because the result is only guaranteed to be integer for the final iteration.

The "Optional TODO" part is not particular to Catalan numbers per se, but is generally advisable when dealing with factorials and multiplication and divison. The binary approach for greatest common divisor is easy to implement and sufficiently fast, and often helps keep the intermediate values within the range of the type used.

A simple way to find out if c = a*b overflows, is to check if c/a == b (assuming positive a, a >= 1).