c - C中双因子方程的尾递归

Question

我在实现以下问题的尾递归解决方案时遇到了困难：

双阶乘还有另一个递归关系，它也依赖于阶乘，就是上面的：（对于n<20）

我必须实现这个方程的递归关系——我按照上面的代码做了：

long long factorial(int n) {
    if (n < 0)
        return 0;
    if (n < 1)
        return 1;

     return n * factorial(n - 1);
}

long long doublefactorial(int n) {
    if (n < 0)
        return 0;
    if (n < 2)
        return 1;
    return factorial(n) / doublefactorial(n - 1);
}

现在我必须使用尾递归来实现同样的问题。有人可以告诉我如何做到这一点，因为我无法弄清楚。（也不需要以尾递归的方式实现阶乘函数）

测试用例：

• 5！！= 15
• 10！！= 3840
• 18！！= 185,794,560
• -10！！= 0

标签： ctail-recursion

Answer 1

如果你稍微扩展你的数学，你会发现阶乘函数结果在最终结果的分子和分母之间迭代。

所以这段代码将在 Python 中做到这一点

def _factorial(n, m):
    if n < 0:
        return 0
    elif n == 0:
        return 1.0 * m
    return _factorial(n - 1, n * m)

def factorial(n):
    return _factorial(n, 1)

def _doublefactorial(n, m, is_even):
    if n < 0:
        return 0
    elif n < 2:
        return 1.0 * m

    if is_even:
        m *= factorial(n)
    else:
        m /= factorial(n)

    return _doublefactorial(n - 1, m, (not is_even))

def doublefactorial(n):
    return _doublefactorial(n, 1, True)

在 C 中：

unsigned int _factorial(const unsigned int n, const unsigned int m) {
    if (n < 0) {
        return 0;
    } else if (n == 0) {
        return m;
    }
    return _factorial(n - 1, n * m);
}

unsigned int factorial(const unsigned int n) {
    return _factorial(n, 1);
}

double _doublefactorial(const unsigned int n, const double m, const char is_even) {
    double value = m;

    if (n < 0) {
        return 0;
    } else if (n < 2) {
        return m;
    }

    if (is_even) {
        value *= factorial(n);
    } else {
        value /= factorial(n);
    }

    return _doublefactorial(n - 1, value, !is_even);
}

double doublefactorial(const unsigned int n) {
    return _doublefactorial(n, 1, 1);
}