CODEWITHSUNDEEP
recursionassemblynasmfibonacci
1337r0b07
1337r0b07

Reputation: 43

nth fibonacci number in NASM using a recursive procedure - [ASSEMBLY]

Here is the code which I used to solve the problem:

%include "io.mac"

section .data
    msg1 db "Enter a positive number: ",0
    msg2 db "fibonacci number is: ",0
    space db " ",0

section .bss

section .text
    global _start
_start:
    PutStr msg1
    GetLInt EBX
    mov EDX,EBX
    cmp EBX,1
    jge result
    jmp _start
result:
    PutLInt EBX
    PutStr space
    PutStr msg2
    call fibo
    PutLInt EAX
    nwln
    .EXIT

fibo:
    cmp EBX,2
    jg fibo_helper
    mov EAX,1
    ret

fibo_helper:
    dec EBX
    call fibo
    mov ECX,EAX
    dec EBX
    call fibo
    ADD EAX,ECX
    ret

But this code outputs the right way only for n<5..for the rest it just outputs n-1.

Can someone help me with this?

Upvotes: 0

Views: 1052

Answers (1)

Ped7g
Ped7g

Reputation: 16596

Your algorithm is recursive, but you are using registers to store intermediate values like local variables in C, thus roughly this happens (writing it from head, use debugger and single step over instructions to verify I got it right):

- fibo(ebx = 5): jumps to fibo_helper, ebx = 4 (--ebx), call fibo(ebx=4)
  - fibo(ebx=4): -> helper -> call fibo(ebx=3)
    - fibo(ebx=3): -> helper -> call fibo(ebx=2)
      - fibo(ebx=2), eax=1, ret
    - in helper after first call: ecx=1, --ebx, call fibo(ebx=1)
      - fibo(ebx=1), eax=1, ret
    - eax = 1 + ecx(1) = 2, ret
  - in helper after first call: ecx=2, --ebx, call fibo(ebx=0)
    - fibo(ebx=0), eax=1, ret
  - eax = 1 + ecx(2) = 3, ret
- in helper after first call: ecx=3, --ebx, call fibo(ebx=-1)
  - fibo(ebx=-1), eax=1, ret
- eax = 1 + ecx(3) = 4, ret

The registers are like "super globals", if you want to create recursive algorithm, you must preserve all values you need somewhere (dynamically, most likely on stack), which must survive the recursive call.

Google for some working x86 example (rather exampleS to see how even such simple implementation may differ), there must be ton of this stuff, even here on SO... And check some stack-usage vs recursion tutorial to get better idea how/when to preserve values.

edit: if you are smart enough and you have free hand to design custom calling convention for your recursive function, you may often minimize the stack memory requirements by clever design.

In this case you can for example design the fibo function in such way, that it will ADD value to eax (running sum), take input in ebx = n, which will be preserved (returns unmodified value). So eax will work both as input and output of the function.

Then you will have to first clear eax to zero before call:

    ... set ebx to "n" ...
    xor  eax,eax
    call fibo

And the recursive function itself will be:

fibo:
    cmp  ebx,2
    jg   fibo_helper
    inc  eax      ; sum += 1 (fib(1) = fib(2) = 1)
    ret
fibo_helper:
    dec  ebx
    call fibo     ; sum += fib(n-1)
    dec  ebx
    call fibo     ; sum += fib(n-2)
    add  ebx,2    ; restore ebx to original value
    ret

And the stack memory is then used only to track the call+ret pairs, i.e. recursion depth, no need to use it to preserve values.

Upvotes: 2

Related Questions