Tail Recursion とは
末尾再帰とは、関数の最後の命令がその関数自身の呼び出しであるような再帰呼び出しのことです。バイナリアン的には、どのように最適化されるかが面白いところですので、「末尾再帰は最適化できる」というスタンスで紹介します。
最適化オプションを付けることが前提になること、最適化されなかったときにスタックを予想以上に使い見つけにくいバグになるため、組み込みではあまり使われないテクニックです。
最適化無しの場合
教科書に載っているソースはこちらになります。
int sum(int n, int acc); int main(void) { return sum(3,0); } int sum(int n, int acc){ if (n > 0) return sum(n - 1, acc + n); else return acc; }
引数として、nと0を与えると1〜nまでの和を返します。二つ目の引数accは、アキュムレータとして途中の計算結果を渡すのに使われます。引数が(3,0)の場合は、sum(3,0)→sum(2,3)→sum(1,5)→sum(0,6)の順に呼び出され、最終的に6が返ります。
最適化無しでコンパイルするとこうなります。
sum: addiu $sp,$sp,-32 sw $31,28($sp) sw $fp,24($sp) move $fp,$sp sw $4,32($fp) sw $5,36($fp) lw $2,32($fp) blez $2,.L3 nop lw $2,32($fp) addiu $4,$2,-1 lw $3,36($fp) lw $2,32($fp) addu $2,$3,$2 move $5,$2 jal sum # 再帰で関数呼び出し nop sw $2,16($fp) b .L2 nop .L3: lw $2,36($fp) sw $2,16($fp) .L2: lw $2,16($fp) move $sp,$fp lw $31,28($sp) lw $fp,24($sp) addiu $sp,$sp,32 j $31 nop
jal命令により自分自身を関数呼び出しています。
最適化無しのスタックの状態
n=3の時、再帰呼び出しが最も深い状態でのスタックの様子をpcspimで見てみました。
右上の青線がスタックポインタで、スタックのトップは0x7fffeec8を指しています。下の欄がスタックメモリのダンプになります。
n=3の時、上に書いたように4回のsum()の呼出があります。また、最適化無しですのでsum()の引数もいったんスタックにコピーされています。引数のコピーと戻り番地が保存されている所に赤線を入れています。上3つの0x0040009cが再帰呼び出しを一つ戻るときの戻り番地、一番下の0x00400040がsum()からmain()に戻る時の戻り番地になります。再帰でsum()を呼び出す度に、スタックを使用していくのが分かります。
最適化した場合
-O2 をつけてコンパイルするとこうなります。
sum: b .L3 move $2,$5 .L6: addiu $4,$4,-1 # $4の値を1引く move $2,$3 .L3: addu $3,$2,$4 # $4の値を$2に加える bgtz $4,.L6 # $4が0より大きいならL6に戻る nop j $31 # $4が0以下なら関数から戻る nop
いきなりジャンプするという小技を入れながらも、関数呼び出しであるjal命令が無くなっています。代わりにbgtz命令によるループに置き換えられています。わかりやすい形で末尾再帰の最適化が実行されています。
最適化有りのスタックの状態
同じくループを出る直前のスタックの様子を、pcspimで見てみました。
青線のスタックポインタは0x7fffef40を指しています。最適化しない時のスタックポインタ（0x7fffeec8)に比べると、0x78=120バイト分スタックの使用量が減っています。末尾再帰の以外の最適化の影響もあるので、120バイトという値そのものにはあまり意味はありません。最適化無しの場合、再帰の度に戻り番地としてスタックを使用するのに対し、最適化を有効にすることで戻り番地の保存がなくなり、ループの回数に依らずスタックの使用量は一定になりした。
最適化された結果、sum()は他の関数を呼び出さないleaf-functionになったので、戻り番地は赤線のr31に保存されています。
pcspimの問題点
sde-gccでコンパイルすると、実は.L3部分はこうなります。
.L3: bgtz $4,.L6 # $4が0より大きいならL6に戻る addu $3,$2,$4 # $4の値を$2に加える
bgtzで比較しながら、遅延スロットを使ってaddu命令を実行しています。この遅延スロットがpcspimでは実行されていないようで、そのままでは上手く動きません。命令を入れ替え、遅延スロットにはnopを入れることで動作を確認しました。
末尾再帰のリンク
ひげぽん OSとか作っちゃうかMona- 末尾再帰
より詳しい説明はここがまとまっています。リンク先のリンクもあわせて読むと面白いです。
http://d.hatena.ne.jp/higepon/20070815/1187192864
なんでも再帰
Schemeの場合、最適化テクニックの一つではなく、処理系としての必須条件に入ります。Cの最適化とは違う雰囲気があって面白いです。
http://practical-scheme.net/docs/tailcall-j.html
「末尾再帰がループと同等に実行されるのは、コンパイラによるオプショナルな最適化ではない。 Schemeは、末尾呼び出しでスタックを消費しないことを言語規格上要求している。」
Derive Your Dreams
実践的な例として印象に残っているのがこちら。シェルの実装に末尾再帰を使うというエピソードです。
http://www.kmonos.net/wlog/81.html#_1247080126
