This blog post will dive into a more advanced concept in 8086 assembly: computing the factorial of a number using recursion. Unlike iterative approaches using loops, recursion involves a procedure calling itself. This example highlights crucial concepts of stack management (PUSH and POP), procedure calls (CALL and RET), and conditional jumping to handle base cases. Let’s explore how the stack handles the “memory” of recursive calls!

; Program to calculate Factorial of a number using Recursion
; Input: num (e.g., 5)
; Output: result (e.g., 5! = 120 or 78h)

data segment
    num dw 0005h    ; The number to calculate factorial for (16-bit word)
    result dw ?     ; Variable to store the final 16-bit result
data ends

code segment
    assume cs:code, ds:data

start:
    mov ax, data
    mov ds, ax      ; Initialize Data Segment

    mov cx, num     ; Load the input number into CX register used as counter/argument
    mov ax, 0001h   ; Initialize accumulator AX to 1 (needed for multiplication)

    call factorial  ; Call the recursive procedure

    mov result, ax  ; Store final result from AX into memory variable
    int 3           ; Breakpoint to halt and check registers

;--- Recursive Procedure Definition ---
factorial proc near
    cmp cx, 1       ; BASE CASE: Check if number in CX is <= 1
    jbe base_case   ; If CX is 0 or 1, jump to base_case to return

    push cx         ; RECURSIVE STEP: Save current state of CX on STACK
    dec cx          ; Decrement CX to move towards base case (N-1)
    call factorial  ; Recursive Call: factorial(N-1)

    pop cx          ; UNWINDING: Restore the saved value of CX from STACK
    mul cx          ; AX = AX * CX. (Current Result * Current N)
    ret             ; Return to caller

base_case:
    mov ax, 1       ; Base case returns 1 (as 0! = 1 and 1! = 1)
    ret             ; Return to caller
factorial endp
;--------------------------------------

code ends
end start

Understanding the Code

The program relies heavily on the stack to manage the state of variables during recursive calls.

Data Segment:

• data segment: Defines data.
• num dw 0005h: Declares a 16-bit word variable num initialized to 5. We use words (dw) because factorials grow rapidly and exceed 8-bit capacity quickly (5! = 120, which fits in 8 bits, but 6! = 720, which requires 16 bits).
• result dw ?: Reserves a 16-bit word to hold the final calculated factorial.

Code Segment (Main Program):

• mov ax, data / mov ds, ax: Standard setup to point the DS register to the data segment.
• mov cx, num: Loads our input value (5) into the CX register. We use CX to pass the argument to the procedure.
• mov ax, 0001h: Initializes AX to 1. Since we will be using multiplication (MUL), starting with 1 ensures the first multiplication works correctly.
• call factorial: The program branches to the factorial procedure. The processor automatically pushes the return address onto the stack.
• mov result, ax: After recursion finishes, the final result resides in AX. We move it to memory.
• int 3: Halts execution for debugging.

The Recursive Procedure (factorial):

This is the heart of the program.

• The Base Case:
  • cmp cx, 1: Checks if the current number N is 1 or 0.
  • jbe base_case: If CX is ≤ 1, we jump to the base case. There, mov ax, 1 ensures we return 1, stopping the recursion.
• The Recursive Step & Stack Management:
  • push cx: Crucial step. Before calling the procedure again for (N-1), we must save the current value of N (in CX) onto the stack. If we don’t, we lose the current number we need to multiply later.
  • dec cx: We reduce N by 1.
  • call factorial: The procedure calls itself. This repeats the process until the base case (CX=1) is reached.
• The Unwinding Phase:
  • Once the base case returns, execution resumes after the call instruction.
  • pop cx: We retrieve the value we saved before the recursive call off the stack.
  • mul cx: We multiply the result returned from the deeper recursion level (currently in AX) by the current level’s number (restored into CX). AX = AX * CX.

Flowchart

High-Level Overview

1. Initialization: Load input N into CX, initialize result register AX to 1.
2. Initial Call: Start the recursive procedure.
3. Base Case Check: Inside the procedure, is N <= 1? If yes, return 1.
4. Save State (Push): If N > 1, push current N onto the stack.
5. Recurse: Decrement N and call the procedure again. Repeat steps 3-5 until base case is hit.
6. Restore and Calculate (Pop/Mul): As procedures return, pop the saved N off the stack and multiply it with the running total in AX.

Output

Here is a simulated session compiling and debugging the program to calculate 5!. We expect the result 120, which is 78h in hexadecimal.

C:\TASM>masm factrec.asm
Microsoft (R) Macro Assembler Version 5.00
Copyright (C) Microsoft Corp 1981-1985, 1987.  All rights reserved.

Object filename [factrec.OBJ]:
Source listing  [NUL.LST]:
Cross-reference [NUL.CRF]:

      50402 + 450254 Bytes symbol space free

      0 Warning Errors
      0 Severe  Errors

C:\TASM>link factrec.obj

Microsoft (R) Overlay Linker  Version 3.60
Copyright (C) Microsoft Corp 1983-1987.  All rights reserved.

Run File [FACTREC.EXE]:
List File [NUL.MAP]:
Libraries [.LIB]:
LINK : warning L4021: no stack segment

C:\TASM>debug factrec.exe
-g

AX=0078  BX=0000  CX=0001  DX=0000  SP=0000  BP=0000  SI=0000  DI=0000
DS=0B97  ES=0B87  SS=0B97  CS=0B98  IP=000F   NV UP EI PL NZ NA PO NC
0B98:000F CC            INT     3
-d 0B97:0000
0B97:0000  05 00 78 00 00 00 00 00-00 00 00 00 00 00 00 00  ..x.............
0B97:0010  ... (rest of memory) ...
-q

Understanding the Debugger Output

When execution hits INT 3, we examine the registers and memory:

• AX=0078: The AX register holds the final result of the multiplications. 78h is equal to 120 decimal (5 * 4 * 3 * 2 * 1).
• Memory Dump (d 0B97:0000):
  • The first two bytes 05 00 represent our input variable num (0005h in little-endian format).
  • The next two bytes 78 00 represent the result variable where we stored AX. It correctly holds 0078h.

Implementing recursion in 8086 assembly is a fantastic exercise in understanding how the processor uses the stack to keep track of where it is and what data belongs to which function call 🔄🧠.