末尾再帰
俺は「末尾再帰」という言葉を知ってからもしばらく意味がわからんかった。でも「末尾呼び出し」という言葉を知って、簡単に理解できた。
int fact(int x){ if(x == 0) return 1; else return x * fact(x - 1); }
x == 1 じゃなかったときの最後の命令は「*」。fact は末尾呼び出しじゃない。
int fact(int x){ return fact_tail(1, x); } int fact_tail(int a, int x){ if(x == 0) return a; // else return fact(a*x, x - 1); コード間違ってた。正しくは以下。 else return fact_tail(a*x, x - 1); }
の fact_tail で x == 0 だったときの最後の命令は fact 呼び出し。これは末尾呼び出し。ちなみに末尾呼び出しで自身を呼び出す関数のことを特に末尾再帰と言ったりする。
http://karetta.jp/article/book/004664/006762で Shiro さんがちらっとコメントしてるけど、末尾再帰だから最適化できるというか末尾呼び出しだから最適化できる。
普通の関数呼び出し命令っていうのは呼ぶときスタック積んで返すときスタック下ろしてと、オーバーヘッドがかかるわけですね。でも末尾呼び出しはそんな手間のかかる「呼び出し命令」じゃなくてジャンプ命令で関数を呼ぶことができます。以下に例を。
% cat tailcall.c #include <stdio.h> void fuga(){ puts("Hello!"); } void hoge(){ fuga(); fuga(); } int main(){ hoge(); return 0; } % gcc -S tailcall.c % cat tailcall.s .file "tailcall.c" .section .rodata .LC0: .string "Hello!" .text .globl fuga .type fuga, @function fuga: pushl %ebp movl %esp, %ebp subl $8, %esp subl $12, %esp pushl $.LC0 call puts addl $16, %esp leave ret .size fuga, .-fuga .globl hoge .type hoge, @function hoge: pushl %ebp movl %esp, %ebp subl $8, %esp call fuga call fuga leave ret .size hoge, .-hoge .globl main .type main, @function main: pushl %ebp movl %esp, %ebp subl $8, %esp andl $-16, %esp movl $0, %eax subl %eax, %esp call hoge movl $0, %eax leave ret .size main, .-main .section .note.GNU-stack,"",@progbits .ident "GCC: (GNU) 3.3.6 release (Vine Linux 3.3.6-0vl7)"
普通にアセンブルしたら fuga(); は
call fuga call fuga
となってますね。ほんじゃ gcc さんにちょっと頑張ってもらって、
% gcc -S -O2 tailcall.c % cat tailcall.s .file "tailcall.c" .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "Hello!" .text .p2align 2,,3 .globl fuga .type fuga, @function fuga: pushl %ebp movl %esp, %ebp subl $20, %esp pushl $.LC0 call puts leave ret .size fuga, .-fuga .p2align 2,,3 .globl hoge .type hoge, @function hoge: pushl %ebp movl %esp, %ebp subl $8, %esp call fuga leave jmp fuga .size hoge, .-hoge .p2align 2,,3 .globl main .type main, @function main: pushl %ebp movl %esp, %ebp subl $8, %esp andl $-16, %esp call hoge xorl %eax, %eax leave ret .size main, .-main .section .note.GNU-stack,"",@progbits .ident "GCC: (GNU) 3.3.6 release (Vine Linux 3.3.6-0vl7)"
なんと末尾呼び出しの fuga() が jmp 命令に置き換わってますね。
call fuga leave jmp fuga
そんなわけで関数呼び出しのコストが減ってうれしいなあと。
ほんで末尾呼び出しがジャンプ命令になるならば、末尾再帰は単純なループになるっていうのは自明なことですね。
fuga の puts も末尾呼び出しだけど、あっちはもう puts の実体が「スタックから引数下ろしてきてコード実行!」みたいになってるからジャンプ命令には置き換わりません。
たぶんこんなかんじ。