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

どっちで考えるかだけ

[Anonymous Coward]

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

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

Re:どっちで考えるかだけ

[Anonymous Coward]

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

Re:どっちで考えるかだけ

[taka2 (14791)]

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

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

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

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

Re:

[Anonymous Coward]

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

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

Re:

[Anonymous Coward]

この意見に100%同意。
逆に再帰を使わずに線形オーダーを対数オーダーに下げる実装をするには、自前で
スタックや木などのデータ構造を用意しなくてはいけない。

だから、情報工学やプログラミングのカリキュラムとしては、
ループ使ったプログラミング→スタックなどのプログラムの動作原理→計算量の概念→再帰を使ったプログラミング
であればいいと思う。