データ構造における再帰の原則

再帰は、関数がそれ自体を呼び出すプロセスです。再帰を使用して、大きな問題を小さなサブ問題に解決します。覚えておかなければならないことの1つは、各サブ問題が同じ種類のパターンに従っている場合、再帰的アプローチを使用できるのは私たちだけであるということです。

再帰関数には2つの異なる部分があります。ベースケースと再帰ケース。基本ケースは、繰り返しのタスクを終了するために使用されます。基本ケースが定義されていない場合、関数は（理論的には）無限に繰り返されます。

コンピュータプログラムでは、1つの関数を呼び出すと、プログラムカウンターの値は、関数領域にジャンプする前に内部スタックに格納されます。タスクが完了すると、アドレスがポップアウトされてプログラムカウンターに割り当てられ、タスクが再開されます。再帰呼び出し中に、アドレスを複数回格納し、次の関数呼び出しステートメントにジャンプします。 1つの基本ケースが定義されていない場合、それは何度も繰り返され、アドレスをスタックに格納します。スタックにスペースがなくなると、「内部スタックオーバーフロー」としてエラーが発生します。

再帰呼び出しの1つの例は、数値の階乗を見つけることです。数の階乗n=n！ n *（n-1）!と同じですが、n *（n-1）*（n-2）!と同じです。したがって、階乗が関数の場合、何度も呼び出されますが、引数は1減少します。引数が1または0の場合、1が返されます。これが再帰の基本ケースである可能性があります。

例

#include<iostream>
using namespace std;
long fact(long n){
   if(n <= 1)
   return 1;
   return n * fact(n-1);
}
main(){
   cout << "Factorial of 6: " << fact(6);
}

出力

Factorial of 6: 720