recursion - How to find n-th element of Fibonacci sequence in assembly using stack and recursion

Question

I am trying to write classical fib(n) function in assembly (intel x86) that is returning a n-th element of Fibonacci sequence.

I have written iterative version quite easily, but I'm having trouble trying to manipulate with recursion. This is what I tried:

.intel_syntax noprefix

.text

# unsigned fib(unsigned)
.globl fib

fib_n:
    enter 0, 0

    mov eax, 0

    # n = 0 or n = 1
    cmp edi, 1
    jbe end

    mov eax, 1

    # n == 2
    cmp edi, 2
    je end

    # n > 2, entering recursion

    # fib(n-1)
    push rdi
    dec edi

    call fib_n
    mov r8d, eax 

    pop rdi

    # fib(n-2)
    push rdi
    sub edi, 2

    call fib_n
    mov r9d, eax

    pop rdi

    # fib(n) = fib(n-1) + fib(n-2)
    mov eax, r8d
    add eax, r9d

end:
    leave
    ret

I am expecting for calls marked #fib(n-1) and #fib(n-1) to store local eax results in r8d and r9d registers, and then just add them and return through eax, but this is what I get as output:

n = 1 (1st el): 0 (works fine)
n = 2: 1 (works fine)
n = 3: 1 (works fine)

(wrong results)
n = 4: 2
n = 5: 2

n = 6: 3
n = 7: 3
...

I also tried pushing rax to the stack as well as rdi, but I still get wrong results. What am I missing?

标签： recursionassemblyx86stackfibonacci

Answer 1

What am I missing?

Register r8d is not preserved across recursive calls.

You don't need enter nor leave. No parameters were pushed.
It's easier to preserve the index rdi at the entry of fib_n.

fib_n:
    push    rdi
    xor     eax, eax
    cmp     edi, 2
    jb      end            ; fib(1) = 0
    mov     eax, 1
    je      end            ; fib(2) = 1
    dec     edi
    call    fib_n          ; -> EAX
    push    rax            ; (1) Preserve intermediate result!
    dec     edi    
    call    fib_n          ; -> EAX
    add     eax, [rsp]     ; fib(n) = fib(n-2) + fib(n-1)
    add     rsp, 8         ; (1)
end:
    pop     rdi
    ret

EDIT

The below version of the code incorporates comments made by rcgldr and Peter Cordes.
This code now removes 5 base-cases and is much cleaner.

fib_n:
    cmp     edi, 5         ; n
    jb      .LT5           ; Base-cases
    push    rdi            ; (1) Preserve n
    dec     edi            ; n-1
    call    fib_n          ; -> EAX
    push    rax            ; (2) Preserve intermediate result!
    dec     edi            ; n-2
    call    fib_n          ; -> EAX
    pop     rdi            ; (2) Restore intermediate result
    add     eax, edi       ; fib(n) = fib(n-2) + fib(n-1)
    pop     rdi            ; (1) Restore n
    ret
.LT5:
    mov     eax, edi       ; n < 5
    cmp     edi, 2
    cmc
    sbb     eax, 0         ; fib(0) = 0, fib(1) = 1
    ret                    ; fib(2) = 1, fib(3) = 2, fib(4) = 3