如何在NASM x86中使用递归实现阶乘算法

原代码的问题分析 #

• 递归逻辑错误：原代码在调用fak_rekursiv前执行了mul ebx，违背了阶乘n! = n * (n-1)!的递归定义，应该先获取(n-1)!的结果再与n相乘。
• 执行流错误：当n>1时，递归调用完成后会继续执行ergebnis_1的代码，把栈上的结果覆盖为1，导致最终结果完全错误。
• 寄存器处理不当：使用mul时未考虑溢出情况，且没有正确利用递归返回值完成计算。

修正后的递归阶乘代码 #

%include "asm_io.inc"

segment .data
; 无数据需要定义

segment .bss
; 无变量需要定义

segment .text
    global asm_main

asm_main:
    enter 0,0
    pusha

    call read_int       ; 读取输入整数到eax
    push eax            ; 将参数压入栈中
    call fak_rekursiv   ; 调用递归阶乘函数
    add esp, 4          ; 清理栈上的参数

    call print_int      ; 打印计算结果
    call print_nl       ; 输出换行

    popa
    mov eax, 0          ; 程序正常退出返回0
    leave
    ret

fak_rekursiv:
    enter 4, 0          ; 开辟4字节栈空间存储临时结果
    pusha

    mov eax, [ebp + 8]  ; 获取传入的参数n

    ; 递归终止条件：n ≤ 1时返回1
    cmp eax, 1
    jle ergebnis_1

    ; 递归计算(n-1)!
    dec eax             ; eax = n-1
    push eax            ; 传入参数n-1
    call fak_rekursiv   ; 调用递归，返回值存入eax
    add esp, 4          ; 清理栈上的参数

    ; 计算n * (n-1)!：原n的值存于[ebp+8]，eax当前为(n-1)!
    mov ebx, [ebp + 8]
    mul ebx             ; eax = ebx * eax = n * (n-1)!
    mov [ebp - 4], eax  ; 将结果存入栈上临时空间
    jmp ergebnis_end    ; 跳过终止条件的赋值逻辑

ergebnis_1:
    mov [ebp - 4], dword 1  ; 终止条件返回1

ergebnis_end:
    popa
    mov eax, [ebp - 4]  ; 将结果放入eax作为函数返回值
    leave
    ret

关键逻辑说明 #

• 递归终止条件：遵循数学定义，当n≤1时直接返回1（0!和1!的结果都是1）。
• 递归调用流程：对于n>1的情况，先递归计算(n-1)!，再用原n值乘以该结果，完全匹配阶乘的递归公式。
• 栈帧管理：用enter和leave维护栈帧，栈上的4字节空间用于临时存储计算结果，确保递归返回后能正确传递值。
• 寄存器安全：通过pusha和popa保存、恢复所有通用寄存器，避免递归调用破坏上层函数的寄存器状态。

内容的提问来源于stack exchange，提问作者Mouad Meziani