The Fibonacci sequence is a sequence    Fn    of natural numbers defined recursively:

      F0 = 0 
      F1 = 1 
      Fn = Fn-1 + Fn-2, if n>1 



Task

Write a function to generate the    nth    Fibonacci number.

Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).

The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:

      Fn = Fn+2 - Fn+1, if n<0   

support for negative      n      in the solution is optional.



Related tasks

   Fibonacci n-step number sequences‎
   Leonardo numbers


References

   Wikipedia, Fibonacci number
   Wikipedia, Lucas number
   MathWorld, Fibonacci Number
   Some identities for r-Fibonacci numbers
   OEIS Fibonacci numbers
   OEIS Lucas numbers


fib:
; 	WRITTEN IN C WITH X86-64 CLANG 3.3 AND DOWNGRADED TO 16-BIT X86
; 	INPUT: DI = THE NUMBER YOU WISH TO CALC THE FIBONACCI NUMBER FOR.
;	OUTPUTS TO AX
 
        push    BP
        push    BX
        push    AX
        mov     BX, DI			;COPY INPUT TO BX
        xor     AX, AX			;MOV AX,0
        test    BX, BX			;SET FLAGS ACCORDING TO BX
        je      LBB0_4			;IF BX == 0 RETURN 0
        cmp     BX, 1			;IF BX == 1 RETURN 1
        jne     LBB0_3
        mov     AX, 1			;ELSE, SET AX = 1 AND RETURN
        jmp     LBB0_4
LBB0_3:
        lea     DI, WORD PTR [BX - 1]   ;DI = BX - 1
        call    fib			;RETURN FIB(BX-1)
        mov     BP, AX			;STORE THIS IN BP
        add     BX, -2
        mov     DI, BX	
        call    fib			;GET FIB(DI - 2)
        add     AX, BP		        ;RETURN FIB(DI - 1) + FIB(DI - 2)
LBB0_4:
 
	add sp,2
        pop     BX
        pop     BP
        ret