アカウント名:
パスワード:
末尾再帰の最適化は関数コール命令をジャンプ命令に置き換える処理です
C言語で書くと、たとえば
int foo(int x){ if (x==1) return x; else return x * foo(x-1);}
これを
int foo(int x){ int ret = x;loop: if (x==1) return ret; else { x
しれっといい加減なことを書くな。
そのループに展開したものに相当するのは、
int foo(int x) { loop(x, x);} int loop(int x, int ret) { if (x == 1) return ret; else return loop(x - 1, (x - 1) * ret);}
元のコードは末尾再帰ではない。末尾再帰は呼び出した関数の戻り値がそのまま呼び出した側の関数の戻り値になる場合。元のコードでは"x * "が関数の呼び出し後に実行されるため、呼び出した関数の戻り値が来るまでxをスタックに残す必要があり、最適化はできない。
元のコードの末尾再帰バージョンは、
int foo(int x) { loop(x, 1);} int loop(int x, int ret) { if (x == 1) return ret; else loop(x - 1, x * ret));}
こう書くと、最適化のレベル次第で、ループに変換されるようになる。
>最適化のレベル次第で、ループに変換されるようになる。C言語の処理系が末尾再帰最適化をしてくれる印象がなかったが、最近のgccは最適化してくれる [srad.jp]のか。(Ver.3から [ameblo.jp]となるとリリースが2001年 [gnu.org]なので「最近」でもないが。)
しかしgccで最適化するとコンパイラのバグ [goo.ne.jp]踏む印象もある。
あんたの説明もいうほど適切ではないやろ。その説明の仕方だと再帰と末尾再帰の違いはともかく相互末尾再帰が登場したあたりで結局詰む。昔の大学カリキュラムの再帰 → オートマトン → 構文解析と続くあたりで理解が追いつかなくなって落ちこぼれるパティーン。てかそもそも末尾再帰の説明するのに「スタック」いいだしたあたりでLisperからすると失笑レベル。
末尾再帰そのものの話ではなくて最適化の話。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
あと、僕は馬鹿なことをするのは嫌いですよ (わざとやるとき以外は)。-- Larry Wall
関数呼び出しをジャンプ(goto)に書き換えるだけ (スコア:0)
末尾再帰の最適化は関数コール命令をジャンプ命令に置き換える処理です
C言語で書くと、たとえば
int foo(int x){
if (x==1)
return x;
else
return x * foo(x-1);
}
これを
int foo(int x){
int ret = x;
loop:
if (x==1)
return ret;
else {
x
Re:関数呼び出しをジャンプ(goto)に書き換えるだけ (スコア:0)
しれっといい加減なことを書くな。
そのループに展開したものに相当するのは、
元のコードは末尾再帰ではない。末尾再帰は呼び出した関数の戻り値がそのまま呼び出した側の関数の戻り値になる場合。元のコードでは"x * "が関数の呼び出し後に実行されるため、呼び出した関数の戻り値が来るまでxをスタックに残す必要があり、最適化はできない。
元のコードの末尾再帰バージョンは、
こう書くと、最適化のレベル次第で、ループに変換されるようになる。
Re:関数呼び出しをジャンプ(goto)に書き換えるだけ (スコア:1)
>最適化のレベル次第で、ループに変換されるようになる。
C言語の処理系が末尾再帰最適化をしてくれる印象がなかったが、最近のgccは最適化してくれる [srad.jp]のか。
(Ver.3から [ameblo.jp]となるとリリースが2001年 [gnu.org]なので「最近」でもないが。)
しかしgccで最適化するとコンパイラのバグ [goo.ne.jp]踏む印象もある。
Re: (スコア:0)
あんたの説明もいうほど適切ではないやろ。
その説明の仕方だと再帰と末尾再帰の違いはともかく相互末尾再帰が登場したあたりで結局詰む。
昔の大学カリキュラムの再帰 → オートマトン → 構文解析と続くあたりで理解が追いつかなくなって落ちこぼれるパティーン。
てかそもそも末尾再帰の説明するのに「スタック」いいだしたあたりでLisperからすると失笑レベル。
Re: (スコア:0)
末尾再帰そのものの話ではなくて最適化の話。