Nasm: fibonacci.asm

This recursive routine uses the system stack quite heavily. Every call to the routine (including the recursive calls) creates a new stack frame consisting of: any pushed arguments; the return address; the saved value of the ebp register; any other saved registers; and any local variables.

;----------------------------------------------------------------
; fib1.asm
;   as developed in class.
;
; 2005-10-28
;----------------------------------------------------------------
%ifdef ELF
%define _fib fib     ; work with Linux as well
%endif

    section .text
    global _fib     ; '_' to be DOS/Win compatible

_fib:
    push ebp
    mov  ebp, esp
    sub  esp, 16    ; ...AA-A-A-ND we've built the stack frame
    
    mov  eax, [ebp+8]
    cmp  eax, 2
    jae  .recur

    xor  edx, edx
    jmp  .done

.recur:
    sub  eax, 2
    push eax            ; compute fib(n-2)
    call _fib
    mov  [ebp-8], eax   ; save returned value in 8-byte local variable...
    mov  [ebp-4], edx   ; ...in Little-Endian byte order.

    mov  eax, [ebp+8]   ; get argument again
    dec  eax
    push eax            ; compute fib(n-1)
    call _fib
    mov  [ebp-16], eax  ; save returned value in 8-byte local variable...
    mov  [ebp-12], edx  ; ...in Little-Endian byte order.

; the next steps are not as efficient as they could be...
    mov  eax, [ebp-8]
    mov  edx, [ebp-4]   ; retrieve 1st computed value
    add  eax, [ebp-16]
    adc  edx, [ebp-12]  ; add 2nd computed value
.done:
    mov  esp, ebp
    pop  ebp
    ret
;----------------------------------------------------------------