Recursive factorial

Code

; fact(n) -> n!   rdi = n, result in rax
section .text
global fact

fact:
    ; prologue
    push    rbp
    mov     rbp, rsp
    push    rbx              ; save callee-saved rbx (we use it for n)

    mov     rbx, rdi         ; rbx = n
    cmp     rbx, 1
    jle     .base            ; if n <= 1, return 1

    ; recursive case:  n * fact(n-1)
    lea     rdi, [rbx - 1]   ; arg = n-1
    call    fact             ; rax = fact(n-1)
    imul    rax, rbx         ; rax = n * fact(n-1)
    jmp     .epi

.base:
    mov     rax, 1

.epi:
    pop     rbx              ; restore rbx
    pop     rbp              ; restore rbp (epilogue)
    ret

; Tail-recursive form compiled to a loop (no stack growth)
global fact_iter
fact_iter:
    mov     rax, 1           ; accumulator
.loop:
    test    rdi, rdi
    jle     .done
    imul    rax, rdi
    dec     rdi
    jmp     .loop
.done:
    ret

Explanation

Each recursive call sets up a full stack frame: push rbp; mov rbp,rsp (frame pointer); push rbx (callee-saved, used to hold n across the recursive call). The base case returns 1; otherwise we recurse with n-1 and multiply the result. The iterative version uses tail-recursion-style accumulation and never grows the stack — preferable for deep recursion. imul is the two-operand signed multiply.

More Assembly Snippets