なあ、再帰関数好きな人いる? パート3 [転載禁止]©2ch.net
レス数が900を超えています。1000を超えると表示できなくなるよ。
再帰処理は
現在の関数が戻ってゆくアドレスをスタックに保存し、このアドレスを積極的に利用する。
プログラミングの実行アドレスをスタックから取り出して制御するので、
再帰プログラミングを利用するコツは、戻りアドレスを正しく理解することだ。
再帰は同じ関数を行ったり来たりするものだが、
日常の社会では、やらない方法だ。
普通は、配列を利用して、そこに保存してあるデータを使い、
同じ場所でプログラムを実行する >>881
そらまあ再起が辿るイメージ図は全てツリーって名称付けれますし ゲーム作るときになってようやく再帰の恩恵を得た
めっちゃ書きやすい >>883
ミニマックス法かアルファベータ法だろ? マイコンだとスタックが1桁とかだから再帰書いた瞬間に死ぬ ルネサスのRL78/G10はRAMが128Byteしかないらしいな λf . (λx . f (x x)) (λx . f (x x)) ループで書くと出現する余計な変数がなくなるのが再帰のメリット >>889
?
kwsk
ループ変数は再帰関数でも必要なのでは? どんどんスタックにつめば確かにループ変数はいらない
ただ、人間のためにループ変数はあった方かいいと思うけど 再帰関数を理解したとき、最初にこれ考えたやつは天才だと思ったね
実行速度やスタック問題はともかくコードは見ていて美しい以外の何者でもない。 CやUnix、オブジェクト指向なんかよりもはるかに古いんだよな
最初に実装されたのはlispかな
メモリを食いすぎるのでおもちゃしか動かなかったようだが 今の時代メモリ食いすぎても動くし遅くもならないよな
1億再帰とかやったら話は別だけど >>890
要らない
/* n の階乗を求める */
int fact(int n)
{
if(n==0){
return 1;
} else {
return fact(n-1);
}
}
実質ループする処理だけど、ループの回数数えるための
変数は一切出現しない。なおかつ n は不変。 おお、"n*" を忘れた。こんな短い関数にバグ突っ込む俺(泣) くだらん処理にスタックを使いたくないのでわしは使わん
ライブラリが殆ど無いマイナーCPUのマイナーCコンパイラでQuickSortを書いた時くらいじゃケケケ 最近じゃオプティマイザがなるべくスタック使わないように
最適化してくれるんじゃなかったっけ? >>898
末尾再帰ならそうだと思いますが、末尾再帰でなければ無理でしょう >>896-897 は末尾再帰じゃないから最適化されにくい、というか、されない >>8
ループと再帰の能力は同じです
かなり古い計算論の結果です >>899
結合法則を仮定していいドメインなら
CPS変換を用いて最適化する手法が随分前からあります
結合法則はGPU並列化でも使われてます
浮動小数点の場合は工夫しないと誤差が変わりますが
ちなみにC++ conceptの初期案でもaxiomで法則を記述出来ました >>902
scheme の継続渡しに関係しますか?
キーワードありがとうございます >>903
そう
Continuation-passing style, defunctionalization, and associativity
Categorical Structure of ContinuationPassing Style
この辺のサンプルプログラム読んで すき
しかし再帰絶対書かないマンが思いの外多くて草生えるわ
末尾最適化できない再起をループに展開したって結局キューだのスタックオブジェクトでヒープ使うわけで
メモリ大幅に節約できると勘違いしてる基地外とか話にならん
再帰深度がたかだか1000段とかでスタックフレームにデカいオブジェクトブチ込んだりしなきゃ
素直に再帰で組むのがいいに決まってるじゃないか
数学的演算でもしない限り業務用でスタック溢れるケースを探す方が大変 スタックとヒープは別物
共有してるアーキテクチャもあるが ループに展開できる処理をわざわざ再帰で書く奴も大概やけどな。 >>909
二方向に再帰するもの、は展開に苦労しますね
式の評価は、再帰じゃないと書けないですね 再帰的データ構造は再帰でたどるのが楽なんだけど
ループで処理したほうが途中で抜けたり処理を組み合わせやすい
そこで再帰的な処理を遅延リストと組み合わせてループで処理するやり方がいまでは一般的な気がする
こういうふうに C#
https://paiza.io/projects/WbmxzuNdJq95o9RYTKFY_A 何が一般的なのか知らんがかなり変態的なコードだな
ループでGetEnumerator呼び出したりMoveNextの戻り値を見ずCurrentを取り出したりは一般的じゃないぞ
つーかバグだろそれ レス数が900を超えています。1000を超えると表示できなくなるよ。