21/07/16 14:24:10.16 S3gddm5/.net
>>892
要らない
/* n の階乗を求める */
int fact(int n)
{
if(n==0){
return 1;
} else {
return fact(n-1);
}
}
実質ループする処理だけど、ループの回数数えるための
変数は一切出現しない。なおかつ n は不変。
898:デフォルトの名無しさん
21/07/16 14:26:08.03 S3gddm5/.net
おお、"n*" を忘れた。こんな短い関数にバグ突っ込む俺（泣）
899:デフォルトの名無しさん
21/07/19 22:18:11.50 hlpOkuZF.net
くだらん処理にスタックを使いたくないのでわしは使わん
ライブラリが殆ど無いマイナーCPUのマイナーCコンパイラでQuickSortを書いた時くらいじゃケケケ
900:デフォルトの名無しさん
21/07/22 20:45:12.08 sSLTRpJ4.net
最近じゃオプティマイザがなるべくスタック使わないように
最適化してくれるんじゃなかったっけ？
901:ハノン
21/07/25 23:45:12.36 rUybnQpf.net
>>900
末尾再帰ならそうだと思いますが、末尾再帰でなければ無理でしょう >>898-899 は末尾再帰じゃないから最適化されにくい、というか、されない
902:デフォルトの名無しさん
21/10/02 15:46:41.87 qz0ghb/n.net
>>8
ループと再帰の能力は同じです
かなり古い計算論の結果です
903:デフォルトの名無しさん
21/10/02 15:52:22.08 qz0ghb/n.net
>>894
ゲーデル先生
904:デフォルトの名無しさん
21/10/02 16:12:27.49 qz0ghb/n.net
>>901
結合法則を仮定していいドメインなら
CPS変換を用いて最適化する手法が随分前からあります
結合法則はGPU並列化でも使われてます
浮動小数点の場合は工夫しないと誤差が変わりますが
ちなみにC++ conceptの初期案でもaxiomで法則を記述出来ました
905:ハノン
21/10/02 20:52:53.81 7AkA9F3V.net
>>904
scheme の継続渡しに関係しますか？
キーワードありがとうございます
906:デフォルトの名無しさん
21/10/04 21:48:56.27 tW+d3xqB.net
>>905
そう
Continuation-passing style, defunctionalization, and associativity
Categorical Structure of ContinuationPassing Style
この辺のサンプルプログラム読んで
907:デフォルトの名無しさん
21/11/01 12:26:41.37 ZNnEkaFK.net
履歴をとってるループが再帰
908:デフォルトの名無しさん
22/09/07 22:59:05.75 hj8+EGae.net
すき
しかし再帰絶対書かないマンが思いの外多くて草生えるわ
末尾最適化できない再起をループに展開したって結局キューだのスタックオブジェクトでヒープ使うわけで
メモリ大幅に節約できると勘違いしてる基地外とか話にならん
再帰深度がたかだか1000段とかでスタックフレームにデカいオブジェクトブチ込んだりしなきゃ
素直に再帰で組むのがいいに決まってるじゃないか
数学的演算でもしない限り業務用でスタック溢れるケースを探す方が大変
909:デフォルトの名無しさん
22/09/08 09:28:47.03 JEMfdspa.net
スタックとヒープは別物
共有してるアーキテクチャもあるが
910:デフォルトの名無しさん
22/09/08 13:02:30.59 o4zCWVHV.net
ループに展開できる処理をわざわざ再帰で書く奴も大概やけどな。
911:デフォルトの名無しさん
22/09/08 15:04:24.55 wt4RcFVD.net
展開できないものあるの
912:ハノン
22/09/11 14:15:38.74 gVwBfSXr.net
>>911
二方向に再帰するもの、は展開に苦労しますね
式の評価は、再帰じゃないと書けないですね
913:デフォルトの名無しさん
22/09/15 12:56:10.95 LWNlvRIc.net
てｓｔ
914:デフォルトの名無しさん
24/01/02 13:18:51.50 yx0oLXiq.net
再帰的データ構造は再帰でたどるのが楽なんだけど
ループで処理したほうが途中で抜けたり処理を組み合わせやすい
そこで再帰的な処理を遅延リストと組み合わせてループで処理するやり方がいまでは一般的な気がする
こういうふうに C#
URLﾘﾝｸ(paiza.io)
915:デフォルトの名無しさん
24/01/04 11:34:09.71 iR4GsMlV.net
何が一般的なのか知らんがかなり変態的なコードだな
ループでGetEnumerator呼び出したりMoveNextの戻り値を見ずCurrentを取り出したりは一般的じゃないぞ
つーかバグだろそれ
916:デフォルトの名無しさん
24/11/23 05:47:56.88 dIdD47Ip.net
将棋やオセロ、ぷよぷよなんかは再帰処理使うよね
917:デフォルトの名無しさん
24/12/08 17:57:51.53 EhZF4lXKz
美しいけどね。今のコンパイラでは実行速度はどうだろ。それと、問題によっては
スタックオーバーフローが起きそう。