アカウント名:
パスワード:
ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装するしロジックを設計した段階で単純ループになってればループ構造で実装する。
そのように考える方が分かりやすいからそういうロジック設計になっているのだしリソースが潤沢な時代だからどっちでもいい。
計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。リソースが膨大でも実際にスタックとして確保されるメモリは多くない。たかだか1〜10MB末尾再帰以外の再帰呼出しは関数型言語でも基本的にスタックを消費する。
> 計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。
クイックソート(ピボットより小さい側と大きい側の二つ)とか、木のトラバース(2分木なら左の枝と右の枝)といった「自分自身を2回以上呼び出す」ような分割統治されたコードを書くときは、まず再帰を使いますね。末尾再帰とかループ化は簡単にはできません。自前でキューとか作って管理すれば再帰を無くせますが、可読性が格段に落ちますし。そんなことをするぐらいなら、関数呼び出しの引数を最小化する(データ本体は別に持たせて、参照のインデックスだけ再帰呼び出しの引数にする)などといったスタック消費量削減を目指した方が楽かと。
#クイックソートも計算量O(N logN)で、O(N)より大きいよ。ていうか、「計算量がO(N)より小さい」ような「再帰を使う」アルゴリズムってめったにないよなぁ。#二分探索ぐらいかですかね?。あれこそ再帰を使うのがばからしいというか、簡単に再帰無しのループに書き下せる感じだけど…
まあ、2回呼び出しがあるからといってフィボナッチを再帰で組むヤツがいたとしたら、そいつはさすがに許せないな。
> 計算量がO(N)より小さい」ような「再帰を使う」アルゴリズムってめったにないよなぁ。
B木ですかねO(log N)。ループだと面倒な気がする。あと連続して使うとするとO(N log N)ですが。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
人生unstable -- あるハッカー
どっちで考えるかだけ (スコア:2, 興味深い)
ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装するし
ロジックを設計した段階で単純ループになってればループ構造で実装する。
そのように考える方が分かりやすいからそういうロジック設計になっているのだし
リソースが潤沢な時代だからどっちでもいい。
Re: (スコア:0)
計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。リソースが膨大でも実際にスタックとして確保されるメモリは多くない。たかだか1〜10MB
末尾再帰以外の再帰呼出しは関数型言語でも基本的にスタックを消費する。
Re:どっちで考えるかだけ (スコア:1)
> 計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。
クイックソート(ピボットより小さい側と大きい側の二つ)とか、木のトラバース(2分木なら左の枝と右の枝)といった「自分自身を2回以上呼び出す」ような分割統治されたコードを書くときは、まず再帰を使いますね。末尾再帰とかループ化は簡単にはできません。
自前でキューとか作って管理すれば再帰を無くせますが、可読性が格段に落ちますし。そんなことをするぐらいなら、関数呼び出しの引数を最小化する(データ本体は別に持たせて、参照のインデックスだけ再帰呼び出しの引数にする)などといったスタック消費量削減を目指した方が楽かと。
#クイックソートも計算量O(N logN)で、O(N)より大きいよ。ていうか、「計算量がO(N)より小さい」ような「再帰を使う」アルゴリズムってめったにないよなぁ。
#二分探索ぐらいかですかね?。あれこそ再帰を使うのがばからしいというか、簡単に再帰無しのループに書き下せる感じだけど…
まあ、2回呼び出しがあるからといってフィボナッチを再帰で組むヤツがいたとしたら、そいつはさすがに許せないな。
Re: (スコア:0)
> 計算量がO(N)より小さい」ような「再帰を使う」アルゴリズムってめったにないよなぁ。
B木ですかねO(log N)。ループだと面倒な気がする。
あと連続して使うとするとO(N log N)ですが。