C++相談室 part149
レス数が950を超えています。1000を超えると書き込みができなくなります。
>>851
そこを指摘したつもりじゃなかったんだけど、確かにセミコロン抜けてるね。
> C * ptr = &c 言語についてあれこれ言うなら今時は必要な視点だろ。
20年前で時間が止まってんのかね。 コードのチェックについてはその後反省して改善したらしいよ。
https://cpplover.blogspot.com/2016/09/c17.html
> 参考書のソースコードからサンプルコードを抽出してコンパイルするテストは、適当なツールがなかったので適当に実装した。C++で書いて200行ぐらいだった。 ストラウストラップの本こき下ろしてたクセにテメェもろくな本書けないっていう
ストラウストラップの本拾い読みする方が何万倍ありがたいわな 江添さんのC++入門本を読んでいますが、「末尾再帰」を完全に間違えていますね…
私と同じ間違え方でしたが、私以外にも間違える人がまだ居るようですね
view-source:https://ezoeryou.github.io/cpp-intro/#再帰関数
＞int factorial( int n )
＞{
＞ if ( n < 1 )
＞ return 0 ;
＞ else if ( n == 1 )
＞ return 1 ;
＞ else
＞ return n * factorial(n-1) ;
＞}
＞この関数は、引数nが1未満であれば引数が間違っているので0を返す。そうでない場合でnが1であれば1を返す。それ以外の場合、n * factorial(n-1)を返す。
＞このコードは末尾再帰になっている。 ええ・・・本にする前に誰も気付かんかったんか・・・ >>860
ところでそのケースは末尾再帰ではないが、
gcc で -O2 を付けるとループに最適化するんだ。
賢いなぁ！ 大抵一番目の引数はレジスタで代用したりする最適化するよね >>864
それは最適化ではなくABIで決まっていることでは >>860
>return n * factorial(n-1) ;
n を掛けたら、ダメなのか。
return factorial(引数)としないといけないのか
関数の引数に、蓄積器を持つように、変形しないといけないのか スタックが何を保持しとかないといけないか考えたらわかることだけどね。 >>867
末尾で呼び出した関数の返却値を「何も加工せずに」そのまま返却値にするような場合は、
素朴なスタックを使う ABI だと積んだのを直後に降ろす操作になるだけなんだ。
だから相殺してスタック操作を消せる。 call と ret からスタック操作を消すとジャンプになるという理屈。
Wikipedia の説明とかを見てもわかりにくいんだけど、スタックの動きで考えるとわかりやすいと私は思う。 >>869
32BIT の x86のアセンブラで書けば、
push dword ptr a2
push dword ptr a1
call func_addr
add esp,8
ret
となっているのを
mov eax,a1
mov [ebp+xxx1],eax // xxx1は仮引数1のスタック上の相対位置
mov eax,a2
mov [ebp+xxx2],eax // xxx2は仮引数2のスタック上の相対位置
jmp func_addr
などとすると。再帰を行わなくても
return retcode; 文は、
mov eax,retcode
add esp,8
ret
とコンパイルされるから、結局等価になる。 コンパイラに「inline指定された部分がインライン化できなかったら警告」
みたいなオプションがあるけど、それと同様に、
プログラマが末尾再帰のつもりで書いた関数(ソースに明示する)が
実際には末尾再帰じゃない場合に指摘してくれるような機能はないじゃろか。
最適化機構の中でチェックできてるはずだし、学習の役立ちそうな気がする。
末尾再帰に慣れた人には不要な補助輪だろうけど。 二本のスタックを使って木をコピーする方法を思いついてしまったかもしれない。 心底どうでもいい機能を無駄に入れようとするな
そんなことするくらいなら自力で再帰でない書き方する方がまともな対応
スタック消費を気にするなら再帰で書こうとすること自体が間違ってる 江添さんがこのスレを見てれば委員会に提案してくれるかも。 明示的にオーバーライドしないとできない様に制限する機能ってないの？
たまに同名同タイプで気づかずにオーバーライドしてしまった事があるんだが。 規格はコンパイラの警告は決めてない
警告機能が欲しいならコンパイラの開発者に要望を出すんだな >>1
アセンブリファイル出力を行うようにコンパイルオプションを設定して、自分で出力アセンブリコードを見ればいいだけ。 意図したとおりの訳になったかどうかが問題になるのはスポットで全域じゃないからな
ただ、そういう箇所はコンパイラの出力を参考にアセンブラで書くべきだと思うが >>875 gcc の ver.5 だと -Wsuggest-override って警告オプションがあるね。
これと警告をエラー扱いにする指定を組み合わせればいいのかな。 別に
アーキテクチャ依存の話を持ち出さずとも、
fractional(n) = n * fractional(n-1)
とゆー事実をもってただちにfractional(n)は末尾再起と言える
なぜなら
fractional(n) = n * ((n-1) * fractional(n-2))
= n * ((n-1) * ((n-2) * fractional(n-3)))
= ....
となってfractional(0)に至るまで延々展開でき、*が可換である故にこれは
fractional(n) = n * (n-1) * fractional(n-2)
= n * (n-1) * (n-2) * fractional(n-3)
= ....
となって右端を延々展開して「も」得られるからである
*の可換性への依存を良しとしない立場をとったとたん、末尾再起関数と認められるものは
f(n) = f(n-1)
とゆーnに関する恒等写像のみとなる
そう言いたいのであれば別に止めはしないがそっちの方が異端じゃないの；
つまり頭おかしい >>881
>>881
＞fractional(n) = n * fractional(n-1)
fractional(n-1) から値が帰ってきたあと、その値と n とを掛け合わせる計算は fractional(n) の関数内で実施しているでしょう？
コールした関数から戻ったときに、そのままなにもせずに得た値をリターンするのならば末尾再帰ですが、
この場合は得た値を加工してからリターンするのだから、これは末尾再帰とはいいません
＞ fractional(n) = n * (n-1) * fractional(n-2)
＞ = n * (n-1) * (n-2) * fractional(n-3)
＞= ....
＞となって右端を延々展開して「も」得られるからである
展開可能であることと末尾再帰であることはなんの関係もありません
＞*の可換性への依存を良しとしない立場をとったとたん、末尾再起関数と認められるものは
＞ f(n) = f(n-1)
＞とゆーnに関する恒等写像のみとなる
* の可換性はなんの関係もありません
引数を一つに限定するのならそうですが、プログラム言語は引数を二つ以上持ってもいい
普通は f() の引数を二つ以上とって、その中にアーキュムレータを置いて末尾再帰にします。
f(s, t) = f(u, v) = f(w, x) = …
むしろこっちの方が普通の末尾再帰といっていいでしょう >展開可能であることと末尾再帰であることはなんの関係もありません
>* の可換性はなんの関係もありません
大きく出たな…
まず右端展開の繰り返しにより表現可能でありかつ末尾再起化できない関数というものは無い
なぜなら、右端展開の繰り返しを手続き的に書けばループに他ならんぬ、、、
逆も真で、ループとして書ける関数なら右端展開の繰り返しとしても表せるんであーる
つまり、右端展開の繰り返しにより表現可能であることと、末尾再起化できる関数というものは同値
で、アキュムレータを使った複数引数の関数化というものは、関数の表現を右端展開繰り返し可能な形に直しているにすぎない
で、右端展開の繰り返しにより表現可能かどうかには演算子の結合則が関係する例は
>>881に挙げたとーり
実際、演算子の結合則が成り立たない例として、Aが行列でIが単位行列のとき
fractional3(A) = fractional3(A - I) (A - I) ・・・(1)
というﾌﾞﾂを考えると、この関数は右端展開可能でないからもはや末尾再帰化はできない
Aが実数でIが1なら末尾再帰化できるのに…！ 末尾再帰であることと末尾再帰に変換できることは区別しようや 末尾再帰に書き換えられることなんか誰も否定してないのに一人で暴れてる 訂正orz、
×： 結合則
○： 交換則
あとなんか式(1)は末尾再帰化可能な気がしてきたorz そりゃ交換則なんか末尾最適化に何の関係もないからな >>883
＞まず右端展開の繰り返しにより表現可能でありかつ末尾再起化できない関数というものは無い
＞なぜなら、右端展開の繰り返しを手続き的に書けばループに他ならんぬ、、、
理解が粗いと思います
あなたのいう「右端展開」が繰り返し適応可能であればループに展開できる…①
と置いたとき、
①が事実だったとしても、それは末尾再帰となんの関係もありません
末尾再帰の最適化とは関数コール命令＋関数リターン命令（call ～ ret) をジャンプ命令に変換するという最適化でしかなく、
再帰的に記述された関数定義をループに変換する最適化の集合を「末尾再帰という」、わけではないのです
あなたは末尾再帰を広く捉えすぎです >>888
ちょっCPSって継続と書いてある
右端展開の繰り返し表現可能ということと、継続で表せることは自明な勢いで同値なのでは…
つまり漏れの面の皮を通って赤面させるほどの目新しさのインパクトは無いｷﾓｽ、
>>889
AとBに何の関係も無い、とは、Aの真偽とBの真偽が独立のことを言うはず…
この場合「右端展開の繰り返しで表現可能」と「ループに展開できる」ことが同値なのであるから、
何の関係も無いというのは強弁に過ぎるのでは…
>末尾再帰の最適化とは関数コール命令＋関数リターン命令（call ～ ret) をジャンプ命令に変換するという最適化でしかなく
最適化した結果のみを末尾再帰というのであれば狭く捉え過ぎｗｗｗｗｗｗ
徹頭徹尾アセンブラで議論してろよ；；
そうではなくて末尾再帰の最適化の話に限定するのであればスレを分けた方が適切なのでは… >>890
＞この場合「右端展開の繰り返しで表現可能」と「ループに展開できる」ことが同値なのであるから、
＞何の関係も無いというのは強弁に過ぎるのでは…
>>889 はそんなことを言ってはいません
＞「右端展開の繰り返しで表現可能」であれば「ループに展開できる」できる…①
とおいたとき、
①と末尾再帰とが、何の関係もない、といっているのです
＞最適化した結果のみを末尾再帰というのであれば狭く捉え過ぎｗｗｗｗｗｗ
＞徹頭徹尾アセンブラで議論してろよ；；
最適化を実施するのに、あれこれ解析する必要がなく機械的な命令の置き換え／書き換えだけで可能である、というのが末尾再帰の肝です
まあアセンブラを理解できないようでは C/C++ の理解も薄い弱い、とは思ってはいますが
＞そうではなくて末尾再帰の最適化の話に限定するのであればスレを分けた方が適切なのでは…
まず、末尾再帰とはなにか？を両者で合致するように合意をとるのが先決でしょう 厨二プログラマが食いつきやすい三大話題
・再帰
・例外処理
・
おっさんプログラマが食いつきやすい三大話題
・インデントルール
・命名規則
・ >893はID:vZ2zRqlYが指を咥えて見てるだけの話題 厨二プログラマが食いつきやすい三大話題
・再帰
・例外処理
・標準化委員会
おっさんプログラマが食いつきやすい三大話題
・インデントルール
・命名規則
・原点回帰 厨二にもおっさんにもボコボコにされるだけで歯が立たないやつ悔しそう もっと簡単に考えろ
一般に再帰は階層に復帰したときに必ず元の状態に戻さなければならない
復帰後の階層固有の計算に必要だからだ
しかし復帰後に階層固有の計算がない末尾再帰は戻す必要がない
よってループで書けるというだけの話だ
これを順序非可換の問題ととらえることはまあ理にかなっている
以下左が末尾
f(n+1)x=f(n)h(n)g(n)x≠h(n)f(n)g(n)x
f(n+1)x=h(n)f(n)g(n)x=h(n)h(n-1)f(n-1)g(n-1)g(n)x
f(n+1)x=f(n)h(n)g(n)x=f(n-1)h(n-1)g(n-1)h(n)g(n)x
h(n)h(n-1)が可能であるためにはスタックの復帰が必要よって示された あなた達の話は難しくてよくわかりません！
簡潔に説明すると末尾再帰ってなんなんですか？
普通の再帰と違ってスタックオーバーフローが避けられるってこと？ >>895
そしてテスト、保守性といったものには誰も興味を持たないのである。おしまい。 >>898から、>>860は末尾再帰であると言える
g(n)x=nx,h(n)x=xと考える >>901 あんたきのうの>881だよね？
たぶん「末尾再帰」の定義が他の人（たとえば Wikipedia の「自身の再帰呼び出しが、
その計算における最後のステップになっているような再帰」）と違いそうだから、まず定義を示してもらいたい。 いや違うよ
級数積が関数という認識があるかないかが彼とは違う 違うのか、悪かった。
で、あんたの「末尾再帰」の定義はどうなってんの？ その昔、こんな再帰もやったがｗ
JSREE EQU *
* DO PREPARE
BSR *+2
* DO SOMETHING
RTS 「自身の再帰呼び出しが、その計算における最後のステップになっているような再帰」
に異論ない。言葉通りだ
ただしそう定義したものは、>>898の性質を持つ >>906
そうなると >860 の "return n * factorial(n-1) ;" における「最後のステップ」は
再帰呼び出しではなく乗算なので、その末尾再帰の定義には合致しないのでは？ >>901を適用して
f(n+1)x=f(n)g(n)x
g(n)x=x'
として、
f(n+1)x=f(n)x'
と書けば納得いただけるだろうか >>908 いやサッパリ。
その g やら x やらが >860 の関数とどう関係してるか、示されてないように思うし、
関係が示されたところで "return n * factorial(n-1) ;" の最終ステップが何であるかに
影響するとは思えない。 こう書いた方がよかったかな
f(n+1)x=f(n)g(n)x
f(n)g(n)=h(n)として
h(n+1)x=h(n)x
具体的には
(n+1)f(n+1)x=nf(n)x
例外は最上位の呼び出し元だけがf(n)xになっていることで、
実質h(n)=n * factorial(n-1)という関数の末尾再帰になっている f(n)xはf(n)の結果にxを掛けるんだからf(n)が最終ステップじゃないだろ まずfactorialを末尾再帰に書き換えられるって話なら、そんなの当たり前だし誰も否定してない
それに加えてお前の書き換え方はおかしい
二重に話が噛み合ってなくて訳がわからない
宇宙人か？ おそらくわからないという人は、
末尾再帰⇔ループ
の書き換えがどうなっているのかわかっていない
末尾再帰な関数は、関数の戻り値以外のローカル変数はすべて再利用可能であるのでスタックする必要がない
そしてreturnが返しているのは戻り値である
ｎ*はリターン値に含まれている
よってn * factorial(n-1)は一つの関数単位として扱われ得る
実際にそう扱っているかどうかは実装によるだろうが末尾再帰な関数の定義からは漏れていない >>915
仮に「n * factorial(n-1)は一つの関数単位として扱われ得る」を認めたところで
最終ステップはその「関数単位」とやらであって「自身の再帰呼び出し」ではないので、
末尾再帰とは言えないよね。
・・・ >860 を末尾再帰と言えないと死ぬ病気か何かなの？ >>916
factorialの呼び元は大本の読み出し元以外はすべてnがかかっていること
実際にループに書き換えられること
よって>>860を否定する必要はないというだけのこと
否定する必要があるならそれでもいいが意味はあるか？ >ｎ*はリターン値に含まれている
>よってn * factorial(n-1)は一つの関数単位として扱われ得る
リターン値に含まれていようが関数の呼び出しに含まれていなんだから「一つの関数単位」にはならんわな。 そもそもこの人の数学とやらが意味不明
> (n+1)f(n+1)x=nf(n)x
乗算なのか関数の適用なのかどっちだこれ？
左辺の(n+1)はどっからでてきたんだよ >>917
ループに書き換えられれば末尾再帰と言えるんならやっぱり Wikipedia の定義と違うんじゃん。
「>>860は末尾再帰であると言える」を否定しないと「末尾再帰」の定義（共通認識）が変わってしまうし、
共通認識を壊す行いを認めることになる。それは害悪。やめてほしい。 末尾再帰とかschemeじゃないと意味無い話
末尾再帰だとループに最適化されることが言語で保証されてるって前提なのだから
そこで言う末尾再帰ではn*f(n-1)みたいなのは違う
だから変形して末尾再帰にしろって話になるのだから >>920
それは
return n * factorial(n-1);
と書いてはいけないと強制するということだろうか
だとしたらそれは間違っている
末尾再帰の定義を満たしているにもかかわらず認めないということはそういうことだ 末尾再帰は関数の最後で自身を呼び出してそれをそのままreturnするものだけ
末尾再帰に変形できる関数は末尾再帰に変形できる関数であって、末尾再帰関数ではない >>922
強制とか間違ってるとか認めないとか
お前は誰と戦ってんの？
誰もそんな話してないんだが
読んでで怖いわ >>923
それでいいと思う
だがだとすれば君らは何がわからなかったのかそれがわからない >>915
＞ｎ*はリターン値に含まれている
＞よってn * factorial(n-1)は一つの関数単位として扱われ得る
return 式
の式に全部書いてしまえるからといっても、その式の中に存在する演算が複数あれば、それぞれの演算に順序があるわけですから
一つに扱うことはできないでしょう、この場合、リターン値を得た後で * n しているのだから、これは一つじゃなく二つ
したがって >>902 の末尾再帰の定義
＞「自身の再帰呼び出しが、その計算における最後のステップになっているような再帰」
には合致せず（なぜならば、この場合の最終ステップは * n をすることだから）、>>860 で引用されたプログラムは末尾再帰ではありませんね >>922
＞それは
＞return n * factorial(n-1);
＞と書いてはいけないと強制するということだろうか
いいえ、単に return * factorial(n-1) と書くのならば、末尾再帰ではなくなるというだけのことです。
＞末尾再帰の定義を満たしているにもかかわらず認めないということはそういうことだ
もう一度ききましょう、あなたの「末尾再帰」の定義は何ですか？ >>927
あなたのいう、「関数」の定義は何ですか
わたしはn * factorial(n-1)は関数だと思います やっぱりこいつ、末尾再帰と末尾呼び出しの区別がついていないとしか思えない >わたしはn * factorial(n-1)は関数だと思います
これがfractional自身とは異なる以上、末尾再帰にはならんわけ。 >>931
では何がわからなくてここまでの長い議論をしていたのですか？
末尾再帰が理解したいというのなら、定義そのままを暗記するだけで済んだはず
一連の私の書き込みは単に理解の方法を提示したに過ぎず、
それを否定するということは定義が理解できていたということでしょう？ 中置で書くから分かりづらくなる
ポーランドか逆ポーランドで書けば自明なのに >>928
＞あなたのいう、「関数」の定義は何ですか
＞わたしはn * factorial(n-1)は関数だと思います
仮に関数の定義をあきらかにしたからといっても、それは末尾再帰の定義とは関係ないでしょうね
繰り返しますが、末尾再帰の定義は >>902
＞＞「自身の再帰呼び出しが、その計算における最後のステップになっているような再帰」
であり、>>860 で引用されたプログラムの「自身の再帰呼び出し」すなわち「return n * factorial(n-1);」
は、計算における最後のステップになっていない（なぜならば、最後のステップはこの場合 n * であるから）ので、
>>860 で引用されたプログラムは末尾再帰ではありませんね >>932
>>860は末尾再帰にならないということをアンタだけが理解できていないというだけ。 >>934
それを最初から言っていれば、ここまでの無意味な議論はしなくて済んだでしょうね
よって示された 逆になぜ末尾再帰にするかを考えれば、>>934の制限は強すぎる ID:QlEyGkfmは何でもかんでもここのみんなに教えてもらおうとせず
まず落ち着いて自分のペースでしっかり考えてみたらどうかな
みんな呆れてるよ >>938
昔私が末尾再帰を間違えていたとき、当時からこのコテで煽り気味にやっていたにもかかわらず、最上級の親切を示して
「末尾再帰はジャンプ最適化だ！」
と教えてくださった方がおられました、当時のその方ほどの忍耐力を今回発揮できず、申し訳ございません… 皆さんこそ落ち着いてください
nはスタック変数ではなく、ループのインクリメント変数なんですよ 「末尾再帰」という情報処理用語を定義しているJIS規格票もしくは
"tail recursion" という情報処理用語を定義しているISO規格票の
条項を出せるやついるの？
これだけ上から目線でマウント取っといて
あげくオレ用語だったら恥ずかしいぞ 江添が間違えたのが全部悪い
奴が間違えてなければ同じ勘違いをした気違いを呼び寄せることもなかった 江添氏は勘違いと言うより
末尾再帰というもんを単に知らなかったのではと思ってる
末尾再帰の最適化が保証されてる言語使ってる人じゃないだろうから 消費税の計算を例題にあげたけど、計算方法間違ってたみたいなもの
c++的には関係ない分野の知識 蒸し返して悪いんだけど
>>898 の数式解読できる人いる？
この人何を勘違いしてんのか興味でてきたんだが 「添字を持つ添字」みたいなもんを上手に管理する方法ってある？
例えば、
0 <= i < n である全ての i について a[i] を 0 から m の範囲で動かす
みたいなループの構造を想定してる。
当然大きな多重ループになるから小さい n と m についてしか使えないと思うけど、デバッグなどのときにこういうのを簡潔にミスらず書けたらと思っての質問です >>947
> a[i] を 0 から m の範囲で動かす
これの意味がわからない
具体例書いて >>948
for(a=0; a<m; a++)
for(b=0; b<m; b++)
for(c=0; c<m; c++)
...
という形の多重ループのループ変数 a, b, c,... を a[0], a[1], a[2],... にしたいという意味です。
TeX の文法で数式を書けば
\prod_{i=0}^{n} \sum_{a[i]=0}^{m}
という意味です。
・数式との対応が分かりやすい形で書きたい
・簡潔でミスしにくい形で書きたい
といった理由で質問させていただいてます。 >>948-949
すみません。必ずしも和をとりたいだけではないので、式はあくまで例です。
あとレンジが1つずれてるのもすみません。 >という形の多重ループのループ変数 a, b, c,... を a[0], a[1], a[2],... にしたいという意味です。
やればいいだけの話じゃなくて？質問は何だろう。 レス数が950を超えています。1000を超えると書き込みができなくなります。
