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”部分并不是加泰罗尼亚数字本身所特有的，但在处理阶乘、乘法和除法时通常是可取的。 greatest common divisor 的二进制方法易于实现且足够快，并且通常有助于将中间值保持在所使用类型的范围内。

一个简单的方法来查明是否 c = a*b溢出，就是检查是否c/a == b (假设正 a 、 a >= 1 )。