アセンブリ言語 - 再帰

再帰(Recursion)は関数が自身を呼び出す技術です。アセンブリで再帰を実装するにはスタックフレームを適切に管理する必要があり、各呼び出しには独立した引数とローカル変数のコピーがあります。


再帰の原理とスタックフレーム

再帰の核心は呼び出しのたびに新しいスタックフレームを作成、現在の状態をスタックに保存する。

再帰呼び出しのたびに、引数、戻り先アドレス、ローカル変数がスタックにプッシュされる。再帰が終了すると、スタックフレームが階層ごとにポップされ、各階層は子呼び出しの結果を受け取り、計算を完了する。

递归要素说明汇编实现
终止条件無限再帰の防止条件分岐 + je/jg ジャンプ
递归调用関数が自身を呼び出すcall 指令
状态保存各呼び出しは独立した状態栈帧(push ebp; mov ebp, esp)
参数传递毎回異なる引数引数をスタックにpush

再帰はコードがエレガントですが、アセンブリでは各呼び出しに少なくないスタックオーバーヘッドがあります。再帰の深さが大きすぎるとスタックオーバーフロー(Stack Overflow)を引き起こす可能性があります。パフォーマンスに敏感な場面では、再帰をループに書き換えることを検討してください。


階乗の再帰実装

实例

; 文件路径:factorial.asm
; 递归计算阶乘:n! = n * (n-1)!

section .data
    n dd 5                       ; 计算 5!
    result dd 0
    output_msg db 'Factorial result: '
    output_len equ $ - output_msg
    newline db 0xA

section .bss
    result_str resb 12

section .text
    global _start

_start:
    ; 调用 factorial(5)
    push dword [n]               ; 压入参数 n
    call factorial
    add esp, 4                   ; 清理参数
    ; eax = 120 (5!)

    mov [result], eax

    ; 输出结果
    mov eax, 4
    mov ebx, 1
    mov ecx, output_msg
    mov edx, output_len
    int 0x80

    ; 简单输出数字(仅用于个位数演示)
    mov eax, [result]
    ; ここでは簡略化処理
    mov ebx, eax
    mov eax, 1
    int 0x80

; 过程:factorial(n)
; 输入:[ebp+8] = n
; 输出:eax = n!
factorial:
    push ebp                     ; 保存旧栈帧
    mov ebp, esp                 ; 建立新栈帧

    mov eax, [ebp + 8]           ; 获取参数 n
    cmp eax, 1                   ; n <= 1 ?
    jg  recurse                  ; n > 1,继续递归

    ; 终止条件:n <= 1,返回 1
    mov eax, 1
    jmp factorial_end

recurse:
    ; 現在の n の値を保存(レジスタは再帰呼び出しによって破壊される)
    push eax                     ; 保存 n

    ; 递归调用 factorial(n-1)
    dec eax                      ; n - 1
    push eax                     ; 参数:n-1
    call factorial               ; 递归调用
    add esp, 4                   ; 清理参数

    ; 恢复 n
    pop ebx                      ; ebx = n

    ; eax = n * factorial(n-1)
    mul ebx                      ; edx:eax = eax * ebx
    ; 小さい n の場合、edx は 0 で、結果はすべて eax にあります。

factorial_end:
    pop ebp                      ; 恢复旧栈帧
    ret

再帰による factorial(5) の完全な呼び出しスタックと戻りのプロセス:

递归调用栈 - factorial(5)

以下はテキスト版の呼び出しプロセスである:

factorial(5)
  -> 5 * factorial(4)
       -> 4 * factorial(3)
            -> 3 * factorial(2)
                 -> 2 * factorial(1)
                      -> 1  (终止条件)
                 <- 1 * 2 = 2
            <- 2 * 3 = 6
       <- 6 * 4 = 24
  <- 24 * 5 = 120

フィボナッチの再帰実装

实例

; 文件路径:fibonacci.asm
; 再帰のにフィボナッチ数列を計算: fib(n) = fib(n-1) + fib(n-2)

section .data
    n dd 10                      ; 计算 fib(10)

section .text
    global _start

_start:
    ; 调用 fib(10)
    push dword [n]
    call fibonacci
    add esp, 4
    ; eax = fib(10) = 55

    mov ebx, eax                 ; 退出码 = 55
    mov eax, 1
    int 0x80

; 过程:fibonacci(n)
; 输入:[ebp+8] = n
; 输出:eax = fib(n)
fibonacci:
    push ebp
    mov ebp, esp

    mov eax, [ebp + 8]           ; 获取参数 n

    ; 终止条件:n <= 1 返回 n
    cmp eax, 1
    jg  fib_recurse              ; n > 1,需要递归
    ; n <= 1:fib(0)=0, fib(1)=1
    jmp fib_end

fib_recurse:
    ; ★ 注意:递归有两个分支,需要仔细管理栈
    push ebx                     ; ebx を保存する(中間結果の保存に使用される)

    ; 计算 fib(n-1)
    mov eax, [ebp + 8]
    dec eax                      ; n - 1
    push eax
    call fibonacci
    add esp, 4
    mov ebx, eax                 ; ebx = fib(n-1)(保存结果!)

    ; 计算 fib(n-2)
    mov eax, [ebp + 8]
    sub eax, 2                   ; n - 2
    push eax
    call fibonacci
    add esp, 4
    ; eax = fib(n-2)

    ; eax = fib(n-1) + fib(n-2)
    add eax, ebx                 ; eax = fib(n-2) + fib(n-1)

    pop ebx                      ; 恢复 ebx

fib_end:
    pop ebp
    ret

再帰版のフィボナッチには大量の重複計算があります。fib(10) は fib(9)、fib(8) を呼び出し、fib(8) は2回呼び出されます...そのため時間計算量は O(2^n) になります。実際のエンジニアリングではループ反復版を使用することをお勧めします。


フィボナッチ反復版(比較)

实例

; 文件路径:fibonacci_iter.asm
; 迭代版本:更高效,无递归开销

section .data
    n dd 10

section .text
    global _start

_start:
    mov ecx, [n]                 ; ecx = n
    dec ecx                      ; n-1 回ループする(第2項から開始)

    mov eax, 0                   ; fib(0) = 0
    mov ebx, 1                   ; fib(1) = 1

    cmp ecx, 0
    jle fib_done                 ; n <= 1,直接返回

fib_loop:
    mov edx, ebx                 ; 古い fib(n-1) を保存
    add ebx, eax                 ; ebx = fib(n-1) + fib(n-2)
    mov eax, edx                 ; 更新 fib(n-2)
    loop fib_loop

fib_done:
    ; n=10 の場合、最終のに ebx = 55
    mov eax, 1
    mov ebx, ebx                 ; 返回值 = fib(n)
    int 0x80

再帰と反復の比較

特性递归迭代
代码量より短く、ロジックが明確より長いが、性能が良い
栈使用各呼び出しが1つのスタックフレームを占有し、深さが大きいとオーバーフローする可能性があります少量の固定スペース
性能call/ret のオーバーヘッドがある関数呼び出しのオーバーヘッドなし
可读性数学的帰納法の問題に直感的ループ状態を手動で維持する必要がある
适用场景木の走査、分割統治法、数学的帰納法単純な繰り返し、パフォーマンスが重要な場面

アセンブリでは再帰呼び出しのたびにスタック領域を消費します。Linux のデフォルトのスタックサイズは約8MBで、深さ100000の再帰ではスタックオーバーフローする可能性があります。再帰を使うタイミングの判断:問題の再帰深さが制御可能であり(例:平衡木の深さ O(log n))、かつ再帰ロジックが反復よりはるかに明確な場合。

其他扩展