終端&&非終端遞歸調用

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，所以這是真正的尾遞歸。