Fibonacci sequence

Fibonacci sequence
You are encouraged to solve this task according to the task description, using any language you may know.

The Fibonacci sequence is a sequence of numbers defined as such:

Where n is an integer greater than 2:
F1 = F2 = 1
Fn = Fn-1 + Fn-2

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).

BASIC

Works with: QuickBasic version 4.5

Iterative

<qbasic>FUNCTION itFib (n) IF (n <= 2) THEN

       itFib = 1

ELSE

       ans = 0
       n1 = 1
       n2 = 1
       n = n - 2
       DO WHILE (n > 0)
               ans = n1 + n2
               n1 = n2
               n2 = ans
               n = n - 1
       LOOP
       itFib = ans

END IF END FUNCTION</qbasic>

Recursive

<qbasic>FUNCTION recFib (n) IF (n <= 2) THEN

       recFib = 1

ELSE

       recFib = recFib(n - 1) + recFib(n - 2)

END IF END FUNCTION</qbasic>

Befunge

00:.1:.>:"@"8**++\1+:67+`#@_v
       ^ .:\/*8"@"\%*8"@":\ <

D

Here are four version of Fibonacci Number generating functions.
FibD has an argument limit of magnitude 82 due to floating point precision, the others have a limit of 92 due to overflow (long).
The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results.
All four functions have extended to deal with negative argument. <d>module fibonacci ; import std.stdio ; import std.math ; import std.conv ;

long FibD(int m) { // Direct Calculation, correct for abs(m) <= 82

 const real sqrt5r = 0.44721359549995793928L ; // 1 / sqrt(5)
 const real golden = 1.6180339887498948482L ;  // (1 + sqrt(5)) / 2 ;
 real sign = (m < 0) && (1 & m ^ 1) ? -1.0L : 1.0L ;
 return rndtol(pow(golden, abs(m)) * sign * sqrt5r)  ;

} long FibI(int m) { // Iterative

 int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
 int n = m < 0 ? -m : m ;
 if (n < 2)
   return n ;
 long prevFib = 0 ;
 long thisFib = 1 ;
 for(int i = 1 ; i < n ;i++) {
   long tmp = thisFib ;
   thisFib += prevFib ;
   prevFib = tmp ;
 } 
 return thisFib*sign ;   

} long FibR(int m) { // Recursive

 if (m == 0 || m == 1) return m ;
 return (m >= 0) ? FibR(m-1) + FibR(m-2) : (1 & m ^ 1) ? - FibR(-m) : FibR(-m)  ;

} long FibO(int m) { // Optimized Recursive

 static long[] fib = [0,1] ;

 int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
 int n = m < 0 ? -m : m ;  

 if(n >= fib.length )
   fib ~= FibO(n-2) + FibO(n-1) ;
 return fib[n]*sign ;    

} void main(string[] args) {

 int k = args.length > 1 ? toInt(args[1]) : 10 ;
 writefln("Fib(%3d) = ", k) ;
 writefln("D : %20d <- %20d + %20d", FibD(k), FibD(k - 1), FibD(k - 2) ) ;
 writefln("I : %20d <- %20d + %20d", FibI(k), FibI(k - 1), FibI(k - 2) ) ;
 if( abs(k) < 36 || args.length > 2) // set a limit for recursive version
 writefln("R : %20d <- %20d + %20d", FibR(k), FibO(k - 1), FibO(k - 2) ) ;
 writefln("O : %20d <- %20d + %20d", FibO(k), FibO(k - 1), FibO(k - 2) ) ;

}</d> Output for n = 83:

Fib( 83) =
D :    99194853094755496 <-    61305790721611591 +    37889062373143906
I :    99194853094755497 <-    61305790721611591 +    37889062373143906
O :    99194853094755497 <-    61305790721611591 +    37889062373143906

Forth

: fib ( n -- fib )
  0 1 rot 0 ?do  over + swap  loop drop ;

Java

Iterative

<java>public static long itFibN(int n){ if(n <= 2)return 1; long ans = 0; long n1 = 1; long n2 = 1; for(n -= 2;n > 0;n--){ ans = n1 + n2; n1 = n2; n2 = ans; } return ans; }</java>

Recursive

<java>public static long recFibN(int n){ if(n <= 2) return 1; return recFibN(n-1) + recFibN(n-2); }</java>

MAXScript

Iterative

fn fibIter n =
(
    if n <= 2 then
    (
        1
    )
    else
    (
        fib = 1
        fibPrev = 1
        for num in 3 to n do
        (
            temp = fib
            fib += fibPrev
            fibPrev = temp
        )
        fib
    ) 
)

Recursive

fn fibRec n =
(
    if n <= 2 then
    (
        1
    )
    else
    (
        fibRec (n - 1) + fibRec (n - 2)
    )
)

Python

Iterative

<python>def fibIter(n):

   if n <= 2:
       return 1
   fibPrev = 1
   fib = 1
   for num in xrange(2, n):
       temp = fib
       fib += fibPrev
       fibPrev = temp
   return fib</python>

Recursive

<python>def fibRec(n):

   if n <= 2:
       return 1
   else:
       return fibRec(n-1) + fibRec(n-2)</python>