アセンブリ言語 - 再帰
再帰(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
; 递归计算阶乘: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)
-> 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(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
; 迭代版本:更高效,无递归开销
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))、かつ再帰ロジックが反復よりはるかに明確な場合。