データ構造の末尾再帰

ここでは、末尾再帰とは何かを確認します。末尾再帰は基本的に、関数の最後のステートメントとして再帰関数を使用しています。したがって、再帰呼び出しから戻った後に何もすることが残っていない場合、それは末尾再帰と呼ばれます。末尾再帰の一例を見ていきます。

例

#include <iostream>
using namespace std;
void printN(int n){
   if(n < 0){
      return;
   }
   cout << n << " ";
   printN(n - 1);
}
int main() {
   printN(10);
}

出力

10 9 8 7 6 5 4 3 2 1 0

末尾再帰は、非末尾再帰よりも優れています。再帰呼び出しの後にタスクが残っていないため、コンパイラーがコードを最適化するのが簡単になります。 1つの関数が呼び出されると、そのアドレスはスタック内に格納されます。したがって、末尾再帰の場合は、アドレスをスタックに格納する必要はありません。

再帰を使用して階乗を使用できますが、関数は末尾再帰ではありません。 fact（n-1）の値はfact（n）内で使用されます。

long fact(int n){
   if(n <= 1)
      return 1;
   n * fact(n-1);
}

他のいくつかのパラメーターを追加することで、末尾再帰にすることができます。これは以下のようなものです-

long fact(long n, long a){
   if(n == 0)
      return a;
   return fact(n-1, a*n);
}