Assembly Language - Recursion

Recursion is a technique in which a function calls itself. Implementing recursion in assembly requires proper stack frame management, with each call having independent copies of parameters and local variables.

Recursion principles and stack frames

The core of recursion lies ineach call creating a new stack frame, saving the current state on the stack.

Each recursive call pushes parameters, the return address, and local variables onto the stack. When the recursion terminates, stack frames are popped layer by layer, and each layer receives the result of its subcall and completes its calculation.

Recursion essentials	Description	Assembly implementation
Termination condition	Prevent infinite recursion	Conditional check + je/jg jump
Recursive call	Function calls itself	call instruction
State saving	Independent state for each call	Stack frame (push ebp; mov ebp, esp)
Parameter passing	Different parameters each time	push parameters onto the stack

Although recursion makes code elegant, each call in assembly has considerable stack overhead. Excessive recursion depth may cause stack overflow. For performance-sensitive scenarios, consider rewriting recursion as a loop.

Recursive factorial implementation

Example

; File path: factorial.asm
; Recursively compute factorial: n! = n * (n-1)!

section .data
n dd 5 ; Compute 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 [n] ; Push parameter n
call factorial
add esp, 4 ; Clean up parameters
; eax = 120 (5!)

mov [result], eax

; Output result
mov eax, 4
mov ebx, 1
mov ecx, output_msg
mov edx, output_len
int 0x80

; Simple numeric output (for single-digit demo only)
mov eax, [result]
; Simplified 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 ; Set up 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 (the register will be destroyed by the recursive call)
push eax ; Save n

; Recursively call factorial(n-1)
dec eax ; n - 1
push eax ; Argument: n-1
call factorial ; Recursive call
add esp, 4 ; Clean up parameters

; Restore n
pop ebx ; ebx = n

; eax = n * factorial(n-1)
mul ebx ; edx:eax = eax * ebx
; For smaller n, edx is 0, and the result is entirely in eax

factorial_end:
pop ebp ; Restore old stack frame
ret

The complete call stack and return process for recursively computing factorial(5):

The following is the textual call process:

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

Recursive Fibonacci implementation

Example

; File path: fibonacci.asm
; Recursively compute the Fibonacci sequence: fib(n) = fib(n-1) + fib(n-2)

section .data
n dd 10 ; Compute fib(10)

section .text
global _start

_start:
; Call fib(10)
push dword [n]
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: return n when n <= 1
cmp eax, 1
jg fib_recurse ; n > 1, recursion needed
; n <= 1：fib(0)=0, fib(1)=1
jmp fib_end

fib_recurse:
; ★ Note: recursion has two branches, so the stack must be managed carefully
push ebx ; Save ebx (it will be used to store the intermediate result)

; Compute 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 the result!)

; Compute 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 involves a lot of duplicate calculations. fib(10) calls fib(9) and fib(8), and fib(8) is called twice... resulting in a time complexity of O(2^n). In actual engineering, it is recommended to use the loop iterative version.

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, [n] ; ecx = n
dec ecx ; Loop n-1 times (starting from the 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 the 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

Feature	Recursion	Iteration
Code size	Shorter, clear logic	Longer, but good performance
Stack usage	Each call occupies a stack frame; may overflow when depth is large	Fixed small amount of space
Performance	Has call/ret overhead	No function call overhead
Readability	Intuitive for mathematical induction problems	Need to manually maintain loop state
Applicable scenarios	Tree traversal, divide and conquer algorithms, mathematical induction	Simple repetition, performance-sensitive scenarios

In assembly, every recursive call consumes stack space. The default stack size on Linux is about 8MB, and recursion with a depth of 100000 may cause stack overflow. Judging when to use recursion: when the recursion depth of the problem is controllable (such as balanced tree depth O(log n)), and the recursive logic is much clearer than iteration.

Other extensions