使用递归过程 NASM 中的第 n 个斐波那契数 - [ASSEMBLY]

Question

这是我用来解决问题的代码：

%include "io.mac"

section .data
    msg1 db "Enter a positive number: ",0
    msg2 db "fibonacci number is: ",0
    space db " ",0

section .bss

section .text
    global _start
_start:
    PutStr msg1
    GetLInt EBX
    mov EDX,EBX
    cmp EBX,1
    jge result
    jmp _start
result:
    PutLInt EBX
    PutStr space
    PutStr msg2
    call fibo
    PutLInt EAX
    nwln
    .EXIT

fibo:
    cmp EBX,2
    jg fibo_helper
    mov EAX,1
    ret

fibo_helper:
    dec EBX
    call fibo
    mov ECX,EAX
    dec EBX
    call fibo
    ADD EAX,ECX
    ret

但是这段代码只对 n<5 输出正确的方式..对于其余的它只输出 n-1.

有人可以帮我解决这个问题吗？

Answer 1

您的算法是递归的，但是您使用寄存器来存储中间值，例如 C 中的局部变量，因此大致会发生这种情况（从头开始编写，使用调试器和单步执行指令来验证我是否正确）：

- fibo(ebx = 5): jumps to fibo_helper, ebx = 4 (--ebx), call fibo(ebx=4)
  - fibo(ebx=4): -> helper -> call fibo(ebx=3)
    - fibo(ebx=3): -> helper -> call fibo(ebx=2)
      - fibo(ebx=2), eax=1, ret
    - in helper after first call: ecx=1, --ebx, call fibo(ebx=1)
      - fibo(ebx=1), eax=1, ret
    - eax = 1 + ecx(1) = 2, ret
  - in helper after first call: ecx=2, --ebx, call fibo(ebx=0)
    - fibo(ebx=0), eax=1, ret
  - eax = 1 + ecx(2) = 3, ret
- in helper after first call: ecx=3, --ebx, call fibo(ebx=-1)
  - fibo(ebx=-1), eax=1, ret
- eax = 1 + ecx(3) = 4, ret

寄存器就像 "super globals"，如果你想创建递归算法，你必须在某个地方（动态地，最有可能在堆栈上）保存你需要的所有值，这些值必须在递归调用中存活下来。

Google 对于一些有效的 x86 示例（而不是示例，以了解即使是这样简单的实现可能有何不同），必须有很多这样的东西，即使在 SO 上也是如此...并检查一些 stack-usage vs 递归教程以获得更好的想法 how/when 来保留值。

编辑：如果您足够聪明并且可以自由设计递归函数的自定义调用约定，您通常可以通过巧妙的设计最大限度地减少堆栈内存需求。

在这种情况下，例如，您可以这样设计 fibo 函数，它会将值添加到 eax（运行总和），在 [=15] 中输入=]，这将被保留（returns 未修改的值）。所以 eax 将作为函数的输入和输出。

那么在调用之前你必须先将eax清零：

    ... set ebx to "n" ...
    xor  eax,eax
    call fibo

递归函数本身将是：

fibo:
    cmp  ebx,2
    jg   fibo_helper
    inc  eax      ; sum += 1 (fib(1) = fib(2) = 1)
    ret
fibo_helper:
    dec  ebx
    call fibo     ; sum += fib(n-1)
    dec  ebx
    call fibo     ; sum += fib(n-2)
    add  ebx,2    ; restore ebx to original value
    ret

然后堆栈内存仅用于跟踪 call+ret 对，即递归深度，无需使用它来保存值。

使用递归过程 NASM 中的第 n 个斐波那契数 - [ASSEMBLY]

nth fibonacci number in NASM using a recursive procedure - [ASSEMBLY]

recursion

assembly

nasm

fibonacci