title: NASM Assembly recursive fibonacci
body: <p>Learning NASM Assembly on 32-bit Ubuntu.</p>
  
  <p>I've been learning about recursive functions. I just did factorial, with your help here: <a href="https://stackoverflow.com/q/19217960/555690">Understanding recursive factorial function in NASM Assembly</a></p>
  
  <p>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 <code>0</code>:</p>
  
  <pre><code>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 &lt;= 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
  </code></pre>
  
  <p>It is a bit crude. I calculate fibonacci for <code>(parameter - 1)</code>, then I do it again for <code>(parameter - 2)</code>, and just add them up and put them into <code>EAX</code>.</p>
  
  <p>It doesn't work:</p>
  
  <pre><code>2 =&gt; 2
  3 =&gt; 3
  4 =&gt; 4
  5 =&gt; 4
  </code></pre>
  
  <p>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?</p>
  
  <p>One particular observation is that, for some reason, doing <code>mov ECX,EAX</code> gave me a segmentation fault error. That's why I used <code>ESI</code> instead. I'm not sure why, but I guess that it is related.</p>