YouTipAssembly Language - Recursion
Recursion is a technique where a function calls itself. Implementing recursion in assembly requires proper management of stack frames, with each call having independent copies of parameters and local variables.
Recursion Principles and Stack Frames
The core of recursion lies in creating a new stack frame with each call, saving the current state onto the stack.
Each recursive call pushes parameters, return address, and local variables onto the stack. When recursion terminates, stack frames are popped layer by layer, with each layer obtaining its child call's result and completing the calculation.
| Recursion Element | Description | Assembly Implementation |
|---|---|---|
| Termination Condition | Prevents infinite recursion | Conditional jump + je/jg |
| Recursive Call | Function calls itself | call instruction |
| State Preservation | Independent state per call | Stack frame (push ebp; mov ebp, esp) |
| Parameter Passing | Different parameters each time | push parameters onto stack |
While recursion produces elegant code, each call in assembly incurs significant stack overhead. Excessive recursion depth may cause stack overflow. For performance-sensitive scenarios, consider rewriting recursion as iteration.
Factorial Recursion Implementation
Example
; File path: factorial.asm
; Recursively calculate factorial: n! = n * (n-1)!
section .data
n dd 5 ; Calculate 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:
; Call factorial(5)
push dword ; Push parameter n
call factorial
add esp, 4 ; Clean up parameter
; eax = 120 (5!)
mov , eax
; Output result
mov eax, 4
mov ebx, 1
mov ecx, output_msg
mov edx, output_len
int 0x80
; Simple number output (demo for single digit only)
mov eax,
; Simplified handling here
mov ebx, eax
mov eax, 1
int 0x80
; Procedure: factorial(n)
; Input: [ebp+8] = n
; Output: eax = n!
factorial:
push ebp ; Save old stack frame
mov ebp, esp ; Establish new stack frame
mov eax, [ebp+8] ; Get parameter n
cmp eax, 1 ; n <= 1 ?
jg recurse ; n > 1, continue recursion
; Termination condition: n <= 1, return 1
mov eax, 1
jmp factorial_end
recurse:
; Save current n value (register will be clobbered by recursive call)
push eax ; Save n
; Recursive call factorial(n-1)
dec eax ; n - 1
push eax ; Parameter: n-1
call factorial ; Recursive call
add esp, 4 ; Clean up parameter
; Restore n
pop ebx ; ebx = n
; eax = n * factorial(n-1)
mul ebx ; edx:eax = eax * ebx
; For small n, edx is 0, result entirely in eax
factorial_end:
pop ebp ; Restore old stack frame
ret
The complete call stack and return process for calculating factorial(5):
Text version of the call process below:
factorial(5) -> 5 * factorial(4) -> 4 * factorial(3) -> 3 * factorial(2) -> 2 * factorial(1) -> 1 (termination condition) <- 1 * 2 = 2 <- 2 * 3 = 6 <- 6 * 4 = 24 <- 24 * 5 = 120
Fibonacci Recursion Implementation
Example
; File path: fibonacci.asm
; Recursively calculate Fibonacci sequence: fib(n) = fib(n-1) + fib(n-2)
section .data
n dd 10 ; Calculate fib(10)
section .text
global _start
_start:
; Call fib(10)
push dword
call fibonacci
add esp, 4
; eax = fib(10) = 55
mov ebx, eax ; Exit code = 55
mov eax, 1
int 0x80
; Procedure: fibonacci(n)
; Input: [ebp+8] = n
; Output: eax = fib(n)
fibonacci:
push ebp
mov ebp, esp
mov eax, [ebp+8] ; Get parameter n
; Termination condition: n <= 1 return n
cmp eax, 1
jg fib_recurse ; n > 1, need recursion
; n <= 1: fib(0)=0, fib(1)=1
jmp fib_end
fib_recurse:
; ★ Note: Recursion has two branches, need careful stack management
push ebx ; Save ebx (will be used to store intermediate result)
; Calculate 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) (save result!)
; Calculate 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 ; Restore ebx
fib_end:
pop ebp
ret
The recursive version of Fibonacci contains massive redundant computation. fib(10) calls fib(9), fib(8), fib(8) is called twice... resulting in O(2^n) time complexity. In practice, the iterative version is recommended.
Fibonacci Iterative Version (Comparison)
Example
; File path: fibonacci_iter.asm
; Iterative version: more efficient, no recursion overhead
section .data
n dd 10
section .text
global _start
_start:
mov ecx, ; ecx = n
dec ecx ; Loop n-1 times (starting from 2nd term)
mov eax, 0 ; fib(0) = 0
mov ebx, 1 ; fib(1) = 1
cmp ecx, 0
jle fib_done ; n <= 1, return directly
fib_loop:
mov edx, ebx ; Save old fib(n-1)
add ebx, eax ; ebx = fib(n-1) + fib(n-2)
mov eax, edx ; Update fib(n-2)
loop fib_loop
fib_done:
; For n=10, finally ebx = 55
mov eax, 1
mov ebx, ebx ; Return value = fib(n)
int 0x80
Recursion vs Iteration Comparison
| Characteristic | Recursion | Iteration |
|---|---|---|
| Code Size | Shorter, clear logic | Longer, but better performance |
| Stack Usage | One stack frame per call, may overflow at great depth | Fixed small space |
| Performance | Has call/ret overhead | No function call overhead |
| Readability | Intuitive for mathematical induction problems | Requires manual loop state maintenance |
| Applicable Scenarios | Tree traversal, divide-and-conquer algorithms, mathematical induction | Simple repetition, performance-sensitive scenarios |
Each recursive call in assembly consumes stack space. Linux default stack size is about 8MB, and recursion depth of 100000 may cause stack overflow. Determine when to use recursion: when recursion depth is controllable (e.g., balanced tree depth O(log n)), and recursive logic is much clearer than iterative.