末尾再帰

hoge

俺は「末尾再帰」という言葉を知ってからもしばらく意味がわからんかった。でも「末尾呼び出し」という言葉を知って、簡単に理解できた。

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 の実体が「スタックから引数下ろしてきてコード実行！」みたいになってるからジャンプ命令には置き換わりません。


たぶんこんなかんじ。

test