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

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

  • by Anonymous Coward

    ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装するし
    ロジックを設計した段階で単純ループになってればループ構造で実装する。

    そのように考える方が分かりやすいからそういうロジック設計になっているのだし
    リソースが潤沢な時代だからどっちでもいい。

    • by Anonymous Coward

      計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。リソースが膨大でも実際にスタックとして確保されるメモリは多くない。たかだか1〜10MB
      末尾再帰以外の再帰呼出しは関数型言語でも基本的にスタックを消費する。

      • > 計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。

        クイックソート(ピボットより小さい側と大きい側の二つ)とか、木のトラバース(2分木なら左の枝と右の枝)といった「自分自身を2回以上呼び出す」ような分割統治されたコードを書くときは、まず再帰を使いますね。末尾再帰とかループ化は簡単にはできません。
        自前でキューとか作って管理すれば再帰を無くせますが、可読性が格段に落ちますし。そんなことをするぐらいなら、関数呼び出しの引数を最小化する(データ本体は別に持たせて、参照のインデックスだけ再帰呼び出しの引数にする)などといったスタック消費量削減を目指した方が楽かと。

        #クイックソートも計算量O(N logN)で、O(N)より大きいよ。ていうか、「計算量がO(N)より小さい」ような「再帰を使う」アルゴリズムってめったにないよなぁ。
        #二分探索ぐらいかですかね?。あれこそ再帰を使うのがばからしいというか、簡単に再帰無しのループに書き下せる感じだけど…

        まあ、2回呼び出しがあるからといってフィボナッチを再帰で組むヤツがいたとしたら、そいつはさすがに許せないな。

        親コメント
        • by Anonymous Coward

          > 計算量がO(N)より小さい」ような「再帰を使う」アルゴリズムってめったにないよなぁ。

          B木ですかねO(log N)。ループだと面倒な気がする。
          あと連続して使うとするとO(N log N)ですが。

にわかな奴ほど語りたがる -- あるハッカー

処理中...