再帰は、次の反復に移動する前にローカル状態を暗黙的に保持する反復の一種です。これは、通常の関数が次々に呼び出していることを考えれば簡単に理解できます。
void iteration_2 (int x) {
/* ... */
}
void iteration_1 (int x) {
if (x > 0) return;
iteration_2(x + 1);
}
void iteration_0 (int x) {
if (x > 0) return;
iteration_1(x + 1);
}
それぞれiteration_#()は基本的に互いに同一ですが、それぞれに独自のxがあり、それぞれがどの関数がそれを呼び出したかを記憶しているため、呼び出した関数が終了したときに呼び出し元に適切に戻ることができます。この概念は、プログラムが再帰バージョンに変換されても変わりません。
void iteration (int x) {
if (x > 0) return;
iteration(x + 1);
}
停止条件 (関数からのifチェック) を削除すると、反復は無限になります。return再帰から戻ることはありません。そのため、連続する関数呼び出しごとに記憶される情報 (ローカルxと呼び出し元のアドレス) は、OS がその情報を格納するためのメモリを使い果たすまで蓄積され続けます。
「スタック」をオーバーフローしない無限再帰関数を実装することが可能です。十分な最適化レベルでは、多くのコンパイラーが最適化を適用して、末尾再帰呼び出しのために何かを記憶するために必要なメモリーを削除できます。たとえば、次のプログラムを考えてみましょう。
int iteration () {
return iteration();
}
でコンパイルするとgcc -O0、次のようになります。
iteration:
.LFB2:
pushq %rbp
.LCFI0:
movq %rsp, %rbp
.LCFI1:
movl $0, %eax
call iteration
leave
ret
ただし、 でコンパイルするとgcc -O2、再帰呼び出しが削除されます。
iteration:
.LFB2:
.p2align 4,,7
.L3:
jmp .L3
この無限再帰の結果は単純な無限ループであり、「スタック」のオーバーランはありません。したがって、無限ループが許可されているため、無限再帰が許可されます。
ただし、再帰呼び出しは関数が最後に行うことではないため、プログラムは末尾呼び出しの最適化の候補ではありません。関数にはreturn、再帰呼び出しに続くステートメントがまだあります。再帰呼び出しが戻った後に実行する必要があるコードがまだあるため、オプティマイザーは再帰呼び出しのオーバーヘッドを取り除くことができません。その後のコードが実行できるように、呼び出しが正常に戻ることを許可する必要があります。そのため、プログラムは、呼び出しコードの戻りアドレスを格納するというペナルティを常に支払うことになります。
標準では、特定の用語で「無限再帰」について言及していません。ご質問に関連すると思われるものをまとめました。
- 関数の再帰呼び出しが許可されている (C.11 §6.5.2.2 ¶11)
再帰的な関数呼び出しは、他の関数のチェーンを介して直接的および間接的に許可されます。
- ステートメントへの再帰的なエントリは、ローカル変数の新しいインスタンスを作成します (C.11 §6.2.4 ¶5,6,7)
識別子がリンケージおよびストレージ クラス指定子 static なしで宣言されているオブジェクトは、一部の複合リテラルと同様に、自動ストレージ期間を持ちます。...
可変長配列型を持たないこのようなオブジェクトの場合、その有効期間は、関連付けられているブロックへのエントリから、そのブロックの実行が何らかの方法で終了するまで延長されます。(囲まれたブロックに入るか、関数を呼び出すと、現在のブロックの実行が中断されますが、終了しません。) ブロックに再帰的に入ると、オブジェクトの新しいインスタンスが毎回作成されます。...
可変長配列型を持つオブジェクトの場合、その有効期間は、オブジェクトの宣言から、プログラムの実行が宣言のスコープを離れるまで延長されます。スコープが再帰的に入力される場合、オブジェクトの新しいインスタンスが毎回作成されます。
標準では、多くの場所でメモリ割り当ての失敗について述べていますが、自動ストレージ期間を持つオブジェクトのコンテキストでは決してありません。標準で明示的に定義されていないものはすべて未定義であるため、自動保存期間を持つオブジェクトの割り当てに失敗したプログラムの動作は未定義です。これは、非常に長い関数呼び出しチェーンまたは再帰呼び出しが多すぎるプログラムの間でも同様に適用されます。