無限再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/17 09:59 UTC 版)
無限再帰とは、無限ループの特例で、再帰で発生する無限ループである。最も些細な例としては、次のSchemeで示したラムダ計算の Ω項である。 (define Ω(let ([ω (lambda (f) (f f))])(ω ω))) Ω は無限再帰なので、正規形を持たない。基底ケースが無かったり、帰納段階が不完全な構造的再帰では、普通は無限再帰になってしまう。このような不完全な構造的再帰の例は次の通り。 (define (sum-from-1-to n)(+ n (sum-from-1-to (sub1 n)))) 関数 sum-from-1-to は決して再帰が止まることはなく、スタックを使い尽くすだろう。これを修正するには、基底ケースを追加する。 (define (sum-from-1-to' n)(cond[(= n 1) 1][else (+ n (sum-from-1-to' (sub1 n)))])) 修正した関数は、n が 1 未満か、n が大きすぎる時にだけ、スタックを使い尽くすが、最初のケースはエラーチェックすれば回避できる。スタックを使い尽くすことのない再帰関数については、末尾再帰を参照のこと。
※この「無限再帰」の解説は、「無限ループ」の解説の一部です。
「無限再帰」を含む「無限ループ」の記事については、「無限ループ」の概要を参照ください。
ウィキペディア小見出し辞書の「無限再帰」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 無限再帰のページへのリンク
