终端&非终端递归调用

Question

有人能告诉我终端递归调用和非终端递归调用之间的差异吗？

我写

#include <iostream>

int factorial(int n)
{
    if (n==0 || n==1)
        return 1;
    else
        return n*factorial(n-1);
}

Answer 1

当递归调用是函数中要完成的最后一次操作时，就会发生终端递归。

当从递归调用返回时需要做额外的工作时，就会发生非终端递归。

您的示例是非终端的，因为从递归调用返回后，仍然需要进行乘法( n*)。最后一行：

return n*factorial(n-1)

实际上相当于：

int temp = factorial(n-1);
return temp * n;

可以使用附加参数将factorial()函数更改为终端：

int factorial_x(int n, int f)
{
    if (n==0 || n==1)
        return f;
    else
        return factorial_x(n - 1, f * n);
}
int factorial(int n)
{
    return factorial_x(n, 1);
}

递归调用：

return factorial_x(n - 1, f * n);

相当于：

int n2 = n - 1;
int f2 = f * n;
return factorial(n2, f2);

正如您所看到的，现在乘法在递归调用之前，而不是在后面。在递归调用之后，没有什么，只有return，所以这是真正的尾递归。