Data-structures-algorithms-recursion-basics
データ構造-再帰の基本
一部のコンピュータープログラミング言語では、モジュールまたは関数が自分自身を呼び出すことができます。 この手法は、再帰として知られています。 再帰では、関数*α*はそれ自体を直接呼び出すか、元の関数*α*を呼び出す関数*β*を呼び出します。 関数*α*は、再帰関数と呼ばれます。
例-それ自体を呼び出す関数。
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}例-別の関数を呼び出して、それを再び呼び出す関数。
int function1(int value1) {
if(value1 < 1)
return;
function2(value1 - 1);
printf("%d ",value1);
}
int function2(int value2) {
function1(value2);
}プロパティ
再帰関数はループのように無限に進むことができます。 再帰関数の無限実行を避けるために、再帰関数が持つ必要がある2つのプロパティがあります-
- 基本条件-この条件が満たされると、関数がそれ自体の再帰呼び出しを停止するように、少なくとも1つの基本条件または条件が必要です。
- プログレッシブアプローチ-再帰呼び出しは、再帰呼び出しが行われるたびに基本条件に近づくように進行する必要があります。
実装
多くのプログラミング言語は、 stacks を使用して再帰を実装しています。 一般に、関数（ caller ）が別の関数（ callee ）またはそれ自体を呼び出し先として呼び出すたびに、呼び出し元関数は実行制御を呼び出し先に渡します。 この転送プロセスには、呼び出し元から呼び出し先に渡されるデータも含まれる場合があります。
これは、呼び出し元の関数がその実行を一時的に中断し、実行制御が呼び出し先の関数から戻ったときに再開する必要があることを意味します。 ここで、呼び出し元関数は、それ自体を保留にする実行ポイントから正確に開始する必要があります。 また、作業していたのとまったく同じデータ値が必要です。 この目的のために、呼び出し側関数のアクティベーションレコード（またはスタックフレーム）が作成されます。
このアクティベーションレコードは、ローカル変数、仮パラメーター、戻りアドレス、および呼び出し元関数に渡されるすべての情報に関する情報を保持します。
再帰の分析
同じタスクを反復で実行できるため、再帰を使用する理由を議論するかもしれません。 最初の理由は、再帰はプログラムをより読みやすくし、最新の強化されたCPUシステムのために、再帰は反復よりも効率的です。
時間の複雑さ
反復の場合、時間の複雑さをカウントするために反復回数を取ります。 同様に、再帰の場合、すべてが一定であると仮定して、再帰呼び出しが行われている回数を把握しようとします。 関数の呼び出しはΟ（1）であるため、再帰呼び出しが（n）回行われると、再帰関数がΟ（n）になります。
スペースの複雑さ
スペースの複雑さは、モジュールの実行に必要な追加スペースの量としてカウントされます。 繰り返しの場合、コンパイラは余分なスペースをほとんど必要としません。 コンパイラは、反復で使用される変数の値を更新し続けます。 ただし、再帰の場合、システムは再帰呼び出しが行われるたびにアクティベーションレコードを保存する必要があります。 したがって、再帰関数の空間の複雑さは、反復を伴う関数の空間の複雑さよりも高くなると考えられます。
