NASM Assembly recursive fibonacci

Question

Learning NASM Assembly on 32-bit Ubuntu.

I've been learning about recursive functions. I just did factorial, with your help here: Understanding recursive factorial function in NASM Assembly

Watching the code, I thought that maybe I could quickly implement fibonacci as well, using almost the same code. Here is the code, assuming that the parameter is always greater than 0:

SECTION .text
global main
main:
; -----------------------------------------------------------
; Main
; -----------------------------------------------------------
push    6
call    fibonacci
mov     [ECX],EAX
add     byte [ECX],'0'
mov     EDX,1
call    print

; -----------------------------------------------------------
; Exit
; -----------------------------------------------------------
mov EAX,1
int 0x80

; -----------------------------------------------------------
; Fibonacci recursivo: f(n) = f(n - 1) + f(n - 2)
; -----------------------------------------------------------
fibonacci:

push    EBP         ; Retrieve parameter and put it
push    EBX         ; Save previous parameter
mov     EBP,ESP     ; into EBX register
add     EBP,12      ;
mov     EBX,[EBP]   ; EBX = Param

cmp     EBX,1       ; Check for base case
jle     base        ; It is base if (n <= 1)

dec     EBX     ; Decrement EBX to put it in the stack
push    EBX     ; Put (EBX - 1) in stack
inc     EBX     ; Restore EBX
call    fibonacci   ; Calculate fibonacci for (EBX - 1)
mov ESI,EAX     ; EAX = (EAX + EBX)
pop EBX         ; Retrieve EBX from the stack

sub EBX,2       ; Decrement EBX to put it in the stack
push    EBX     ; Put (EBX - 2) in stack
add EBX,2       ; Restore EBX
call    fibonacci   ; Calculate fibonacci for (EBX - 2)
mov EDX,EAX     ; EAX = (EAX + EBX)
pop EBX         ; Retrieve EBX from the stack

add ESI,EDX
mov EAX,ESI

jmp end
base:               ; Base case
mov EAX,1           ; The result would be 1

end:

pop     EBX         ; Restore previous parameter
pop     EBP         ; Release EBP
ret

It is a bit crude. I calculate fibonacci for (parameter - 1), then I do it again for (parameter - 2), and just add them up and put them into EAX.

It doesn't work:

2 => 2
3 => 3
4 => 4
5 => 4

Fortunately I fixed the segmentation fault errors, but I probably broke something else doing that. Now I don't see what's the problem. Can you tell me why am I getting the wrong values?

One particular observation is that, for some reason, doing mov ECX,EAX gave me a segmentation fault error. That's why I used ESI instead. I'm not sure why, but I guess that it is related.

Answer 1

Whenever you're dealing with recursion, you have to be very careful about what the next layer in the recursive chain will do to the state of the current layer (e.g. register values). I'd suggest rewriting the function as follows:

fibonacci:
push    EBP         ; Retrieve parameter and put it
push    EBX         ; Save previous parameter
mov     EBP,ESP     ; into EBX register
add     EBP,12      ;
mov     EBX,[EBP]   ; EBX = Param

cmp     EBX,1       ; Check for base case
jle     base        ; It is base if (n <= 1)

lea ecx,[ebx-1]
push ecx            ; push N-1
call    fibonacci   ; Calculate fibonacci for (EBX - 1)
pop ecx             ; remove N-1 off the stack

push eax            ; save the result of fibonacci(N-1)
lea ecx,[ebx-2]
push ecx            ; push N-2
call    fibonacci   ; Calculate fibonacci for (EBX - 2)
pop ecx             ; remove N-2 off the stack
pop ecx             ; ecx = fibonacci(N-1)
add eax,ecx         ; eax = fibonacci(N-2) + fibonacci(N-1)

jmp end
base:               ; Base case
mov EAX,1           ; The result would be 1

end:
pop     EBX         ; Restore previous parameter
pop     EBP         ; Release EBP
ret