Recursive Fibonacci in MASM Assembly

Question

So I am creating a program to give the nth term of the Fibonacci sequence. I am supposed to implement the following logic using recursive MASM assembly.

int fib(int n){ 
 if ((n == 1) || (n == 2)) 
     return n - 1; 
 else 
     return fib(n-1) + fib(n-2); 
}

The issue I seem to be having is retaining the values as the program cycles through until reaching 1. I am fairly unexperienced with recursion and I feel like I am missing something in that aspect. I am not sure how to retain the values to add them.

.code
main PROC
    mov ecx,0
    push 4          ; calculate the nth fib
    call Fib            ; calculate fib (eax)
    call WriteDec
    call Crlf
    exit
main ENDP

Fib PROC
    add ecx,1
    push ebp
    mov  ebp,esp
    mov  eax,[ebp+8]    ; get n
    cmp  eax,2      ; n == 2?
    je   exception2     
    cmp  eax,1      ; n == 1?
    je   exception2         
    dec eax
    push eax            ; Fib(n-1)
    call fib

    add eax,
    jmp Quit


Exception2:
    dec eax
Quit:
    pop  ebp            ; return EAX
    ret  4          ; clean up stack
Fib ENDP

END main

Answer 1

At the end of the procedure you must restore ESP not only EBP.

ret 4 (stdcall) is in this case not convenient because you can reuse the value on the stack for the second call.

For the result of the first call you can use a local variable which will be created on the "current" stack.

Don't mix lower and upper case in symbols even if an OPTION-directive allows it!

I changed your code accordingly:

include Irvine32.inc

.code
main PROC
    mov ecx,0
    push 10             ; calculate the nth fib
    call fib            ; calculate fib (eax)
    add esp, 4          ; clean up the stack

    call WriteDec
    call Crlf
    exit
main ENDP

fib PROC C
    add ecx,1
    push ebp
    mov  ebp,esp
    sub  esp, 4         ; space for a local dword [ebp-4]
    mov  eax,[ebp+8]    ; get n

    ; if ((n == 1) || (n == 2)) return 1;
    cmp  eax,2          ; n == 2?
    je   exception2
    cmp  eax,1          ; n == 1?
    je   exception2

    ;else return fib(n-1) + fib(n-2);
    dec eax
    push eax            ; Fib(n-1)
    call fib
    mov [ebp-4], eax    ; store first result

    dec dword ptr [esp] ; (n-1) on the stack -> (n-2)
    call fib
    add esp, 4          ; clean up stack

    add eax, [ebp-4]    ; add result and stored first result

    jmp Quit

exception2:
    mov eax, 1          ; start values: 1, 1
    ; dec eax           ; start values: 0, 1
Quit:
    mov esp, ebp        ; restore esp
    pop ebp             ; restore ebp

    ret                 ; return EAX, stack not cleaned up
fib ENDP

END main

Answer 2

assemble in VS

.686p

        .xmm

        .model  flat, c

includelib  libcmtd

printf      proto   :vararg

scanf       proto   :vararg

Fibo        proto   :dword

        .data
guid_msg    db  ' Number of protest? ', 00h

doc_form_1  db  '%d', 00h

doc_form_2  db  ' %d ', 00h

        .data?

num_i       dd  ?

num_j       dd  ?

        .code

main        proc

        invoke  printf, addr guid_msg

        invoke  scanf, addr doc_form_1, addr num_j

        mov edi, 0

     .while edi < num_j

        invoke  Fibo, edi

        invoke  printf, addr doc_form_2, eax

        inc edi

    .endw

        ret 0

main        endp

Fibo        proc    uses edx esi, num_n:dword

        mov edx, num_n

    .if         edx < 1

        xor eax, eax

     .elseif   edx < 2

        mov eax, 1

    .else

        sub edx, 1

        invoke  Fibo, edx

        mov esi, eax

        sub     edx, 1

        invoke  Fibo, edx

        add eax, esi

    .endif

        ret 0

Fibo        endp

        end