アカウント名:
パスワード:
末尾再帰の最適化は関数コール命令をジャンプ命令に置き換える処理です
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 = x-1; ret *= x; goto loop; }}
と変換していることに相当します。
原理的には、関数呼び出しがスタックを浪費するから、ジャンプ命令に置き換えましょう、って事です
C言語のコンパイラ的には、最適化前のfoo()に対応するアセンブラと最適化後のfoo()に対応するアセンブラはかなり似たものになります。上記の例だと int ret = x; に対応する機械語は最適化前のfoo()にも含まれているので最適化による違いは goto の部分だけになります。
しれっといい加減なことを書くな。
そのループに展開したものに相当するのは、
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);}
>最適化のレベル次第で、ループに変換されるようになる。C言語の処理系が末尾再帰最適化をしてくれる印象がなかったが、最近のgccは最適化してくれる [srad.jp]のか。(Ver.3から [ameblo.jp]となるとリリースが2001年 [gnu.org]なので「最近」でもないが。)
しかしgccで最適化するとコンパイラのバグ [goo.ne.jp]踏む印象もある。
あんたの説明もいうほど適切ではないやろ。その説明の仕方だと再帰と末尾再帰の違いはともかく相互末尾再帰が登場したあたりで結局詰む。昔の大学カリキュラムの再帰 → オートマトン → 構文解析と続くあたりで理解が追いつかなくなって落ちこぼれるパティーン。てかそもそも末尾再帰の説明するのに「スタック」いいだしたあたりでLisperからすると失笑レベル。
末尾再帰そのものの話ではなくて最適化の話。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
吾輩はリファレンスである。名前はまだ無い -- perlの中の人
関数呼び出しをジャンプ(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 = x-1;
ret *= x;
goto loop;
}
}
と変換していることに相当します。
原理的には、関数呼び出しがスタックを浪費するから、ジャンプ命令に置き換えましょう、って事です
C言語のコンパイラ的には、最適化前のfoo()に対応するアセンブラと
最適化後のfoo()に対応するアセンブラはかなり似たものになります。
上記の例だと int ret = x; に対応する機械語は最適化前のfoo()にも含まれているので
最適化による違いは goto の部分だけになります。
Re: (スコア: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)
末尾再帰そのものの話ではなくて最適化の話。