アカウント名:
パスワード:
ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装するしロジックを設計した段階で単純ループになってればループ構造で実装する。
そのように考える方が分かりやすいからそういうロジック設計になっているのだしリソースが潤沢な時代だからどっちでもいい。
趣味では使うが、仕事では積極的に使わない。ハイエンドのマシンを使う顧客とか、ピーク時でギリギリ扱えるぐらいの余力だったりする。やはり、リソースが潤沢という前提が成り立つかどうかかが、業務などの環境依存なので環境依存のコードを入れるのは避けたいところ。
色んな顧客がいて、負荷がかかるコンポーネントも少しずつ違うし、負荷特性の違う顧客にそれぞれの顧客に対して、再起呼び出しで使うスタックサイズが十分であることを保証し続けることが面倒。
顧客のシステムが運用中にスタックオーバフローで落ちるとか目も当てられないので、まずは、見積もり式が必要になるが、これを作成し、メンテナンスし続けるのが手間。再起関数を修正すると、必要なスタックサイズも変更になるし、その度に再見積もりさせる訳にもいかない。というより、再起呼び出しを使わなくても、スタックに置くデータサイズには気を使う。ヒープ見積もりも、見積もりしやすいようにデータ構造の管理方法とか工夫しているくらい。
これ。再起呼び出しの使いづらさは、「スタックの使用量の見積と確保が困難」という点に尽きる。
とはいえスタックサイズを過信しないほうがよいと思う。
ヒープと違ってスタックサイズは潤沢とは言えないですよね。特にデフォルト値。
計算量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)ですが。
この意見に100%同意。逆に再帰を使わずに線形オーダーを対数オーダーに下げる実装をするには、自前でスタックや木などのデータ構造を用意しなくてはいけない。
だから、情報工学やプログラミングのカリキュラムとしては、ループ使ったプログラミング→スタックなどのプログラムの動作原理→計算量の概念→再帰を使ったプログラミングであればいいと思う。
自分もロジックによって変えるに一票、というか考えた通り自然に実装するのであまり意識しない。もちろん#2759511の通りスタックサイズなどの制約があれば別。
記述がシンプルになる方を選ぶかな。
そのように考える方が分かりやすいからそういうロジック設計になっている
これは、おっしゃる通りだと思います。再帰も、ループも、どちらも単なる(考える/機能を実現する)道具でしかないので、「使い分け」るだけという事ですよね ?
# この基本的な部分には合意した上で、敢えて反論すると..
ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装する
は、ちょっとだけ違うのではないかなと...
思うに、「設計」と「実装」では、立場が違うのではないかと思います。
(「現状(ここでは C 言語で表現する事を想定..)」では..) 再帰(の実装)は、ループ(の実装)の(機能的な..)上位互換になっています。( #2759525 [developers.srad.jp]) で、ご指摘があったように、ループは
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
身近な人の偉大さは半減する -- あるアレゲ人
どっちで考えるかだけ (スコア:2, 興味深い)
ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装するし
ロジックを設計した段階で単純ループになってればループ構造で実装する。
そのように考える方が分かりやすいからそういうロジック設計になっているのだし
リソースが潤沢な時代だからどっちでもいい。
Re:どっちで考えるかだけ (スコア:2)
趣味では使うが、仕事では積極的に使わない。
ハイエンドのマシンを使う顧客とか、ピーク時でギリギリ扱えるぐらいの余力だったりする。
やはり、リソースが潤沢という前提が成り立つかどうかかが、業務などの環境依存なので環境依存のコードを入れるのは避けたいところ。
色んな顧客がいて、負荷がかかるコンポーネントも少しずつ違うし、負荷特性の違う顧客にそれぞれの顧客に対して、
再起呼び出しで使うスタックサイズが十分であることを保証し続けることが面倒。
顧客のシステムが運用中にスタックオーバフローで落ちるとか目も当てられないので、
まずは、見積もり式が必要になるが、これを作成し、メンテナンスし続けるのが手間。
再起関数を修正すると、必要なスタックサイズも変更になるし、その度に再見積もりさせる訳にもいかない。
というより、再起呼び出しを使わなくても、スタックに置くデータサイズには気を使う。
ヒープ見積もりも、見積もりしやすいようにデータ構造の管理方法とか工夫しているくらい。
Re: (スコア:0)
これ。再起呼び出しの使いづらさは、「スタックの使用量の見積と確保が困難」という点に尽きる。
Re:どっちで考えるかだけ (スコア:1)
とはいえスタックサイズを過信しないほうがよいと思う。
Re: (スコア:0)
ヒープと違ってスタックサイズは潤沢とは言えないですよね。特にデフォルト値。
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)ですが。
Re: (スコア:0)
この意見に100%同意。
逆に再帰を使わずに線形オーダーを対数オーダーに下げる実装をするには、自前で
スタックや木などのデータ構造を用意しなくてはいけない。
だから、情報工学やプログラミングのカリキュラムとしては、
ループ使ったプログラミング→スタックなどのプログラムの動作原理→計算量の概念→再帰を使ったプログラミング
であればいいと思う。
Re: (スコア:0)
自分もロジックによって変えるに一票、というか考えた通り自然に実装するのであまり意識しない。
もちろん#2759511の通りスタックサイズなどの制約があれば別。
Re: (スコア:0)
記述がシンプルになる方を選ぶかな。
Re: (スコア:0)
そのように考える方が分かりやすいからそういうロジック設計になっている
これは、おっしゃる通りだと思います。
再帰も、ループも、どちらも単なる(考える/機能を実現する)道具でしかないので、「使い分け」るだけという事ですよね ?
# この基本的な部分には合意した上で、敢えて反論すると..
ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装する
は、ちょっとだけ違うのではないかなと...
思うに、「設計」と「実装」では、立場が違うのではないかと思います。
(「現状(ここでは C 言語で表現する事を想定..)」では..) 再帰(の実装)は、ループ(の実装)の(機能的な..)上位互換になっています。
( #2759525 [developers.srad.jp]) で、ご指摘があったように、ループは