汇编中的递归Fibonacci

我正在尝试在Assembly中实现递归的Fibonacci程序。但是，我的程序崩溃，有一个未处理的异常，我似乎无法找出问题。我不怀疑它涉及我对堆栈的不当使用，但我似乎无法指出哪里......

.386
.model Flat
public Fibonacci
include iosmacros.inc ;includes macros for outputting to the screen

.code
Fibonacci proc

MOV EAX, [EBP+8]
CMP EAX, 1
    JA Recurse
    MOV ECX, 1
    JMP exit

Recurse:
    DEC EAX
    MOV EDX, EAX
    PUSH EAX
    CALL Fibonacci
    ADD ESP, 4
    MOV EBX, ECX
    DEC EDX
    PUSH EDX
    CALL Fibonacci
    ADD ECX, EBX
exit:
ret
Fibonacci endp


.data


end

此外，我已经推送了我用于在外部过程中将Fibonacci值转换为堆栈的数字。任何想法可能存在的想法？

已邀请:

3 个回复

桔适丛

执行call时，下一个操作的地址将作为返回值推送到堆栈。在创建函数时，通常习惯于创建“堆栈帧”。此框架可用于打印调用堆栈，以及局部变量和参数的偏移量。通过函数开头的两个操作创建框架：

push ebp
mov ebp, esp

在函数结束时，使用leave删除调用堆栈，这相当于这两个操作的反向。当使用堆栈帧时，esp的值存储在ebp中，使其指向堆栈中称为帧基的位置。因为，在这个地址之上，有ebp的旧值和返回地址，你通常会使用[ebp+8]得到第一个参数。但是，您没有设置堆栈帧。这意味着ebp的旧值没有被推入堆栈，并且当前的值不能用于获取参数，因为你不知道它在哪里。因此，你应该使用[esp+4]得到你的论点。此外，习惯上将返回值放在eax中并且为调用者保留ebx。您的代码不遵循这些约定。此外，技术上不需要保留ecx或edx的功能，所以通常你应该在调用另一个函数之前将它们推到堆栈中，如果你想保留它们的话。使用此代码，如果使用大于2的值调用，则会覆盖edx和ebx，从而导致无效结果。这是一个完整的列表，其中包括我提到的所有修复程序。我没有创建堆栈框架，因为它没有必要，而你的代码没有。

.386
.model Flat
public Fibonacci
include iosmacros.inc ;includes macros for outputting to the screen

.code
Fibonacci proc

    MOV EAX, [ESP+4]
    CMP EAX, 1
    JA Recurse
    MOV EAX, 1 ; return value in eax
    JMP exit

Recurse:
    PUSH EBX ; preserve value of ebx
    DEC EAX
    PUSH EAX
    CALL Fibonacci
    MOV EBX, EAX ; ebx is preserved by callee, so it is safe to use
    DEC [ESP] ; decrement the value already on the stack
    CALL Fibonacci
    ADD EAX, EBX ; return value in eax
    ADD ESP, 4 ; remove value from stack
    POP EBX ; restore old value of ebx
exit:
ret
Fibonacci endp

咳累录酬

几个问题：如果要在堆栈上传递参数，则没有正确的（标准）函数条目，因此EBP指向错误的位置您没有在edx中正确保存参数值这是我认为你想要的，假设你在堆栈上传递参数（最好为每条指令添加注释）明确你的想法吧：

Fibonacci proc
  PUSH EBP          ; save previous frame pointer
  MOV  EBP, ESP     ; set current frame pointer

  MOV  EAX, [EBP+8] ; get argument N
  CMP  EAX, 1       ; N<=1?
  JA   Recurse      ; no, compute it recursively
  MOV  ECX, 1       ; yes, Fib(1)--> 1
  JMP  exit

Recurse:
  DEC  EAX          ; = N-1
  MOV  EDX, EAX     ; = N-1
  PUSH EDX          ; save N-1
  PUSH EAX          ; set argument = N-1
  CALL Fibonacci    ; compute Fib(N-1) to ECX
  POP  EAX          ; pop N-1
  DEC  EAX          ; = N-2
  PUSH ECX          ; save Fib(N-1)
  PUSH EAX          ; set argument = N-2
  CALL Fibonacci    ; compute Fib(N-2) to ECX
  POP  EAX          ; = Fib(N-1)
  ADD  ECX, EAX     ; = Fib(N-1)+FIB(N-2)
exit:
  MOV  ESP,EBP      ; reset stack to value at function entry 
  POP  EBP          ; restore caller's frame pointer
  RET               ; and return

但是您不必在堆栈上传递参数。使用寄存器更有效：

Fibonacci proc ; computes Fib(EAX) --> EAX; do not call with EAX==0
  CMP  EAX, 1      ; N<=1?
  JBE  exit        ; yes, we have the answer
  DEC  EAX         ; = N-1
  PUSH EAX         ; save N-1
  CALL Fibonacci   ; computing FIB(n-1)to EAX
  XCHG EAX,0[ESP]  ; swap FIB(n-1) for saved N-1 (You'll love this instruction, look it up in the Intel manual)
  DEC  EAX         ; = N-2
  CALL Fibonacci   ; computing FIB(N-2) to EAX
  POP  ECX         ; = FIB(N-1)
  ADD  EAX,ECX     ; = FIB(N-1)+FIB(N-2)
exit:
  RET

禽兢玫坞劲

首先，你使用EBP的堆栈偏移量为8，为什么？你不是指ESP吗？普通调用只使用一个32位单元格，所以你的arg应该是偏移4.我很确定存在其他问题，但你可以从那开始。您应该写一些伪代码，这样您和我们就可以看到您要完成的任务。如果你想作弊，谷歌搜索“nasm递归斐波那契”带你到一个工作程序。但如果你自己解决它，你将成为一个更好的程序员。

要回复问题请先登录或注册

汇编中的递归Fibonacci

3 个回复

发起人

fibonacci

assembly

问题状态

汇编中的递归Fibonacci

与内容相关的链接

3 个回复

发起人

fibonacci

assembly

问题状态