c - 为什么我们不能使用静态变量来实现尾递归？

Question

我正在学习 C，所以我正在用 C 写一些小练习来练习这门语言。

我有函数式代码的经验，所以我喜欢递归。我认为使用 C 静态变量实现尾递归会很棒，因此不需要额外的参数或辅助函数。

此代码使用递归计算阶乘失败：

long long int fact(int n)
{
    static long long int result = -1;

    if(n <= 0) {
        if(result < 0)
            return 1;
        else {
            long long int temp = result;
            result = -1;
            return temp;
        }
    } else {
        result *= n;
        fact(n - 1);
    }
}

但是，由于某种原因，我不能在 C 中执行此操作。是否有相同的成语？它只是我的编译器吗？记忆化呢？

非常感谢。

Answer 1

您的代码已损坏，因为它有一个不返回值的控制路径。这很好用：

long long int fact(int n)
{
    static long long int result = 1;

    if(n <= 1) {
        long long int temp = result;
        result = 1;
        return temp;
    } else {
        result *= n;
        return fact(n - 1);
    }
}

GCC 确实成功地将尾递归转换为迭代。

一般来说，我认为避免使用静态进行尾递归的原因仅仅是因为函数失去了可重入性。如今，如此多的代码最终不得不在多线程环境中运行，以至于很难证明在代码中留下函数局部静态“地雷”是合理的。我承认这与技术论点一样多。非静态尾递归代码：

static inline long long int fact_(int n, long long int result)
{
    if(n <= 1) {
        return result;
    } else {
        return fact_(n - 1, result * n);
    }
}

long long int fact(int n)
{
    return fact_(n, 1);
}

如果有什么更容易编写 - 特别是两个版本都是 13 LOC - 并且编译同样有效地迭代但不需要静态数据。

Answer 2

您的 else 块似乎没有明确的返回值。你没有收到编译器警告吗？请确保您在打开所有警告的情况下进行编译。

基本上，您需要添加return result;到 else 块的末尾，否则您将如何将结果返回给原始调用者？请记住，return 只弹出一个函数调用，并且当您调用 return 时您是任意深度，因为您在 else 块中对 fact() 进行了所有递归调用。

Answer 3

int factorial(int n)
{
    static int m = 1;
    m *= n;
    if (n > 1)
        factorial(n - 1);
    return m;
}