这是尾递归吗？

Question

我编写了一个函数来计算整数的幂然后取模。我想知道我所做的是不是尾递归：

int takeModulusTAILRECURSION(int coef, int x, int n, int module){
        int result = 0;
        if ( n > 0 )
            result = takeModulusTAILRECURSION( mod(coef * x, module), x , n - 1, module  );
        else if ( n == 0)
            result = mod ( coef , module );
        return result;
    }

//take modul of an integer ( both negative and positive )
int mod(int x, int modul){
    while ( x < 0) 
        x += modul;
    return x % modul;
}

这是另一个纯粹使用递归的函数，我认为它与上面的不同：

int takeModulusNORMRECURSION(int x, int n, int module){
    if ( n == 1 )
        return mod( x, module );
    else {
        int total = x * takeModulusNORMRECURSION( x, n - 1, module);
        return mod( total, module);
    }
}

顺便说一句，任何人都可以告诉我如何在这些情况下检查 Eclipse 中的帧堆栈？正如我尝试的那样（不知道对还是错），它们都需要运行许多堆栈。

Answer 1

这是否是尾递归取决于代码的编译方式。

当您直接返回对另一个函数（可能是您自己）的调用时，就会发生尾递归。当编译器/解释器注意到这一点时，尾调用优化（人们关心尾递归的原因）就会发生，并且只是替换当前堆栈帧而不是创建另一个堆栈帧。在您的情况下，如果它是天真编译的，则没有尾递归，因为您正在进行递归调用，然后将其分配给调用堆栈中的变量，稍后返回该变量。该分配步骤意味着您在调用其他函数后要做额外的事情，这使得您的代码不适合尾部调用优化。

但是一个好的编译器应该像这样重写你的代码：

int takeModulusTAILRECURSION(int coef, int x, int n, int module){
    if ( n > 0 )
        return takeModulusTAILRECURSION( mod(coef * x, module), x , n - 1, module  );
    else if ( n == 0)
        return mod ( coef , module );
    else
        return 0;
}

//take modul of an integer ( both negative and positive )
int mod(int x, int modul){
    while ( x < 0) 
        x += modul;
    return x % modul;
}

现在它是尾递归的。

但现在是否可以进行尾调用优化取决于语言和实现。例如，如果您的代码应该是 Java，那么 JVM 是否会阻止 tail调用优化？指出，无论你做什么，你都不会得到尾部调用优化。

编辑：我说的是“尾递归”，即“尾递归和尾调用优化”。

Answer 2

第一种方法是尾递归，因为当函数执行“return”时，它返回的值是一个不依赖于当时对另一个方法的调用的值。

第二种方法不是尾递归，事实上也不是递归的，因为它只是迭代改变 x 的值。

第三个也是最后一个方法也是尾递归的，因为与第一个示例一样，当方法“返回”时，它能够在不调用任何方法（包括其自身）的情况下执行此操作。

希望这有帮助。