Concept of Recursion

Recursion is an important technique in programming, referring to a process or function that calls itself directly or indirectly in its definition. Implementing recursion in assembly language requires a deep understanding of stack operations and the function calling mechanism.

Types of Recursion

1. Direct Recursion

The process calls itself directly

2. Indirect Recursion

Process A calls process B, and process B calls process A

Key Elements of Recursion

1. Base Case – The termination condition of recursion
2. Recursive Case – The condition for calling itself
3. Stack Management – Saving return addresses and local variables

Detailed Implementation of Factorial Recursion

Below is a complete implementation of factorial recursion, including detailed comments:

section .data
    msg db 'Factorial of 5 is: ', 0xa
    len equ $ - msg
    newline db 0xa

section .bss
    result resb 10      ; Store result string
    ascii_buffer resb 1 ; ASCII conversion buffer

section .text
    global _start

_start:
    ; Set the number to calculate factorial
    mov ebx, 5          ; Calculate factorial of 5
    call factorial      ; Call factorial function

    ; Convert result to ASCII and display
    mov esi, result     ; Result buffer
    call number_to_ascii

    ; Display message
    mov eax, 4          ; sys_write
    mov ebx, 1          ; stdout
    mov ecx, msg        ; Message
    mov edx, len        ; Message length
    int 0x80

    ; Display result
    mov eax, 4          ; sys_write
    mov ebx, 1          ; stdout
    mov ecx, result     ; Result
    call get_string_length
    mov edx, ecx        ; String length
    int 0x80

    ; New line
    mov eax, 4
    mov ebx, 1
    mov ecx, newline
    mov edx, 1
    int 0x80

    ; Exit program
    mov eax, 1          ; sys_exit
    mov ebx, 0          ; Exit code
    int 0x80

; =============================================
; Factorial recursive function
; Input: EBX = n
; Output: EAX = n!
; =============================================
factorial:
    ; Save register state
    push ebp
    mov ebp, esp
    push ebx            ; Save EBX, as we will modify it

    ; Base case: fact(0) = 1, fact(1) = 1
    cmp ebx, 1
    jle .base_case

    ; Recursive case: fact(n) = n * fact(n-1)
    ; Save current n value
    push ebx

    ; Prepare recursive call: fact(n-1)
    dec ebx             ; n = n - 1
    call factorial      ; Recursive call

    ; Restore saved n value
    pop ebx

    ; Calculate n * fact(n-1)
    mul ebx             ; EAX = EAX * EBX
    jmp .end

.base_case:
    mov eax, 1          ; fact(0) = 1, fact(1) = 1

.end:
    ; Restore register state
    pop ebx
    mov esp, ebp
    pop ebp
    ret

; =============================================
; Convert number to ASCII string
; Input: EAX = number, ESI = output buffer
; =============================================
number_to_ascii:
    push eax
    push ebx
    push ecx
    push edx

    mov ecx, 0          ; Digit count
    mov ebx, 10         ; Divisor

.convert_loop:
    mov edx, 0          ; Clear EDX for division
    div ebx             ; EAX = EAX/10, EDX = remainder

    ; Convert number to ASCII
    add dl, '0'         ; Number to ASCII
    push dx             ; Save to stack (reverse order)
    inc ecx             ; Increase digit count

    ; Check if there are more digits to process
    cmp eax, 0
    jne .convert_loop

    ; Pop numbers from stack (in correct order)
.pop_loop:
    pop ax
    mov [esi], al       ; Store in buffer
    inc esi
    loop .pop_loop

    mov byte [esi], 0   ; String terminator

    pop edx
    pop ecx
    pop ebx
    pop eax
    ret

; =============================================
; Get string length
; Input: ECX = string address
; Output: ECX = string length
; =============================================
get_string_length:
    push eax
    push esi

    mov esi, ecx
    mov ecx, 0

.count_loop:
    mov al, [esi]
    cmp al, 0
    je .done
    inc esi
    inc ecx
    jmp .count_loop

.done:
    pop esi
    pop eax
    ret

Analysis of Recursive Call Stack

Let’s analyze the stack state when calculating fact(3):

Initial call: fact(3)
│
├── Save EBP, EBX
├── Push EBX=3
├── Call fact(2)
│   │
│   ├── Save EBP, EBX  
│   ├── Push EBX=2
│   ├── Call fact(1)
│   │   │
│   │   ├── Save EBP, EBX
│   │   ├── Base case returns EAX=1
│   │   └── Restore EBX, EBP
│   │
│   ├── Pop EBX=2
│   ├── Calculate 2 * 1 = 2
│   └── Restore EBX, EBP
│
├── Pop EBX=3
├── Calculate 3 * 2 = 6
└── Restore EBX, EBP

More Complex Recursive Example: Fibonacci Sequence

section .data
    fib_msg db 'Fibonacci sequence: ', 0
    fib_len equ $ - fib_msg
    space db ' ', 0
    newline db 0xa

section .bss
    fib_buffer resb 10

section .text
    global _start

_start:
    ; Display message
    mov eax, 4
    mov ebx, 1
    mov ecx, fib_msg
    mov edx, fib_len
    int 0x80

    ; Calculate and display the first 10 Fibonacci numbers
    mov ecx, 0          ; Counter
.fib_loop:
    push ecx
    call fibonacci      ; Calculate fib(ecx)

    ; Display number
    mov esi, fib_buffer
    call number_to_ascii

    mov eax, 4
    mov ebx, 1
    mov ecx, fib_buffer
    call get_string_length
    mov edx, ecx
    int 0x80

    ; Display space
    mov eax, 4
    mov ebx, 1
    mov ecx, space
    mov edx, 1
    int 0x80

    pop ecx
    inc ecx
    cmp ecx, 10
    jl .fib_loop

    ; New line and exit
    mov eax, 4
    mov ebx, 1
    mov ecx, newline
    mov edx, 1
    int 0x80

    mov eax, 1
    mov ebx, 0
    int 0x80

; =============================================
; Fibonacci recursive function
; Input: ECX = n
; Output: EAX = fib(n)
; =============================================
fibonacci:
    push ebp
    mov ebp, esp
    push ebx
    push ecx

    ; Base case
    cmp ecx, 0
    je .fib_0
    cmp ecx, 1
    je .fib_1

    ; Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ; Calculate fib(n-1)
    mov ebx, ecx        ; Save n
    dec ecx             ; n-1
    call fibonacci      ; fib(n-1)
    push eax            ; Save result

    ; Calculate fib(n-2)
    mov ecx, ebx        ; Restore n
    sub ecx, 2          ; n-2
    call fibonacci      ; fib(n-2)

    ; Add
    pop ebx             ; Restore fib(n-1)
    add eax, ebx        ; fib(n-1) + fib(n-2)
    jmp .end

.fib_0:
    mov eax, 0
    jmp .end

.fib_1:
    mov eax, 1

.end:
    pop ecx
    pop ebx
    mov esp, ebp
    pop ebp
    ret

Key Points of Recursive Programming

1. Stack Management

• Each recursive call consumes stack space
• Registers must be correctly saved and restored
• Be aware of stack overflow risks

2. Performance Considerations

• Recursion may be less efficient (multiple function calls)
• Consider tail recursion optimization or iterative implementation

3. Debugging Techniques

• Use a debugger to observe stack changes
• Add debug output to show recursion depth

Conclusion

Implementing recursion in assembly language requires:

1. Careful management of stack pointers and base pointers
2. Correctly saving and restoring register states
3. Clearly defining base cases and recursive cases
4. Being mindful of stack space usage to avoid overflow

By understanding the implementation mechanism of recursion at the assembly level, one can better grasp function calling conventions and stack operations, laying the foundation for writing more complex assembly programs.