如何使用堆栈和递归在汇编中找到斐波那契数列的第 n 个元素

Question

我正在尝试在汇编 (intel x86) 中编写经典的 fib(n) 函数，即 return 斐波那契数列的第 n 个元素。

我已经很容易地编写了迭代版本，但是我在尝试使用递归进行操作时遇到了麻烦。这是我试过的：

.intel_syntax noprefix

.text

# unsigned fib(unsigned)
.globl fib

fib_n:
    enter 0, 0

    mov eax, 0

    # n = 0 or n = 1
    cmp edi, 1
    jbe end

    mov eax, 1

    # n == 2
    cmp edi, 2
    je end

    # n > 2, entering recursion

    # fib(n-1)
    push rdi
    dec edi

    call fib_n
    mov r8d, eax 

    pop rdi

    # fib(n-2)
    push rdi
    sub edi, 2

    call fib_n
    mov r9d, eax

    pop rdi

    # fib(n) = fib(n-1) + fib(n-2)
    mov eax, r8d
    add eax, r9d

end:
    leave
    ret

我期待标记为 #fib(n-1) 和 #fib(n-1) 的调用存储 local eax 产生 r8d 和 r9d 寄存器，然后通过 eax 将它们和 return 相加，但这是我得到的输出：

n = 1（第一个 el）：0（工作正常）
n = 2: 1（工作正常）
n = 3: 1（工作正常）

（错误结果）
n = 4: 2
n = 5: 2

n = 6: 3
n = 7: 3
...

我也试过将rax和rdi压入栈，但我还是得到了错误的结果。我错过了什么？

Answer 1

What am I missing?

寄存器 r8d 不会在递归调用中保留。

您不需要 enter 也不需要 leave。没有推送任何参数。
在 fib_n 的条目处保留索引 rdi 更容易。

fib_n:
    push    rdi
    xor     eax, eax
    cmp     edi, 2
    jb      end            ; fib(1) = 0
    mov     eax, 1
    je      end            ; fib(2) = 1
    dec     edi
    call    fib_n          ; -> EAX
    push    rax            ; (1) Preserve intermediate result!
    dec     edi    
    call    fib_n          ; -> EAX
    add     eax, [rsp]     ; fib(n) = fib(n-2) + fib(n-1)
    add     rsp, 8         ; (1)
end:
    pop     rdi
    ret

编辑

以下版本的代码包含了 and 的评论。
此代码现在删除了 5 base-cases 并且更加简洁。

fib_n:
    cmp     edi, 5         ; n
    jb      .LT5           ; Base-cases
    push    rdi            ; (1) Preserve n
    dec     edi            ; n-1
    call    fib_n          ; -> EAX
    push    rax            ; (2) Preserve intermediate result!
    dec     edi            ; n-2
    call    fib_n          ; -> EAX
    pop     rdi            ; (2) Restore intermediate result
    add     eax, edi       ; fib(n) = fib(n-2) + fib(n-1)
    pop     rdi            ; (1) Restore n
    ret
.LT5:
    mov     eax, edi       ; n < 5
    cmp     edi, 2
    cmc
    sbb     eax, 0         ; fib(0) = 0, fib(1) = 1
    ret                    ; fib(2) = 1, fib(3) = 2, fib(4) = 3

如何使用堆栈和递归在汇编中找到斐波那契数列的第 n 个元素

How to find n-th element of Fibonacci sequence in assembly using stack and recursion

recursion

x86

assembly

stack

fibonacci