x86汇编（AT&T语法）递归斐波那契程序栈溢出问题排查

你的代码出现栈溢出引发的段错误，主要有两个核心问题，咱们一步步拆解分析：

1. 递归调用后未清理栈上的参数 #

你采用的是C调用约定（cdecl），这种规则下调用者必须负责清理传递给函数的栈参数。看你每次调用fibonacci前都会用push %ecx传递参数，但调用结束后完全没做栈清理操作——这意味着每一层递归都会在栈上残留4字节的无用数据，递归深度稍大就会直接把栈空间撑爆。

比如这段有问题的代码：

decl %ecx
push %ecx
call fibonacci
# 这里缺少清理栈参数的关键步骤！
movl %eax, fibMinus1(%esp)

每次调用完fibonacci后，必须执行addl $4, %esp，把刚才push的参数从栈上抹去，让栈指针恢复到调用前的位置。

2. 错误的栈帧寻址方式导致数据存错 #

你定义fibMinus1用来存储fib(n-1)的结果，但误用了%esp来寻址——%esp会随着push/pop操作不断变化，而栈帧的基址寄存器%ebp才是固定不变的，只有用它才能准确访问栈帧内的局部变量。

你当前的写法：

movl %eax, fibMinus1(%esp)

在push %ecx后，%esp已经比栈帧基址%ebp小了8字节（预留局部变量的4字节+push参数的4字节），此时fibMinus1(%esp)指向的根本不是你预留的局部变量位置，而是栈上的其他区域，会导致数据覆盖或读取错误，进一步加剧栈的混乱。

正确的写法应该是用%ebp寻址：

movl %eax, fibMinus1(%ebp)

因为fibMinus1定义为-4，对应栈帧基址%ebp偏移-4的位置，也就是你一开始sub $4, %esp预留的局部变量空间。

修复后的完整代码 #

# Function signature: 
# int fibonacci(int n)
.text
.equ n, 8                  # 参数n在ebp+8的位置
.equ fibMinus1, -4         # 局部变量fib(n-1)在ebp-4的位置
.global fibonacci
fibonacci:
    # Prologue (prepare the stack frame)
    push %ebp
    mov %esp, %ebp
    subl $4, %esp          # 提前为局部变量预留空间，栈帧结构更清晰
    
    # ECX存储参数n
    movl n(%ebp), %ecx
    
    # 如果n == 0，返回0
    cmpl $0, %ecx
    je retZero
    
    # 如果n == 1，返回1
    cmpl $1, %ecx
    je retOne
    
    # 计算fib(n-1)并保存到局部变量
    decl %ecx
    push %ecx
    call fibonacci
    addl $4, %esp          # 清理栈上的参数
    movl %eax, fibMinus1(%ebp)  # 用ebp寻址存储结果
    
    # 计算fib(n-2)
    movl n(%ebp), %ecx
    subl $2, %ecx
    push %ecx
    call fibonacci
    addl $4, %esp          # 清理栈上的参数
    
    # 结果 = fib(n-1) + fib(n-2)
    addl fibMinus1(%ebp), %eax
    
    # Epilogue
    mov %ebp, %esp
    pop %ebp
    ret

retZero:
    movl $0, %eax
    mov %ebp, %esp
    pop %ebp
    ret

retOne:
    movl $1, %eax
    mov %ebp, %esp
    pop %ebp
    ret

额外优化建议 #

• 递归斐波那契本身时间复杂度是O(2^n)，如果输入的n值过大，即便修复了栈问题也会因为递归层数太多导致性能极差，建议用迭代版本或者手动实现尾递归优化（x86不会自动做尾递归优化）。

内容的提问来源于stack exchange，提问作者Adam Lee