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


 
 
// library: math: get: series: fibonacci <description></description> <version control></version control> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=getmasfi.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 22:04:02]
INTEGER PROC FNMathGetSeriesFibonacciI( INTEGER  nI )
 //
 // Method:
 //
 // 1. Take the sum of the last 2 terms
 //
 // 2. Let the sum be the last term
 //    and goto step 1
 //
 INTEGER I = 0
 INTEGER minI = 1
 INTEGER maxI = nI
 INTEGER term1I = 0
 INTEGER term2I = 1
 INTEGER term3I = 0
 //
 FOR I = minI TO maxI
  //
  // make value 3 equal to sum of two previous values 1 and 2
  //
  term3I = term1I + term2I
  //
  // make value 1 equal to next value 2
  //
  term1I = term2I
  //
  // make value 2 equal to next value 3
  //
  term2I = term3I
  //
  ENDFOR
  //
 RETURN( term3I )
 //
END
 
PROC Main()
 STRING s1[255] = "3"
 REPEAT
  IF ( NOT ( Ask( " = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF
  Warn( FNMathGetSeriesFibonacciI( Val( s1 ) ) ) // gives e.g. 3
 UNTIL FALSE
END
 
 