# Recursion: factorial and Fibonacci

[Courses](https://asm-editor.specy.app/learn/courses.md) › [x86-64 assembly](https://asm-editor.specy.app/learn/courses/x86.md) › Examples

Web page: https://asm-editor.specy.app/learn/courses/x86/examples/factorial-and-fibonacci

> Recursive factorial and Fibonacci subroutines, with stack space and saved registers to keep values across calls.

The same program in: [M68K](https://asm-editor.specy.app/learn/courses/m68k/examples/factorial-and-fibonacci.md), [MIPS](https://asm-editor.specy.app/learn/courses/mips/examples/factorial-and-fibonacci.md), [RISC-V](https://asm-editor.specy.app/learn/courses/risc-v/examples/factorial-and-fibonacci.md), [Z80](https://asm-editor.specy.app/learn/courses/z80/examples/factorial-and-fibonacci.md)

The factorial and Fibonacci subroutines both use recursion: they call themselves. `fact(n)` calls
`fact(n - 1)`, then multiplies the result by `n`. These calls form a chain. `fib(n)` needs both
`fib(n - 1)` and `fib(n - 2)`, so each call that has not reached a base case splits into two branches.

```x86
default rel
global _start

section .bss
fact_out:   resq 1
fib_out:    resq 1

section .text
; fact(n) -> n!, for n >= 0
fact:
    cmp rdi, 1
    jg .recurse
    mov rax, 1              ; 0! and 1! are 1
    ret
.recurse:
    push rdi                ; save this call's n; rsp is now aligned
    dec rdi
    call fact               ; rax = fact(n - 1)
    pop rdi                 ; recover this call's n
    imul rax, rdi           ; n * fact(n - 1)
    ret

; fib(n) -> the nth Fibonacci number, for n >= 0
fib:
    cmp rdi, 2
    jge .recurse
    mov rax, rdi            ; fib(0) = 0 and fib(1) = 1
    ret
.recurse:
    push rbx                ; preserve the caller's rbx; rsp is now aligned
    sub rsp, 16             ; local space; rsp stays aligned
    mov [rsp], rdi          ; save this call's n in its local space

    dec rdi
    call fib                ; rax = fib(n - 1)
    mov rbx, rax            ; keep the first answer across the second call

    mov rdi, [rsp]          ; reload this call's n
    sub rdi, 2
    call fib                ; rax = fib(n - 2)
    add rax, rbx            ; combine the two answers

    add rsp, 16             ; release local space
    pop rbx                 ; return the caller's rbx unchanged
    ret

_start:
    mov rdi, 10
    call fact
    mov [fact_out], rax

    mov rdi, 10
    call fib
    mov [fib_out], rax

    mov rax, 60
    xor rdi, rdi
    syscall
```

Run it and type `402000` into the memory panel. `fact_out` holds `0x375F00` (3628800), and the
next qword, `fib_out`, holds `0x37` (55). The bytes of each qword appear in little-endian order.

## A saved value for each call

In `fact(3)`, the first call saves 3, calls `fact(2)`, and waits. That call saves 2 and calls
`fact(1)`. The base case returns 1. The waiting calls then recover their own values: `2 × 1 = 2`,
followed by `3 × 2 = 6`. Every recursive `call` starts another invocation of the same instructions.
Each invocation pushes at its current stack position, so its saved `n` stays separate from the
values saved by deeper calls.

`rdi` is caller-saved. A call may change it, so `fact` saves its `n` before calling and restores it
before multiplying. On entry, dividing `rsp` by 16 leaves a remainder of 8. The `push` subtracts 8 from `rsp`,
making it divisible by 16 as required immediately before `call`.

## Following both branches of `fib(3)`

`fib` needs its original `n` to set up the second call. It keeps that `n` in `[rsp]`, a local qword
belonging to this invocation. It keeps the first answer in `rbx` while the second call runs.
Because `rbx` is callee-saved, each invocation of `fib` saves the `rbx` it inherited and restores
it before returning. The next invocation of `fib` makes the same promise to this one.

Here is the outer `fib(3)` invocation. The stack column shows **its own** saved values. Deeper
calls temporarily put their stack frames below them. `B` stands for the `rbx` value inherited from its
caller.

| Moment in `fib(3)`           |                `rdi` | `rbx` | This invocation's stack                           | `rax` |
| ---------------------------- | -------------------: | ----: | ------------------------------------------------- | ----: |
| Before the first `call fib`  |                    2 |   `B` | local `n = 3`, padding, saved `B`, return address |     — |
| After `fib(2)` returns       | changed by that call |   `B` | same values                                       |     1 |
| Before the second `call fib` |                    1 |     1 | same values                                       |     1 |
| After `fib(1)` returns       |                    1 |     1 | same values                                       |     1 |
| After `add rax, rbx`         |                    1 |     1 | same values                                       |     2 |

The first child computes `fib(2) = fib(1) + fib(0) = 1`. Back in `fib(3)`, `mov rbx, rax` saves
that answer. `mov rdi, [rsp]` recovers 3 from this invocation's local space, then subtracts 2 to
call `fib(1)`. The second answer arrives in `rax`, while the first is still in `rbx`. After adding
them, this invocation releases its local space, restores `B`, and returns 2.

The stack arithmetic matters for both nested calls. On entry, dividing `rsp` by 16 leaves a
remainder of 8. `push rbx` makes it divisible by 16. Reserving 16 more bytes keeps it that way. Only eight of those local
bytes hold `n`; the other eight are padding. Both calls therefore meet the System V alignment rule.

## Try it

First, change the Fibonacci input in `_start` from 10 to 5. Before running, work out
`fib(5) = fib(4) + fib(3)` from the base cases. Check that `fib_out` becomes `0x5` in memory.
In the call tree, `fib(3)` is computed twice: once inside `fib(4)` and once directly from `fib(5)`.
That repeated work explains why this recursive version makes many more calls as `n` grows.

Next, write a third subroutine, `sum_to(n)`, which returns `1 + 2 + ... + n` for `n >= 0`.
Make `sum_to(0)` return 0. For a positive `n`, save `n`, call `sum_to(n - 1)`, then add the saved
`n` to the returned `rax`. Use the same `rdi` argument and `rax` result convention as `fact`,
and keep `rsp` aligned before the recursive call. Add `sum_out: resq 1` after `fib_out`, call
`sum_to` with 5 in `_start`, and store its result in `sum_out` before the exit syscall. The new
qword at `0x402010` should contain `0xF` (15). Try input 0 as a second check: it should store 0.

## Instructions in this Lecture

- x86-64: [`cmp`](https://asm-editor.specy.app/documentation/x86/instruction/cmp.md), [`jg`](https://asm-editor.specy.app/documentation/x86/instruction/jg.md), [`mov`](https://asm-editor.specy.app/documentation/x86/instruction/mov.md), [`ret`](https://asm-editor.specy.app/documentation/x86/instruction/ret.md), [`push`](https://asm-editor.specy.app/documentation/x86/instruction/push.md), [`dec`](https://asm-editor.specy.app/documentation/x86/instruction/dec.md), [`call`](https://asm-editor.specy.app/documentation/x86/instruction/call.md), [`pop`](https://asm-editor.specy.app/documentation/x86/instruction/pop.md), [`imul`](https://asm-editor.specy.app/documentation/x86/instruction/imul.md), [`jge`](https://asm-editor.specy.app/documentation/x86/instruction/jge.md), [`sub`](https://asm-editor.specy.app/documentation/x86/instruction/sub.md), [`add`](https://asm-editor.specy.app/documentation/x86/instruction/add.md), [`xor`](https://asm-editor.specy.app/documentation/x86/instruction/xor.md), [`syscall`](https://asm-editor.specy.app/documentation/x86/instruction/syscall.md)

Previous: [Stack arguments and a stack frame](https://asm-editor.specy.app/learn/courses/x86/examples/subroutine-with-stack-arguments.md)

Next: [Bubble sort](https://asm-editor.specy.app/learn/courses/x86/examples/bubble-sort.md)
