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


*        Fibonacci sequence    05/11/2014
*        integer (31 bits) = 10 decimals -> max fibo(46)
FIBONACC CSECT
         USING FIBONACC,R12    base register
SAVEAREA B     STM-SAVEAREA(R15) skip savearea
         DC    17F'0'          savearea
         DC    CL8'FIBONACC'   eyecatcher
STM      STM   R14,R12,12(R13) save previous context
         ST    R13,4(R15)      link backward
         ST    R15,8(R13)      link forward
         LR    R12,R15         set addressability
*        ----
         LA    R1,0            f(n-2)=0
         LA    R2,1            f(n-1)=1
         LA    R4,2            n=2 
         LA    R6,1            step
         LH    R7,NN           limit
LOOP     EQU   *               for n=2 to nn
         LR    R3,R2             f(n)=f(n-1)
         AR    R3,R1             f(n)=f(n-1)+f(n-2)
         CVD   R4,PW             n  convert binary to packed (PL8)
         UNPK  ZW,PW             packed (PL8) to zoned (ZL16)
         MVC   CW,ZW             zoned (ZL16) to  char (CL16)
         OI    CW+L'CW-1,X'F0'   zap sign
         MVC   WTOBUF+5(2),CW+14 output
         CVD   R3,PW             f(n) binary to packed decimal (PL8)
         MVC   ZN,EM             load mask
         ED    ZN,PW             packed dec (PL8) to char (CL20)
         MVC   WTOBUF+9(14),ZN+6 output
         WTO   MF=(E,WTOMSG)     write buffer
         LR    R1,R2             f(n-2)=f(n-1)
         LR    R2,R3             f(n-1)=f(n)
         BXLE  R4,R6,LOOP      endfor n
*        ----
         LM    R14,R12,12(R13) restore previous savearea pointer
         XR    R15,R15         return code set to 0
         BR    R14             return to caller
*        ----  DATA
NN       DC    H'46'           nn max n
PW       DS    PL8             15num
ZW       DS    ZL16
CW       DS    CL16
ZN       DS    CL20
*                  ' b 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 , 0 0 0'  15num
EM       DC    XL20'402020206B2020206B2020206B2020206B202120'  mask
WTOMSG   DS    0F
         DC    H'80',XL2'0000'
*                   fibo(46)=1836311903         
WTOBUF   DC    CL80'fibo(12)=1234567890'
         REGEQU
         END   FIBONACC