c++ - 终端&&非终端递归调用

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，所以这是真正的尾递归。