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


 
#include <hbasic.h>
 
#define TERM1    1.61803398874989
#define TERM2    -0.61803398874989
 
#context get Fibonacci number with analitic mode
  GetArgs(n) 
  get Inv of (M_SQRT5), Mul by( Pow (TERM 1, n), Minus( Pow(TERM 2, n) )  );
  then Return\\
 
#proto fibonacci_recursive(__X__)
#synon _fibonacci_recursive    getFibonaccinumberwithrecursivemodeof
 
#proto fibonacci_iterative(__X__)
#synon _fibonacci_iterative    getFibonaccinumberwithiterativemodeof
 
Begin
  Option Stack 1024
 
  get Arg Number(2, n), and Take( n );
  then, get Fibonacci number with analitic mode, and Print It with a Newl.
  secondly, get Fibonacci number with recursive mode of(n), and Print It with a Newl.
  finally, get Fibonacci number with iterative mode of (n), and Print It with a Newl.
End
 
Subrutines
 
fibonacci_recursive(n)
   Iif ( var(n) Is Le? (2), 1 , \
         get Fibonacci number with recursive mode of( var(n) Minus (1));\
         get Fibonacci number with recursive mode of( var(n) Minus (2)); and Add It )
Return
 
fibonacci_iterative(n)
  A=0
  B=1
  For Up( I:=2, n, 1 )
    C=B
    Let ( B: = var(A) Plus (B) )
    A=C
  Next
Return(B)
 