Recursive Fibonacci in Assembly

Question

I'm attempting to implement a recursive Fibonacci program in Assembly. However, my program crashes, with an unhandled exception, and I can't seem to pick out the problem. I don't doubt that it involves my improper use of the stack, but I can't seem to point out where...

.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

Also, I've pushed the number that I'm using to get the Fibonacci value to the stack in an external procedure. Any ideas where the problem might lie?

Answer 1

When you perform a call, the address of the next operation is pushed to the stack as a return value. When creating a function, it is often customary to create a "stack frame". This frame can be used to print the call stack, as well as an offset for local variables and arguments. The frame is created through two operations at the beginning of the function:

push ebp
mov ebp, esp

At the end of the function, the call stack is removed using leave, which is equivalent to the reverse of those 2 operations. When using a stack frame, value of esp is stored into ebp, making it point to a location on the stack called the frame's base. Since, above this address, there are the old value of ebp and the return address, you would normally get the first argument using [ebp+8]. However, you did not set up a stack frame. This means that the old value of ebp was not pushed to the stack, and the current value of ebp cannot be used to get arguments because you don't know where it is. Therefore, you should get your argument using [esp+4].

Also, it is customary that return values are placed in eax and ebx be preserved for the caller. Your code does not follow either of these conventions. Also, technically functions aren't required to preserved ecx or edx, so normally you should push them to the stack before calling another function if you want them preserved. With this code, edx and ebx would be overwritten if called with a value greater than 2, causing an invalid result.

Here is a full listing which includes all of the fixes I have mentioned. I did not create a stack frame as it is not necessary and your code didn't.

.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

Answer 2

Several problems:

• if you are going to pass parameters on the stack, you don't have the right (standard) function entry, so EBP points to the wrong place
• you aren't saving the argument value properly in edx

Here's what I think you wanted, assuming you are passing parameters on the stack (best to add a comment to each instruction making it clear what you think it does):

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

But you don't have to pass the parameters on the stack. It is more efficient to use the registers:

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