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


                               0000  0000     1 .entry	main,0
                            7E 7CFD  0002     2 	clro	-(sp)			;result buffer
                            5E   DD  0005     3 	pushl	sp			;pointer to buffer
                            10   DD  0007     4 	pushl	#16			;descriptor: len of buffer
                       5B   5E   D0  0009     5 	movl	sp, r11			;-> descriptor
                                     000C     6 
                       7E   01   7D  000C     7 	movq	#1, -(sp)		;init 0,1
                                     000F     8 loop:
               7E   6E   04 AE   C1  000F     9 	addl3	4(sp), (sp), -(sp)	;next element on stack
                            17   1D  0014    10 	bvs	ret			;vs - overflow set, exit
                                     0016    11 
                            5B   DD  0016    12 	pushl	r11			;-> descriptor by ref
                         04 AE   DF  0018    13 	pushal	4(sp)			;-> fib on stack by ref
              00000000'GF   02   FB  001B    14 	calls	#2, g^ots$cvt_l_ti	;convert integer to string
                            5B   DD  0022    15 	pushl	r11			;
              00000000'GF   01   FB  0024    16 	calls	#1, g^lib$put_output	;show result
                            E2   11  002B    17 	brb	loop
                                     002D    18 ret:
                                 04  002D    19 	ret
                                     002E    20 .end	main
$ run fib
...
        14930352
        24157817
        39088169
        63245986
       102334155
       165580141
       267914296
       433494437
       701408733
      1134903170
      1836311903
$
 