Recursive fibonacci Assembly

Question

Today I wrote a recursive fibonacci in assembly and it doesn't work. I compiled it to object file with NASM and than made it elf with gcc.
When I enter 1 or 2 the function works perfectly, but when I enter 3, 4, 5, 6, or more the function doesn't work. I think there is problem where the function calls itself.

This the code:

SECTION .data ;init data




str: db "This equal: %d",10,0

SECTION .text   ;asm code


extern printf
global main

main:
push ebp
mov ebp,esp
;--------------------


push 03  ; the index 
call _fibonacci
add esp,4

push DWORD eax
push str
call printf


;---------------------

mov esp,ebp
pop ebp
ret

This is the function:

_fibonacci:

push ebp
mov ebp,esp


mov ebx, [ebp+8] ;; param n 
cmp ebx,0
jne CHECK2

mov eax,0
jmp _endFIbofunc        

CHECK2: 
    cmp ebx,0x1
    jne ELSE3
    mov eax,1
jmp _endFIbofunc

ELSE3:

mov ebx,[ebp+8] 
dec ebx  ;; n-1


;;  FIRST call
push ebx
call _fibonacci
add esp,4
mov edx,eax

;;  SEC CALL
dec ebx
push ebx
call _fibonacci
add esp,4 
add eax,edx


mov eax,[ebp-4]

_endFIbofunc:

mov esp,ebp
pop ebp
ret

After I ran it on Ubuntu 16.04 it send error:

Segmentation fault (core dumped)

What might be the problem?

Answer 1

You must store (push) the registers you are going to change in the recursive call. And then restore their original values (pop). That should fix the problem.

Something like this:

• Push all registers you are going to use in your function (except eax where you will get return value)
• Push ebx as that is your parameter
• Call the function
• Add esp,4
• Pop all registers you pushed in the first step, now in the reverse order

Answer 2

mov eax,[ebp-4]

You are using the memory at [ebp-4] without having put something useful in it! You need to reserve this space in your function prolog:

_fibonacci:
    push ebp
    mov  ebp, esp
    sub  esp, 4

Returning from the 1st recursive call you put the result from EAX in this memory dword.
Returning from the 2nd recursive call you add to EAX the contents of this memory dword.
Doing so, the EDX register will no longer be clobbered.

---

Why do you use the EBX register at all? If you use it you have to preserve it as was explained in the answer by Al Kepp.
If you start by putting the argument in EAX, you know that for both values below 2 (so 0 and 1), the result is just equal to the argument. Simple.

    mov  eax, [ebp+8] ;; param n 
    cmp  eax, 2
    jb   _endFIbofunc        

If you don't balance the stack directly after the 1st recursive call, you can just decrement the dword that is already there and make your second recursive call.

    dec  eax              ; n-1
    push eax              ;(*)
    call _fibonacci
    mov  [ebp-4], eax
    dec  dword ptr [esp]  ; n-2
    call _fibonacci
    add  esp,4            ;(*)
    add  eax, [ebp-4]

The whole proc:

_fibonacci:
    push ebp
    mov  ebp, esp
    sub  esp, 4           ;(*)
    mov  eax, [ebp+8] ;; param n 
    cmp  eax, 2
    jb   _endFIbofunc        
    dec  eax              ; n-1
    push eax              ;(*)
    call _fibonacci
    mov  [ebp-4], eax
    dec  dword ptr [esp]  ;(*) n-2
    call _fibonacci
    add  esp,4            ;(*)
    add  eax, [ebp-4]
_endFIbofunc:
    mov  esp, ebp
    pop  ebp
    ret

Answer 3

In addition to the other answers provided, here's an alternate solution:

_fibonacci:
        mov     eax,[esp+4]             ;eax = n
        cmp     eax,2                   ;br if n < 2
        jb      _endFIbofunc
        dec     eax                     ;push n-1
        push    eax
        call    _fibonacci              ;returns eax = fib(n-1)
        xchg    eax,[esp]               ;eax = n-1, [esp] = fib(n-1)
        dec     eax                     ;push n-2
        push    eax
        call    _fibonacci              ;returns eax = fib(n-2)
        add     eax,[esp+4]             ;eax = fib(n-1)+fib(n-2)
        add     esp,8
_endFIbofunc:
        ret

Trivia - fib(47) is the largest < 2^32. The number of recursive calls = 2*fib(n+1)-1.

 n     fib(n)      # calls

 0          0            1
 1          1            1
 2          1            3
 3          2            5
 4          3            9
 5          5           15
 6          8           25
 7         13           41
 8         21           67
 9         34          109
10         55          177
11         89          287
12        144          465
13        233          753
14        377         1219
15        610         1973
16        987         3193
17       1597         5167
18       2584         8361
19       4181        13529
20       6765        21891
21      10946        35421
22      17711        57313
23      28657        92735
24      46368       150049
25      75025       242785
26     121393       392835
27     196418       635621
28     317811      1028457
29     514229      1664079
30     832040      2692537
31    1346269      4356617
32    2178309      7049155
33    3524578     11405773
34    5702887     18454929
35    9227465     29860703
36   14930352     48315633
37   24157817     78176337
38   39088169    126491971
39   63245986    204668309
40  102334155    331160281
41  165580141    535828591
42  267914296    866988873
43  433494437   1402817465
44  701408733   2269806339
45 1134903170   3672623805
46 1836311903   5942430145
47 2971215073   9615053951
48 4807526976   ...