Recursive Functions

Recursion in Assembly

Recursive functions call themselves. Understanding recursion in assembly reveals exactly what the CPU does when high-level languages handle it automatically -- each recursive call creates a new stack frame, and the call stack unwinds as results are returned.

Like Q sending Picard into nested timelines within timelines, each recursive call drops you one level deeper -- and you must unwind every layer to get back to where you started.

The Core Problem

When a function calls itself with BL, the return address in X30 is overwritten. Without saving it, the function has no way to return to its original caller. Similarly, argument registers (X0-X7) are overwritten by the recursive call's arguments.

Stack Frame Per Call

Each recursive call pushes a "frame" onto the stack to save:

1. The link register (X30) -- so we can return
2. Any register values needed after the recursive call returns

Factorial Example

Here is factorial(n) = n! implemented recursively:

factorial:
    CMP X0, #1
    B.LE base_case         // if n <= 1, return 1

    STP X30, X0, [SP, #-16]!  // Save LR and n

    SUB X0, X0, #1         // Argument: n-1
    BL factorial            // Recursive call: result in X0

    LDP X30, X1, [SP], #16 // Restore LR and n (into X1)

    MUL X0, X0, X1         // Return n * factorial(n-1)
    RET

base_case:
    MOV X0, #1
    RET

Stack Walkthrough for factorial(5)

Call factorial(5): push (LR, 5)  → stack: [(LR,5)]
Call factorial(4): push (LR, 4)  → stack: [(LR,5), (LR,4)]
Call factorial(3): push (LR, 3)  → stack: [(LR,5), (LR,4), (LR,3)]
Call factorial(2): push (LR, 2)  → stack: [(LR,5), (LR,4), (LR,3), (LR,2)]
Call factorial(1): base case!    → return 1

Pop (LR, 2): return 2 * 1 = 2
Pop (LR, 3): return 3 * 2 = 6
Pop (LR, 4): return 4 * 6 = 24
Pop (LR, 5): return 5 * 24 = 120

Each frame is exactly 16 bytes (two 8-byte registers), so factorial(5) uses 64 bytes of stack at peak depth.

Common mistake: Forgetting to save X0 (the current n) before the recursive call. After BL factorial returns, X0 holds the result of the recursive call, not the original n. You need to have saved n somewhere (e.g., on the stack) to use it in the multiplication.

Your Task

Implement the factorial function above and call it with n=5. Print the result (120) followed by a newline.

Hint: 120 is three digits. You need to handle hundreds, tens, and ones digits.