パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

再帰呼び出し、よく使う?使わない?」記事へのコメント

  • 末尾呼び出しの最適化が仕様で保証された言語以外でループ代わりに使うと、あっという間にスタックを使い切る。(再帰的定義で繰り返しを表す発想の起源である)数学ではスタックの深さは無限だから問題にならないだろうけど(ただし停止することの証明が必要)。

    • by Anonymous Coward on 2015年02月11日 19時11分 (#2759503)

      数学的帰納法は停止しないよね!…するのか?どっちだろ。

      親コメント
      • by Anonymous Coward on 2015年02月11日 21時21分 (#2759587)

        たかだかω回で停止する。(数学的にはそういうのは「停止する」うちに入る)

        親コメント
      • by Anonymous Coward

        ・A(0)が成り立つかどうかを判定する関数
        ・A(n)→A(n+1)が成り立つかどうかを判定する関数
        が与えられたとき、与えられた自然数nに対してA(n)が成り立つかどうか判定するプログラムを再帰で書ける(スタックの深さが無限なら)。そのプログラムとnを万能チューリング機械に与えて実行したら、nがどんな自然数でも必ず有限時間内に停止するので、停止する。
        逆に停止しない可能性があるなら、証明として認められない。

      • by Anonymous Coward

        します。

人生unstable -- あるハッカー

処理中...