终端&&非终端递归调用

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