パイパーのパイ

再帰

関数が自分自身を呼び出すとき、その関数は再帰的であると言います。

関数呼び出しとループの大きな違いの1つは、関数を呼び出すと戻り先のアドレスがスタックに積まれることです。 つまり、再帰関数は通常、同等のループよりも多くのスタック領域を必要とします。

その結果、自分自身を呼び続ける関数は、やがてスタック領域を使い果たしてしまうことがあります。 これをスタックオーバーフローと呼びます。

だからこそ、すべての再帰関数には少なくとも1つのベースケースが必要です。ベースケースとは、関数が自分自身を呼び出さずに戻る場合のことです。 再帰呼び出しは、最終的に必ずベースケースに到達しなければなりません。

たとえば、階乗関数n! = n * (n - 1) * ... * 1は、1をベースケースとして再帰的に定義できます。

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

factorialは、再帰する前にpush rdiをし、再帰した後にpop rdiをする必要があることに注意してください。 これは、再帰呼び出しから戻った後にn * (n-1)!を計算するために、まだnが必要だからです。

また、呼び出し先保存レジスタを使ってもこの問題は解決しないことにも注意してください。

再帰関数は自分自身を呼び出す可能性のある呼び出し元ですが、それ自身は別の関数から見た呼び出し先でもあります。 つまり、その関数は呼び出し先保存レジスタを使う前に保存し、使い終わった後に値を復元しなければなりません。 これは通常、以前のコンセプトで見たように、push/popの組み合わせで行います。

再帰関数の各フレームは、ベースケースを除いて、それぞれが自分のローカル変数を保存する必要のある呼び出し元でもあるので、このpush/popの組み合わせはフレームごとに繰り返さなければなりません。 レジスタを使わずに変数を直接スタックに保存したとしても、フレームごとに同じ8バイトが必要になります。

つまり、再帰呼び出しのたびに、callが積む戻り先アドレスのために8バイト、さらに保存が必要なローカル変数ごとに8バイトがスタックに加わります。 関数はベースケースに到達するまで、フレームごとにこれらのバイトをスタックに加え続けます。 そしてようやく、逆の順序で巻き戻り始めます。各再帰呼び出しは必要なだけpopを行い、その後retします。

たとえば、factorialを引数10で呼び出すと、ベースケースの1に到達するまでに9回自分自身を呼び出します。 この時点で、それまでの各フレームのn（8バイト）と戻り先アドレス（8バイト）を保存するために、144バイトが使われていることになります。

末尾呼び出し

状況によっては、関数が別の関数を呼び出した後、戻るまでの間に何も作業を行わないことがあります。

たとえば、次の例を見てみましょう。

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

triple_of_square関数は、次のことをします。

• 渡された引数（rdi内）をそれ自身と掛け合わせ、その2乗を求めます。
• 次にtimes_threeを呼び出します。これは渡された引数に3を掛けた値を返します。

その結果、triple_of_squareは3*x²を返します。ここでxは、rdiで渡された引数です。

triple_of_squareでは、times_threeを呼び出した後に何も作業を行わず、ただ戻るだけであることに注意してください。 このような場合、callを使う代わりに、jmpを使って呼び出される関数に実行を移すことができます。

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

これを末尾呼び出しと呼びます。

末尾呼び出しの主な利点は、callの余分なコストを避けられることです。 callは戻り先アドレスをスタックに積み、その地点に制御を戻すためには、対応するretが必要です。

末尾呼び出しはそのどちらも省きます。積むべき戻り先アドレスも、対応させる余分なretもなく、呼び出される関数自身のretだけがあります。

末尾再帰

末尾呼び出しは、戻るまでに何度も自分自身を呼び出す可能性のある再帰関数で特に役立ちます。

ただし、すべての再帰呼び出しがそのまま末尾呼び出しに変換できるわけではありません。 jmpは呼び出される関数に制御を移すので、呼び出し元は末尾呼び出しの後に何も作業を行えません。

たとえば、先ほどのfactorial関数は末尾再帰ではありません。 再帰呼び出しの後、imul rax, rdiを使って、結果と現在のnを掛け合わせる必要がまだあります。

このような場合、部分的な計算結果を集めて最後に返すアキュムレーターを使えることがあります。 たとえば、作業のほとんどを行うfactorial_helperを定義し、factorialがアキュムレーターを用意してfactorial_helperに制御を移すようにできます。

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

再帰呼び出しの後に何も作業を行わないので、rdiを保存する必要もなくなります。 callもpush rdiもないので、再帰の各繰り返しでスタックに加わるのは0バイトです。追加のスタック領域は使われません。 このバージョンは、スタックをオーバーフローさせることなく、どれだけ大きなnでも扱えます。 より効率的で、より安全です。

場合によっては、関数の順序を工夫することで、ヘルパーへのjmpさえも避けられます。 たとえば、factorialとtriple_of_squareは次のように書き直せます。

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

上のコードでは、factorialの実行はそのままfactorial_helperに流れ込みます。 triple_of_squareとtimes_threeでも同じことが起こります。 どちらの場合も、実行はそのまま順に続き、末尾の関数は「メイン」の関数の中にある単なるローカルラベルにすぎないように見えます。

実際には、ローカルラベルと関数の間に本質的な違いはありません。 x86-64アセンブリは、それらのどれも特別扱いしません。それらは、section .textのような実行可能なコードを含むセクション内の単なるアドレスです。

このように、末尾再帰関数は、再帰呼び出しが先頭に戻るループと本質的に同じものと考えることができ、ベースケースはそのループを終わらせる条件にあたります。