データ構造-再帰の基本

一部のコンピュータープログラミング言語では、モジュールまたは関数がそれ自体を呼び出すことができます。この手法は再帰として知られています。再帰では、関数α 自分自身を直接呼び出すか、関数を呼び出します β これにより、元の関数が呼び出されます α。関数α 再帰関数と呼ばれます。

Example −それ自体を呼び出す関数。

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example −別の関数を呼び出す関数で、別の関数が再度呼び出します。

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

プロパティ

再帰関数は、ループのように無限に進む可能性があります。再帰関数の無限の実行を回避するために、再帰関数が持つ必要のある2つのプロパティがあります-

Base criteria −この条件が満たされると、関数が再帰的に自分自身を呼び出すのを停止するように、少なくとも1つの基本基準または条件が必要です。
Progressive approach −再帰呼び出しは、再帰呼び出しが行われるたびに基本基準に近づくように進行する必要があります。

実装

多くのプログラミング言語は、 stacks。一般的に、関数（caller）別の関数を呼び出します（callee）またはそれ自体を呼び出し先として、呼び出し元関数は実行制御を呼び出し先に転送します。この転送プロセスには、発信者から着信者に渡されるデータも含まれる場合があります。

これは、呼び出し元の関数がその実行を一時的に中断し、後で実行制御が呼び出し先の関数から戻ったときに再開する必要があることを意味します。ここで、呼び出し元関数は、それ自体が保留になっている実行ポイントから正確に開始する必要があります。また、作業していたのとまったく同じデータ値が必要です。この目的のために、呼び出し元関数のアクティベーションレコード（またはスタックフレーム）が作成されます。

このアクティベーションレコードは、ローカル変数、仮パラメーター、戻りアドレス、および呼び出し元関数に渡されるすべての情報に関する情報を保持します。

再帰の分析

同じタスクを反復で実行できるため、再帰を使用する理由について議論する人もいるかもしれません。最初の理由は、再帰によってプログラムが読みやすくなり、最新の拡張CPUシステムにより、再帰は反復よりも効率的であるためです。

時間計算量

反復の場合、時間計算量を数えるために反復回数を取ります。同様に、再帰の場合、すべてが一定であると仮定して、再帰呼び出しが行われている回数を把握しようとします。関数への呼び出しはΟ（1）であるため、（n）回の再帰呼び出しが行われると、再帰関数はΟ（n）になります。

スペースの複雑さ

スペースの複雑さは、モジュールの実行に必要な追加スペースの量としてカウントされます。反復の場合、コンパイラーは余分なスペースをほとんど必要としません。コンパイラーは、反復で使用される変数の値を更新し続けます。ただし、再帰の場合、システムは再帰呼び出しが行われるたびにアクティベーションレコードを保存する必要があります。したがって、再帰関数の空間の複雑さは、反復を伴う関数の空間の複雑さよりも高くなる可能性があると考えられます。