Recursion Is Just Repeated CALLs
A recursive function in assembly is a procedure that includes a CALL instruction targeting its own label. Each invocation pushes a new return address and establishes its own stack frame via the standard prologue, so recursive calls naturally stack on top of each other without special-casing — the CPU treats a self-referential CALL exactly like a call to any other procedure. What makes recursion work correctly is that each stack frame has its own copy of local variables and its own saved EBP, so a deeper recursive call cannot accidentally overwrite the caller's locals as long as the prologue/epilogue convention is followed consistently at every level.
Cricket analogy: Recursion is like a team sending in a night-watchman who, facing another tricky over, calls for yet another night-watchman below them in the order — each batsman gets their own innings record (stack frame) that doesn't overwrite the one before, exactly like nested CALL frames.
Base Cases and Runaway Stack Growth
Every recursive procedure needs a base case check near the top of the function — a conditional jump that returns immediately without recursing further once a terminating condition is met. Without it, or if the base case condition is subtly wrong, the function calls itself indefinitely, pushing a new stack frame on every invocation until the stack pointer runs past the bottom of the memory region the OS allocated for the stack, triggering a stack overflow — typically delivered as a segmentation fault when the next PUSH or CALL touches an unmapped guard page just past the stack's limit.
Cricket analogy: The base case is like the boundary rope rule that stops a fielder's chase for the ball — without a clearly defined stopping point, a fielder would keep running indefinitely, just as a missing or wrong base case lets recursive calls pile up without ever unwinding.
; unsigned int factorial(unsigned int n) using cdecl
section .text
global factorial
factorial:
push ebp
mov ebp, esp
mov eax, [ebp+8] ; n
cmp eax, 1
jbe base_case ; if n <= 1, return 1 (base case)
dec eax
push eax ; argument: n - 1
call factorial ; recursive call
add esp, 4 ; caller cleans up (cdecl)
imul eax, [ebp+8] ; eax = factorial(n-1) * n
jmp done
base_case:
mov eax, 1
done:
pop ebp
retDeep recursion in assembly is far more dangerous than in a high-level language with tail-call optimization, because raw CALL/RET recursion always allocates a new stack frame regardless of whether the recursive call is in tail position — there is no automatic conversion to a loop unless you write that transformation by hand.
Register Preservation Across Recursive Calls
Because a recursive call re-enters the same code, any register the function relies on after the recursive CALL returns must either be restored by the callee (if it's a callee-saved register per the calling convention) or explicitly saved by the caller before the call and restored afterward. This is a common source of bugs specific to recursion: a value held in a caller-saved register like EAX or ECX before a recursive call is not guaranteed to survive that call, since the recursive invocation is free to clobber it just like any other function call would — the fact that it's the same function doesn't grant any special protection.
Cricket analogy: A caller-saved register value is like a bowler's over-count kept only in their head with no scoreboard backup — if they get distracted by an unrelated review during the over (a nested call), that mental count can get overwritten, exactly like EAX getting clobbered by a recursive call unless explicitly saved.
In the factorial example above, [ebp+8] is used to re-read the argument n after the recursive call returns, rather than relying on EAX or ECX to still hold it — this sidesteps the caller-saved register problem entirely by reading from the current frame's own stack slot instead of a register that the recursive call is free to overwrite.
- Recursive functions are ordinary procedures that CALL their own label; each call gets an independent stack frame.
- Every recursive function needs a base case with a conditional jump that stops further recursion.
- A missing or incorrect base case causes unbounded stack growth and an eventual stack overflow.
- Assembly-level CALL/RET recursion never automatically becomes a loop, unlike tail-call-optimized high-level languages.
- Caller-saved registers (like EAX, ECX) are not guaranteed to survive a recursive call and must be explicitly preserved if needed afterward.
- Reading a value back from its stack slot ([ebp+offset]) after a recursive call avoids relying on a register that may have been clobbered.
- Deep recursion is riskier in assembly than in languages with automatic tail-call optimization since every level always consumes stack space.
Practice what you learned
1. What fundamentally makes a recursive function different from any other procedure at the machine-code level?
2. What is the typical consequence of a missing or incorrect base case in a recursive assembly function?
3. Why is it unsafe to assume EAX still holds its pre-call value immediately after a recursive CALL returns?
4. Does raw x86 assembly automatically convert tail-recursive calls into a loop the way some optimizing compilers might?
5. In the example factorial procedure, why is [ebp+8] re-read after the recursive call instead of relying on a register?
Was this page helpful?
You May Also Like
Procedures and Calling Conventions
Learn how assembly functions are called, how arguments and return values are passed, and how the stack frame is built and torn down.
Loops in Assembly
Discover how high-level for and while loops are built from conditional jumps, counters, and the dedicated LOOP instruction in x86 assembly.
The Flags Register
Understand the x86 FLAGS register — the bit fields like ZF, CF, SF, and OF that record the outcome of arithmetic and comparison instructions.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics