c - 可以用尾递归在C中制作一个加泰罗尼亚数字吗？

Question

我有验证的工作，如果可以通过尾递归计算加泰罗尼亚数，我可以使用定义使用堆栈递归进行计算，但我不能通过尾递归来计算

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

Answer 1

指定乘数和除数作为函数的参数，

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

和一个包装函数

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

它为额外参数提供初始值。基本上，我们通过提供中间结果作为额外参数来推迟对返回值的计算，以便最深的迭代可以做到这一点。

我们必须将乘数和除数作为单独的值提供，因为仅保证最终迭代的结果是整数。

“可选 TODO”部分本身并不特定于加泰罗尼亚数字，但在处理阶乘、乘法和除法时通常是可取的。最大公约数的二进制方法易于实现且速度足够快，并且通常有助于将中间值保持在所用类型的范围内。

找出是否c = a*b溢出的一种简单方法是检查 if c/a == b（假设为正a, a >= 1）。