# Recursion: factorial and Fibonacci

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

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

> Trace factorial and Fibonacci calls as saved values and return addresses move on the stack, then see where a 16-bit result overflows.

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), [x86-64](https://asm-editor.specy.app/learn/courses/x86/examples/factorial-and-fibonacci.md)

What happens when a subroutine calls itself? Each `call` puts a return address on the stack. If the
subroutine also saves the values it will need later, one call can wait while the next call works.
These two routines use that pattern to calculate `factorial(8)` and `fib(10)`.

Open the program in the editor and choose **Build**. Use **Step** to follow the smaller calls, or
**Run** to see the answers. The register panel shows hexadecimal values; `8` and `10` in the code
are decimal.

```z80
    .org 0x8000
    ld a, 8
    call factorial      ; 8!, returned in hl
    push hl
    pop ix              ; keep 8! while fib uses hl
    ld a, 10
    call fib            ; fib(10), returned in hl
    jp done

; factorial(n): n in a, answer in hl
factorial:
    cp 2
    jr nc, more
    ld hl, 1            ; factorial(0) and factorial(1) are 1
    ret
more:
    push af             ; save this call's n
    dec a
    call factorial      ; hl = factorial(n - 1)
    pop af              ; recover this call's n
    ld b, a
    ld d, h
    ld e, l             ; de = factorial(n - 1)
    ld hl, 0
times:
    add hl, de          ; add the smaller factorial n times
    djnz times
    ret

; fib(n): n in a, answer in hl
fib:
    cp 2
    jr nc, recurse
    ld l, a
    ld h, 0             ; fib(0) is 0 and fib(1) is 1
    ret
recurse:
    push af             ; save this call's n
    dec a
    call fib            ; hl = fib(n - 1)
    pop af              ; restore n before calculating n - 2
    push hl             ; keep the first answer across the next call
    sub 2
    call fib            ; hl = fib(n - 2)
    pop de              ; de = fib(n - 1)
    add hl, de          ; fib(n - 2) + fib(n - 1)
    ret

done:
    halt
```

### Factorial: one call waits for another

`factorial(0)` and `factorial(1)` return 1 directly. For any larger `n`, the routine saves `n`,
calls `factorial(n - 1)`, and multiplies that answer by `n`. There is no multiply instruction here,
so it adds the smaller factorial to `hl` exactly `n` times.

For `factorial(3)`, the calls go down through `3 → 2 → 1`. The call for 1 returns `hl = 1`.
The waiting call for 2 restores its own `n = 2`, adds 1 twice, and returns `hl = 2`. The waiting
call for 3 restores `n = 3`, adds 2 three times, and returns `hl = 6`. As `factorial(8)` returns,
the calls for 2 through 8 each do their own additions: 2 + 3 + 4 + 5 + 6 + 7 + 8 in all.

`push af` saves the current `a` along with the flags. Z80 `push` and `pop` work with 16-bit pairs,
so `push a` is not an instruction. When the smaller call returns, `pop af` restores the saved `n`
without changing its answer in `hl`. Each deeper `call` and `push` moves `sp` farther down, below
the waiting call's saved value. Its matching `pop` and `ret` move `sp` back up, so the waiting call
gets its own value and return address.

### Fibonacci: keep the first answer for the second call

`fib(0)` returns 0 and `fib(1)` returns 1. For larger `n`, the routine needs both `fib(n - 1)`
and `fib(n - 2)`. Both return their answers in `hl`, so the first answer must be saved before the
second call changes `hl`. That is the job of `push hl` and `pop de`.

Follow `fib(3)` through the recursive part. The values in this trace are decimal; the register
panel shows their hexadecimal equivalents.

| In the waiting `fib(3)` call   | `a`, `hl`, and saved values                                                     |
| ------------------------------ | ------------------------------------------------------------------------------- |
| `push af`; `dec a`; `call fib` | Save original `n = 3`; call `fib(2)`.                                           |
| `fib(2)` returns               | It called `fib(1)` and `fib(0)`, added 1 + 0, and returned `hl = 1`.            |
| `pop af`; `push hl`            | Restore original `a = 3`; save the first answer, 1, on the stack.               |
| `sub 2`; `call fib`            | Subtract from the restored 3, so this call is `fib(1)`. It returns `hl = 1`.    |
| `pop de`; `add hl, de`         | Take the saved first answer into `de = 1`; add it to `hl = 1`. Return `hl = 2`. |

The second call gets its own return address below the saved first answer. When it returns, `sp`
points at that answer again, ready for `pop de`. In the full program, `ix` keeps `factorial(8)`
while Fibonacci uses `hl`. After **Run**, `ix = 9D80` (40320) and `hl = 0037` (55).

Try changing `ld a, 8` to `ld a, 9`, then build and run again. Predict whether `ix` can hold the
whole answer before looking at the panel.

<details>
<summary>Check your answer</summary>

`9!` is 362880, but `ix` shows `8980` (35200). A 16-bit pair holds values from 0 to 65535;
these additions wrap past that limit and keep only the low 16 bits. The routine does not report
the overflow.

</details>

## Instructions in this Lecture

- Z80: [`ld`](https://asm-editor.specy.app/documentation/z80/instruction/ld.md), [`call`](https://asm-editor.specy.app/documentation/z80/instruction/call.md), [`push`](https://asm-editor.specy.app/documentation/z80/instruction/push.md), [`pop`](https://asm-editor.specy.app/documentation/z80/instruction/pop.md), [`jp`](https://asm-editor.specy.app/documentation/z80/instruction/jp.md), [`cp`](https://asm-editor.specy.app/documentation/z80/instruction/cp.md), [`jr`](https://asm-editor.specy.app/documentation/z80/instruction/jr.md), [`ret`](https://asm-editor.specy.app/documentation/z80/instruction/ret.md), [`dec`](https://asm-editor.specy.app/documentation/z80/instruction/dec.md), [`add`](https://asm-editor.specy.app/documentation/z80/instruction/add.md), [`djnz`](https://asm-editor.specy.app/documentation/z80/instruction/djnz.md), [`sub`](https://asm-editor.specy.app/documentation/z80/instruction/sub.md), [`halt`](https://asm-editor.specy.app/documentation/z80/instruction/halt.md)

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

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