Advanced

Recursion

Implementing recursive functions in LC-3 assembly.

Recursion in Assembly

Recursion works in assembly just like in high-level languages — a function calls itself with a smaller problem. The stack is essential because each call needs its own copies of local variables and the return address.

Factorial Example

Let's implement factorial(n):

  • Base case: if n <= 1, return 1

  • Recursive case: return n * factorial(n-1)

    • The key insight: before the recursive call, we must save n and R7 on the stack.

    .ORIG x3000
LD R6, STACK      ; Initialize stack

AND R0, R0, #0
ADD R0, R0, #5    ; Compute 5!

JSR FACTORIAL     ; R0 = factorial(5) = 120

HALT

;-----------------------------------
; FACTORIAL: R0 = factorial(R0)
; Input: R0 = n
; Output: R0 = n!
;-----------------------------------
FACTORIAL
  ADD R6, R6, #-1
  STR R7, R6, #0    ; Save return address
  ADD R6, R6, #-1
  STR R1, R6, #0    ; Save R1

  ADD R1, R0, #0    ; R1 = n (save it)

  ADD R0, R0, #-1   ; n - 1
  BRp RECURSE       ; if n-1 > 0, recurse

  ; Base case: return 1
  AND R0, R0, #0
  ADD R0, R0, #1
  BR FACT_DONE

RECURSE
  ; R0 already = n-1
  JSR FACTORIAL     ; R0 = factorial(n-1)

  ; Now multiply: R0 = R1 * R0 (n * factorial(n-1))
  ; Simple multiply using a loop
  ADD R2, R0, #0    ; R2 = factorial(n-1)
  AND R0, R0, #0    ; R0 = 0 (accumulator)
  ADD R1, R1, #0    ; Check R1

  FMUL_LOOP
    ADD R1, R1, #0
    BRz FACT_DONE
    ADD R0, R0, R2
    ADD R1, R1, #-1
    BR FMUL_LOOP

FACT_DONE
  LDR R1, R6, #0    ; Restore R1
  ADD R6, R6, #1
  LDR R7, R6, #0    ; Restore return address
  ADD R6, R6, #1
  RET

STACK .FILL xFE00
.END

    Each recursive call pushes data onto the stack, and each return pops it off. For factorial(5), the stack grows 5 levels deep before unwinding.

    Quiz

    In a recursive subroutine, what MUST be saved on the stack before making the recursive call?

    ← Subroutines & the StackString Processing →