终端&&非终端递归调用

Question

谁能告诉ma关于终端递归调用与非终端递归调用之间的分歧？

我写

#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，所以这确实是尾递归。