Fibonacci sequence

This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

The Fibonacci sequence is a sequence F_n of natural numbers defined recursively:

F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2, if n>1

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). Support for negative n is optional.

References:

ActionScript

<lang actionscript>public function fib(n:uint):uint {

   if (n < 2)
       return n;
   
   return fib(n - 1) + fib(n - 2);

}</lang>

AppleScript

<lang applescript>set fibs to {} set x to (text returned of (display dialog "What fibbonaci number do you want?" default answer "3")) set x to x as integer repeat with y from 1 to x if (y = 1 or y = 2) then copy 1 to the end of fibs else copy ((item (y - 1) of fibs) + (item (y - 2) of fibs)) to the end of fibs end if end repeat return item x of fibs</lang>

Ada

<lang ada>with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Fibonacci is

  function Fibonacci (N : Natural) return Natural is
     This : Natural := 0;
     That : Natural := 1;
     Sum  : Natural;
  begin
     for I in 1..N loop
        Sum  := This + That;
        That := This;
        This := Sum;
     end loop;
     return This;
  end Fibonacci;

begin

  for N in 0..10 loop
     Put_Line (Positive'Image (Fibonacci (N)));
  end loop;

end Test_Fibonacci;</lang> Sample output:

ALGOL 68

Analytic

PROC analytic fibonacci = (LONG INT n)LONG INT:(
  LONG REAL sqrt 5 = long sqrt(5);
  LONG REAL p = (1 + sqrt 5) / 2;
  LONG REAL q = 1/p;
  ENTIER( (p**n + q**n) / sqrt 5 )
);

Iterative

PROC iterative fibonacci = (INT n)INT: 
  CASE n+1 IN
    0, 1, 1, 2, 3
  OUT
    []INT init = (0, 1);
    [0:1]INT cache := init[@0];
    FOR i FROM UPB cache + 1 TO n DO
      cache[i MOD 2] := cache[0] + cache[1]
    OD;
    cache[n MOD 2]
  ESAC;

Recursive

PROC recursive fibonacci = (INT n)INT:
  ( n < 2 | n | fib(n-1) + fib(n-2));

Generative

Translation of: Python

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

<lang algol68>MODE YIELDINT = PROC(INT)VOID; MODE FORINT = PROC(YIELDINT)VOID;

PROC for fibonacci = (INT n, YIELDINT yield)VOID: (

 [0:1]INT cache := []INT(0,1)[@0];
 yield(cache[0]);
 yield(cache[1]);
 FOR i FROM UPB cache + 1 TO n DO
   cache[i MOD 2] := cache[0] + cache[1];
   yield(cache[i MOD 2])
 OD

);

FOR n IN fibonacci(30) DO #

for fibonacci(30, (INT n)VOID:

 print((" ",whole(n,0)))

); print(new line)</lang> Output:

1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040

AutoHotkey

Search autohotkey.com: sequence

Iterative

Translated from c example <lang AutoHotkey>Loop, 5

 MsgBox % fib(A_Index)

Return

fib(n) {

 If (n < 2) 
   Return n
 i := last := this := 1
 While (i <= n)
 {
   new := last + this
   last := this
   this := new
   i++
 }
 Return this

}</lang>

Recursive and iterative

Source: AutoHotkey forum by Laszlo <lang AutoHotkey>/* Important note: the recursive version would be very slow without a global or static array. The iterative version handles also negative arguments properly.

/

FibR(n) { ; n-th Fibonacci number (n>=0, recursive with static array Fibo)

  Static 
  Return n<2 ? n : Fibo%n% ? Fibo%n% : Fibo%n% := FibR(n-1)+FibR(n-2)

}

Fib(n) { ; n-th Fibonacci number (n < 0 OK, iterative)

  a := 0, b := 1 
  Loop % abs(n)-1 
     c := b, b += a, a := c 
  Return n=0 ? 0 : n>0 || n&1 ? b : -b

}</lang>

Recursive

<lang AutoHotkey>Fib(n) {

Return % ((n = 0) ? 1 : ((n < 0) ? 0 : Fib(n - 1)))

}</lang>

AWK

As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout. <lang awk>$ awk 'func fib(n){return(n<2?n:fib(n-1)+fib(n-2))}{print "fib("$1")="fib($1)}' 10 fib(10)=55</lang>

BASIC

Works with: QuickBasic version 4.5

Works with: FreeBASIC version 0.20.0

Iterative

<lang qbasic>FUNCTION itFib (n)

   n1 = 0
   n2 = 1
   FOR k = 1 TO n

sum = n1 + n2 n1 = n2 n2 = sum

   NEXT k
   itFib = n1

END FUNCTION</lang>

This one calculates each value once, as needed, and stores the results in an array for later retreival. <lang qbasic>DECLARE FUNCTION fibonacci& (n AS INTEGER)

REDIM SHARED fibNum(1) AS LONG

fibNum(1) = 1

'*****sample inputs***** PRINT fibonacci(0) PRINT fibonacci(13) PRINT fibonacci(42) PRINT fibonacci(47) 'should be rejected PRINT fibonacci(-1) 'should be rejected '*****sample inputs*****

FUNCTION fibonacci& (n AS INTEGER)

   SELECT CASE n
       CASE 0 TO 46
           SHARED fibNum() AS LONG
           DIM u AS INTEGER, Loop0 AS INTEGER
           u = UBOUND(fibNum)
           IF n > u THEN
               REDIM PRESERVE fibNum(n) AS LONG
               FOR Loop0 = u + 1 TO n
                   fibNum(Loop0) = fibNum(Loop0 - 1) + fibNum(Loop0 - 2)
               NEXT
           END IF
           fibonacci = fibNum(n)
       CASE ELSE
           'no negative numbers
           'also, many BASICs are limited to signed 32-bit ints (LONG)
           'fib(47)=&hB11924E1
           fibonacci = -1
   END SELECT

END FUNCTION</lang> Outputs:

Recursive

<lang qbasic>FUNCTION recFib (n)

   IF (n < 2) THEN

recFib = n

   ELSE

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

   END IF

END FUNCTION</lang>

Array (Table) Lookup

This uses a pre-generated list, requiring much less run-time processor usage. (Since the sequence never changes, this is probably the best way to do this in "the real world". The same applies to other sequences like prime numbers, and numbers like pi and e.) <lang qbasic>DATA 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765 DATA 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269 DATA 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986 DATA 102334155,165580141,267914296,433494437,701408733,1134903170,1836311903

DIM fibNum(46) AS LONG

FOR n = 0 TO 46

   READ fibNum(n)

bc

iterative

<lang bc>#! /usr/bin/bc -q

define fib(x) {

   if (x <= 0) return 0;
   if (x == 1) return 1;

   a = 0;
   b = 1;
   for (i = 1; i < x; i++) {
       c = a+b; a = b; b = c;
   }
   return c;

} fib(1000) quit</lang>

Befunge

<lang befunge>00:.1:.>:"@"8**++\1+:67+`#@_v

      ^ .:\/*8"@"\%*8"@":\ <</lang>

Brainf***

The first cell contains n (10), the second cell will contain fib(n) (55), and the third cell will contain fib(n-1) (34). <lang bf>++++++++++ >>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]</lang>

C

Recursive

<lang c>long long unsigned fib(unsigned n) {

   return n < 2 ? n : fib(n - 1) + fib(n - 2);

}</lang>

Iterative

<lang c>long long unsigned fib(unsigned n) {

   long long unsigned last = 0, this = 1, new, i;
   if (n < 2) return n;
   for (i = 1 ; i < n ; ++i) {
       new = last + this;
       last = this;
       this = new;
   }
   return this;

}</lang>

Analytic

<lang c>#include <tgmath.h>

define PHI ((1 + sqrt(5))/2)

long long unsigned fib(unsigned n) {

   return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );

}</lang>

Generative

Translation of: Python

Works with: gcc version version 4.1.2 20080704 (Red Hat 4.1.2-44)

<lang c>#include <stdio.h> typedef enum{false=0, true=!0} bool; typedef void iterator;

include <setjmp.h>

/* declare label otherwise it is not visible in sub-scope */

define LABEL(label) jmp_buf label; if(setjmp(label))goto label;
define GOTO(label) longjmp(label, true)

/* the following line is the only time I have ever required "auto" */

define FOR(i, iterator) { auto bool lambda(i); yield_init = (void *)λ iterator; bool lambda(i)
define DO {
define YIELD(x) if(!yield(x))return
define BREAK return false
define CONTINUE return true
define OD CONTINUE; } }

static volatile void *yield_init; /* not thread safe */

define YIELDS(type) bool (*yield)(type) = yield_init

iterator fibonacci(int stop){

   YIELDS(int);
   int f[] = {0, 1};
   int i;
   for(i=0; i<stop; i++){
       YIELD(f[i%2]);
       f[i%2]=f[0]+f[1];
   }

}

main(){

 printf("fibonacci: ");
 FOR(int i, fibonacci(16)) DO
   printf("%d, ",i);
 OD;
 printf("...\n");

}</lang> Output:

fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

C++

Using unsigned int, this version only works up to 48 before fib overflows. <lang cpp>#include <iostream>

int main() {

       unsigned int a = 1, b = 1;
       unsigned int target = 48;
       for(unsigned int n = 3; n <= target; ++n)
       {
               unsigned int fib = a + b;
               std::cout << "F("<< n << ") = " << fib << std::endl;
               a = b;
               b = fib;
       }

       return 0;

}</lang>

Library: GMP

This version does not have an upper bound.

<lang cpp>#include <iostream>

include <gmpxx.h>

int main() {

       mpz_class a = mpz_class(1), b = mpz_class(1);
       mpz_class target = mpz_class(100);
       for(mpz_class n = mpz_class(3); n <= target; ++n)
       {
               mpz_class fib = b + a;
               if ( fib < b )
               {
                       std::cout << "Overflow at " << n << std::endl;
                       break;
               }
               std::cout << "F("<< n << ") = " << fib << std::endl;
               a = b;
               b = fib;
       }
       return 0;

}</lang>

Version using transform: <lang cpp>#include <algorithm>

include <functional>
include <iostream>

unsigned int fibonacci(unsigned int n) {

 if (n == 0) return 0;
 int *array = new int[n+1];
 array[0] = 0;
 array[1] = 1;
 std::transform(array, array+n-1, array+1, array+2, std::plus<int>());
 // "array" now contains the Fibonacci sequence from 0 up
 int result = array[n];
 delete [] array;
 return result;

}</lang>

Far-fetched version using adjacent_difference: <lang cpp>#include <numeric>

include <functional>
include <iostream>

unsigned int fibonacci(unsigned int n) {

 if (n == 0) return 0;
 int *array = new int[n];
 array[0] = 1;
 std::adjacent_difference(array, array+n-1, array+1, std::plus<int>());
 // "array" now contains the Fibonacci sequence from 1 up
 int result = array[n-1];
 delete [] array;
 return result;

}</lang>

Version which computes at compile time with metaprogramming: <lang cpp>#include <iostream>

template <int n> struct fibo {

   enum {value=fibo<n-1>::value+fibo<n-2>::value};

};

template <> struct fibo<0> {

   enum {value=0};

};

template <> struct fibo<1> {

   enum {value=1};

};

int main(int argc, char const *argv[]) {

   std::cout<<fibo<12>::value<<std::endl;
   std::cout<<fibo<46>::value<<std::endl;
   return 0;

}</lang>

C#

Recursive

<lang csharp>static long recFib(int n) {

   if (n < 2) return n;
   return recFib(n - 1) + recFib(n - 2);

}</lang>

Chef

<lang chef> Stir-Fried Fibonacci Sequence.

An unobfuscated iterative implementation. It prints the first N + 1 Fibonacci numbers, where N is taken from standard input.

Ingredients. 0 g last 1 g this 0 g new 0 g input

Method. Take input from refrigerator. Put this into 4th mixing bowl. Loop the input. Clean the 3rd mixing bowl. Put last into 3rd mixing bowl. Add this into 3rd mixing bowl. Fold new into 3rd mixing bowl. Clean the 1st mixing bowl. Put this into 1st mixing bowl. Fold last into 1st mixing bowl. Clean the 2nd mixing bowl. Put new into 2nd mixing bowl. Fold this into 2nd mixing bowl. Put new into 4th mixing bowl. Endloop input until looped. Pour contents of the 4th mixing bowl into baking dish.

Serves 1.</lang>

Clojure

This is implemented idiomatically as an infinitely long, lazy sequence of all Fibonacci numbers: <lang lisp>(defn fibs []

 (map first (iterate (fn a b [b (+ a b)]) [0 1])))</lang>

Thus to get the nth one: <lang lisp>(nth (fibs) 5)</lang> So long as one does not hold onto the head of the sequence, this is unconstrained by length.

Common Lisp

Note that Common Lisp uses bignums, so this will never overflow.

<lang lisp>(defun fibonacci-recursive (n)

 (if (< n 2)
     n
    (+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))</lang>

<lang lisp>(defun fibonacci-iterative (n)

 (if (< n 2)
    n
   (let ((result 0)
         (a 1)
         (b 1))
     (loop for n from (- n 2) downto 1
       do (setq result (+ a b)
                a b
                b result))
     result)))</lang>

D

Here are four versions 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 support for negative arguments. <lang 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) ) ;

}</lang> Output for n = 83:

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

E

<lang e>def fib(n) {

   var s := [0, 1]
   for _ in 0..!n { 
       def [a, b] := s
       s := [b, a+b]
   }
   return s[0]

}</lang>

(This version defines fib(0) = 0 because OEIS A000045 does.)

Erlang

Recursive: <lang erlang>fib(0) -> 0; fib(1) -> 1; fib(N) when N > 1 -> fib(N-1) + fib(N-2).</lang>

Tail-recursive (iterative): <lang erlang>fib(N) -> fib(N,0,1). fib(0,Res,_) -> Res; fib(N,Res,Next) when N > 0 -> fib(N-1, Next, Res+Next).</lang>

FALSE

Factor

Iterative

<lang factor>: fib ( n -- m )

   dup 2 < [
       [ 0 1 ] dip [ swap [ + ] keep ] times
       drop
   ] unless ;</lang>

Recursive

<lang factor>: fib ( n -- m )

   dup 2 < [
       [ 1 - fib ] [ 2 - fib ] bi +
   ] unless ;</lang>

Matrix

Translation of: Ruby

<lang factor>USE: math.matrices

fib ( n -- m )

   dup 2 < [
       [ { { 0 1 } { 1 1 } } ] dip 1 - m^n
       second second
   ] unless ;</lang>

Forth

<lang forth>: fib ( n -- fib )

 0 1 rot 0 ?do  over + swap  loop drop ;</lang>

Fortran

Recursive

In ISO Fortran 90 or later, use a RECURSIVE function: <lang fortran>module fibonacci contains

   recursive function fibR(n) result(fib)
       integer, intent(in) :: n
       integer             :: fib
       
       select case (n)
           case (:0);      fib = 0
           case (1);       fib = 1
           case default;   fib = fibR(n-1) + fibR(n-2)
       end select
   end function fibR</lang>

Iterative

In ISO Fortran 90 or later: <lang fortran> function fibI(n)

       integer, intent(in) :: n
       integer, parameter :: fib0 = 0, fib1 = 1
       integer            :: fibI, back1, back2, i

       select case (n)
           case (:0);      fibI = fib0
           case (1);       fibI = fib1
    
           case default
               fibI = fib1
               back1 = fib0
               do i = 2, n
                   back2 = back1
                   back1 = fibI
                   fibI   = back1 + back2
               end do
        end select
   end function fibI

end module fibonacci</lang>

Test program <lang fortran>program fibTest

   use fibonacci
   
   do i = 0, 10
       print *, fibr(i), fibi(i)
   end do

end program fibTest</lang>

Output

F#

This is a fast [tail-recursive] approach using the F# big integer support. <lang fsharp>#light open Microsoft.FSharp.Math let fibonacci n : bigint =

   let rec f a b n =
       match n with
       | 0I -> a
       | 1I -> b
       | n -> (f b (a + b) (n - 1I))
   f 0I 1I n

> fibonacci 100I ;; val it : bigint = 354224848179261915075I</lang>

Go

Recursive

<lang go>func fib(a int) int {

 if a < 2 {
   return a
 }
 return fib(a - 1) + fib(a - 2)

}</lang>

Groovy

Recursive

A recursive closure must be pre-declared. <lang groovy>def rFib rFib = { it < 1 ? 0 : it == 1 ? 1 : rFib(it-1) + rFib(it-2) }</lang>

Iterative

Test program: <lang groovy>(0..20).each { println "${it}: ${rFib(it)} ${iFib(it)}" }</lang>

Output:

0:    0    0
1:    1    1
2:    1    1
3:    2    2
4:    3    3
5:    5    5
6:    8    8
7:    13    13
8:    21    21
9:    34    34
10:    55    55
11:    89    89
12:    144    144
13:    233    233
14:    377    377
15:    610    610
16:    987    987
17:    1597    1597
18:    2584    2584
19:    4181    4181
20:    6765    6765

HaXe

Iterative

<lang HaXe>static function fib(steps:Int, handler:Int->Void) { var current = 0; var next = 1;

for (i in 1...steps) { handler(current);

var temp = current + next; current = next; next = temp; } handler(current); }</lang>

As Iterator

<lang HaXe>class FibIter { public var current:Int; private var nextItem:Int; private var limit:Int;

public function new(limit) { current = 0; nextItem = 1; this.limit = limit; }

public function hasNext() return limit > 0

public function next() { limit--; var ret = current; var temp = current + nextItem; current = nextItem; nextItem = temp; return ret; } }</lang>

Used like:

<lang HaXe>for (i in new FibIter(10)) Lib.println(i);</lang>

Haskell

With lazy lists

This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:

<lang haskell>fib = 0 : 1 : zipWith (+) fib (tail fib)</lang>

The nth Fibonacci number is then just fib !! n.

With matrix exponentiation

With the (rather slow) code from Matrix exponentiation operator

<lang haskell>import Data.List

xs <+> ys = zipWith (+) xs ys xs <*> ys = sum $ zipWith (*) xs ys

newtype Mat a = Mat {unMat :: a} deriving Eq

instance Show a => Show (Mat a) where

 show xm = "Mat " ++ show (unMat xm)

instance Num a => Num (Mat a) where

 negate xm = Mat $ map (map negate) $ unMat xm
 xm + ym   = Mat $ zipWith (<+>) (unMat xm) (unMat ym)
 xm * ym   = Mat [[xs <*> ys | ys <- transpose $ unMat ym] | xs <- unMat xm]
 fromInteger n = Mat fromInteger n</lang>

we can simply write

<lang haskell>fib 0 = 0 -- this line is necessary because "something ^ 0" returns "fromInteger 1", which unfortunately

         -- in our case is not our multiplicative identity (the identity matrix) but just a 1x1 matrix of 1

fib n = last $ head $ unMat $ (Mat [[1,1],[1,0]]) ^ n</lang>

So, for example, the hundred-thousandth Fibonacci number starts with the digits

*Main> take 10 $ show $ fib (10^5)
"2597406934"

Hope

Recursive

Tail-recursive

<lang hope> dec fib : num -> num; --- fib n <= l (1, 0, n)

   whererec l == \(a,b,succ c) => if c<1 then a else l((a+b),a,c)
                 |(a,b,0) => 0;

</lang>

With lazy lists

This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers: <lang hope> dec fibs : list num; --- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs); </lang> The nth Fibonacci number is then just fibs @ n.

IDL

Recursive

<lang idl>function fib,n

  if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)

end</lang>

Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo.

Iterative

<lang idl>function fib,n

 psum = (csum = 1uL)
 if n lt 3 then return,csum
 for i = 3,n do begin
   nsum = psum + csum
   psum = csum
   csum = nsum
 endfor
 return,nsum

end</lang>

Execution time O(n). Limited by size of uLong to fib(49)

Analytic

<lang idl>function fib,n

 q=1/( p=(1+sqrt(5))/2 ) 
 return,round((p^n+q^n)/sqrt(5))

end</lang>

Execution time O(1), only limited by the range of LongInts to fib(48).

J

The Fibonacci Sequence essay on the J Wiki presents a number of different ways of obtaining the nth Fibonacci number. Here is one: <lang j> fibN=: (-&2 +&$: -&1)^:(1&<) M.</lang> Examples: <lang j> fibN 12 144

  fibN"0  >:i.30

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</lang>

Java

Iterative

<lang java>public static long itFibN(int n){

       if(n < 2)return n;
       long ans = 0;
       long n1 = 0;
       long n2 = 1;
       for(n--;n > 0;n--){
               ans = n1 + n2;
               n1 = n2;
               n2 = ans;
       }
       return ans;

}</lang>

Recursive

<lang java>public static long recFibN(int n){

       if(n < 2) return n;
       return recFibN(n-1) + recFibN(n-2);

}</lang>

Analytic

This method works up to the 92^nd Fibonacci number. After that, it goes out of range. <lang java>public static long anFibN(long n){ double p= (1 + Math.sqrt(5)) / 2; double q= 1 / p; return (long)((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5)); }</lang>

Tail-recursive

<lang java>public static long fibTailRec(int n) {

   return fibInner(0, 1, n);

}

private static long fibInner(long a, long b, int n) {

   if (n < 1) {
       return a;
   } else if (n == 1) {
       return b;
   } else {
       return fibInner(b, a + b, n - 1);
   }

}</lang>

JavaScript

Recursive

One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion: <lang javascript>function fib(n) {

 return function(n,a,b) {
   return n>0 ? arguments.callee(n-1,b,a+b) : a;
 }(n,0,1);

}</lang>

Iterative

<lang javascript>function fib(n) {

 var a=0, b=1, t;
 while (n-- > 0) {
   t = a;
   a = b;
   b += t;
 }
 return a;

} for (var i=0; i<10; ++i) alert(fib(i));</lang>

Joy

Recursive

<lang joy>DEFINE fib == [small]

             []
             [pred dup pred]
             [+]
             binrec .</lang>

Iterative

<lang joy> DEFINE f == [1 0] dip [swap [+] unary] times popd . </lang>

Lisaac

<lang Lisaac>- fib(n : UINTEGER_32) : UINTEGER_64 <- (

 + result : UINTEGER_64;
 (n < 2).if {
   result := n;
 } else {
   result := fib(n - 1) + fib(n - 2);
 };
 result

);</lang>

Logo

<lang logo>to fib :n [:a 0] [:b 1]

 if :n < 1 [output :a]
 output (fib :n-1 :b :a+:b)

end</lang>

Lua

<lang lua> --calculates the nth fibonacci number. Breaks for negative or non-integer n. function fibs(n)

 return n < 2 and n or fibs(n - 1) + fibs(n - 2)

end

--more pedantic version, returns 0 for non-integer n function pfibs(n)

 if n ~= math.floor(n) then return 0
 elseif n < 0 then return pfibs(n + 2) - pfibs(n + 1)
 elseif n < 2 then return n
 else return pfibs(n - 1) + pfibs(n - 2)
 end

end

--tail-recursive function tfibs(i)

 return (function a(n, u, s) return a(n-1,u+s,u) end)(i,1,0)

end

--table-recursive fib_n = setmetatable({1, 1}, {__index = function(z,n) return z[n-1] + z[n-2] end}) </lang>

M4

<lang m4>define(`fibo',`ifelse(0,$1,0,`ifelse(1,$1,1, `eval(fibo(decr($1)) + fibo(decr(decr($1))))')')')dnl define(`loop',`ifelse($1,$2,,`$3($1) loop(incr($1),$2,`$3')')')dnl loop(0,15,`fibo')</lang>

Mathematica

Mathematica already has a built-in function Fibonacci, but a simple recursive implementation would be

<lang mathematica>fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n - 1] + fib[n - 2]</lang>

An optimization is to cache the values already calculated:

<lang mathematica>fib[0] = 0 fib[1] = 1 fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]</lang>

MAXScript

Iterative

<lang maxscript>fn fibIter n = (

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

)</lang>

Recursive

<lang maxscript>fn fibRec n = (

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

)</lang>

Metafont

<lang metafont>vardef fibo(expr n) = if n=0: 0 elseif n=1: 1 else:

 fibo(n-1) + fibo(n-2)

fi enddef;

for i=0 upto 10: show fibo(i); endfor end</lang>

Modula-3

Recursive

<lang modula3>PROCEDURE Fib(n: INTEGER): INTEGER =

 BEGIN
   IF n < 2 THEN
     RETURN n;
   ELSE
     RETURN Fib(n-1) + Fib(n-2);
   END;
 END Fib;</lang>

Nimrod

Analytic

<lang nimrod>proc Fibonacci(n: int): int64 =

 var fn = float64(n)
 var p: float64 = (1.0 + sqrt(5.0)) / 2.0
 var q: float64 = 1.0 / p
 return int64((pow(p, fn) + pow(q, fn)) / sqrt(5.0))</lang>

Iterative

<lang nimrod>proc Fibonacci(n: int): int64 =

 var first: int64 = 0
 var second: int64 = 1
 var t: int64 = 0
 while n > 1:
   t = first + second
   first = second
   second = t
   dec(n)
 result = second</lang>

Recursive

<lang nimrod>proc Fibonacci(n: int): int64 =

 if n <= 2:
   result = 1
 else:
   result = Fibonacci(n - 1) + Fibonacci(n - 2)</lang>

Tail-recursive

<lang nimrod>proc Fibonacci(n: int, current: int64, next: int64): int64 =

 if n == 0:
   result = current
 else:
   result = Fibonacci(n - 1, next, current + next)

proc Fibonacci(n: int): int64 =

 result = Fibonacci(n, 0, 1)</lang>

OCaml

Iterative

<lang ocaml>let fib_iter n =

 if n < 2 then
   n
 else let fib_prev = ref 1
 and fib = ref 1 in
   for num = 2 to n - 1 do
     let temp = !fib in
       fib := !fib + !fib_prev;
       fib_prev := temp
   done;
   !fib</lang>

Recursive

<lang ocaml>let rec fib_rec n =

 if n < 2 then
   n
 else
   fib_rec (n - 1) + fib_rec (n - 2)</lang>

The previous way is the naive form, because for most n the fib_rec is called twice, and it is not tail recursive because it adds the result of two function calls. The next version resolves these problems:

<lang ocaml>let fib n =

 let rec fib_aux (n, a, b) =
   match (n, a, b) with
   | (0, a, b) -> a
   | _ -> fib_aux (n-1, a+b, a)
 in
 fib_aux (n, 0, 1)</lang>

Arbitrary Precision

Using OCaml's Num module.

<lang ocaml>open Num

let fib n =

 let rec fib_aux f0 f1 count =
   match count with
   | 0 -> f0
   | 1 -> f1
   | _ -> fib_aux f1 (f1 +/ f0) (count - 1)
 in
 fib_aux (num_of_int 0) (num_of_int 1) n</lang>

compile with:

ocamlopt nums.cmxa -o fib fib.ml

Octave

Recursive <lang octave>% recursive function fibo = recfibo(n)

 if ( n < 2 )
   fibo = n;
 else
   fibo = recfibo(n-1) + recfibo(n-2);
 endif

endfunction</lang>

Iterative <lang octave>% iterative function fibo = iterfibo(n)

 if ( n < 2 )
   fibo = n;
 else
   f = zeros(2,1);
   f(1) = 0; 
   f(2) = 1;
   for i = 2 : n
     t = f(2);
     f(2) = f(1) + f(2);
     f(1) = t;
   endfor
   fibo = f(2);
 endif

endfunction</lang>

Testing <lang octave>% testing for i = 0 : 20

 printf("%d %d\n", iterfibo(i), recfibo(i));

endfor</lang>

Oz

<lang oz>fun{FibI N} %% Iterative using Cell

 Temp = {NewCell 0}
 A = {NewCell 0}
 B = {NewCell 1}

in

 for I in 1..N do
   Temp := @A + @B
   A := @B
   B := @Temp
 end
 @A          %% return result

end

fun{Fibi N} %% Iterative(or Recursive?) by arguments swapping

 fun{FibIter N A B}
   if N == 0 then B
   else {FibIter N-1 A+B A} end
 end

in

 if N < 2 then N
 else {FibIter N 1 0} end

end

fun{FibR N} %% Simple Recursive

 if N < 2 then N
 else {FibR N-1} + {FibR N-2} end

end</lang>

Pascal

Recursive

<lang pascal>function fib(n: integer): integer;

begin
 if (n = 0) or (n = 1)
  then
   fib := n
  else
   fib := fib(n-1) + fib(n-2)
end;</lang>

Iterative

<lang pascal>function fib(n: integer): integer;

var
 f0, f1, fm1, k: integer;
begin
 f0 := 0;
 fm1 := 1;
 for k := 1 to n do
  begin
   f1:= fm1 + f0;
   fm1 := f0;
   f0 := f1
  end;
 fib := f0
end;</lang>

Perl

Iterative

<lang perl>sub fibIter {

   my $n = shift;
   if ($n < 2) {
       return $n;
   }
   my $fibPrev = 1;
   my $fib = 1;
   for (2..$n-1) {
       ($fibPrev, $fib) = ($fib, $fib + $fibPrev);
   }
   return $fib;

}</lang>

Recursive

<lang perl>sub fibRec {

   my $n = shift;
   return $n <= 2 ? 1 : fibRec($n-1) + fibRec($n-2);

}</lang>

Perl 6

Works with: Rakudo version #21 "Seattle"

Iterative

<lang perl6>sub fib (Int $n --> Int) {

   $n > 2 or return 1;
   my ($prev, $this) = 1, 1;
   $prev, $this = $this, $this + $prev for 2 ..^ $n;
   return $this;

}</lang>

Recursive

<lang perl6>multi fib (Int $n where { $n < 3 }) { 1 } multi fib (Int $n) { fib($n - 1) + fib($n - 2) }</lang>

Analytic

<lang perl6>sub fib (Int $n --> Int) {

   constant φ1 = 1 / do constant φ = (1 + sqrt 5)/2;
   constant invsqrt5 = 1 / sqrt 5;

   floor invsqrt5 * (φ**$n + φ1**$n);

}</lang>

PHP

Iterative

<lang php>function fibIter($n) {

   if ($n < 2) {
       return $n;
   }
   $fibPrev = 0;
   $fib = 1;
   foreach (range(1, $n-1) as $i) {
       list($fibPrev, $fib) = array($fib, $fib + $fibPrev);
   }
   return $fib;

}</lang>

Recursive

<lang php>function fibRec($n) {

   return $n < 2 ? $n : fibRec($n-1) + fibRec($n-2);

}</lang>

PicoLisp

<lang PicoLisp>(de fibo (N)

  (cache '*Fibo (format N)            # Use a cache to accelerate
     (if (> 2 N)
        N
        (+ (fibo (dec N)) (fibo (- N 2))) ) ) )</lang>

Pike

Ported from the Ruby example below ;)

<lang pike>int fibRec(int number){

  if(number <= -2){
     return pow(-1,(number+1)) * fibRec(abs(number));
  } else if(number <= 1){
     return abs(number);
  } else {
     return fibRec(number-1) + fibRec(number-2);
  }

}</lang>

PL/I

<lang PL/I> /* Form the first n+2 Fibonacci numbers. */ get list (n); f1, f2 = 1; put skip list (f1); put skip list (f2); do i = 1 to n;

  f3 = f1 + f2;
  put skip list (f3);
  f1 = f2;
  f2 = f3;

end; </lang>

Pop11

<lang pop11>define fib(x); lvars a , b;

   1 -> a;
   1 -> b;
   repeat x - 1 times
        (a + b, b) -> (b, a);
   endrepeat;
   a;

enddefine;</lang>

PostScript

Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:

<lang postscript>%!PS

% We want the 'n'th fibonacci number /n 13 def

% Prepare output canvas: /Helvetica findfont 20 scalefont setfont 100 100 moveto

%define the function recursively: /fib { dup

      3 lt
        { pop 1 }
        { dup 1 sub fib exch 2 sub fib add }
      ifelse
   } def
   
   (Fib\() show n (....) cvs show (\)=) show n fib (.....) cvs show

showpage</lang>

PowerShell

Iterative

<lang powershell>function fib ($n) {

   if ($n -eq 0) { return 0 }
   if ($n -eq 1) { return 1 }

   $m = 1
   if ($n -lt 0) {
       if ($n % 2 -eq -1) {
           $m = 1
       } else {
           $m = -1
       }

       $n = -$n
   }

   $a = 0
   $b = 1

   for ($i = 1; $i -lt $n; $i++) {
       $c = $a + $b
       $a = $b
       $b = $c
   }
   
   return $m * $b

}</lang>

Recursive

<lang powershell>function fib($n) {

   switch ($n) {
       0            { return 0 }
       1            { return 1 }
       { $_ -lt 0 } { return [Math]::Pow(-1, -$n + 1) * (fib (-$n)) }
       default      { return (fib ($n - 1)) + (fib ($n - 2)) }
   }

}</lang>

Prolog

Works with: SWI Prolog

Works with: GNU Prolog

Pure

Tail Recursive

<lang pure>fib n = loop 0 1 n with

 loop a b n = if n==0 then a else loop b (a+b) (n-1);

end;</lang>

Python

Iterative

<lang python>def fibIter(n):

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

Recursive

<lang python>def fibRec(n):

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

Generative

<lang python>def fibGen():

   f0, f1 = 0, 1
   while True:
       yield f0
       f0, f1 = f1, f0+f1</lang>

Example use

<lang python>>>> fg = fibGen() >>> for x in range(9):

   print fg.next()

0 1 1 2 3 5 8 13 21 >>></lang>

R

<lang R>recfibo <- function(n) {

 if ( n < 2 ) n
 else recfibo(n-1) + recfibo(n-2)

}

iterfibo <- function(n) {

 if ( n < 2 )
   n
 else {
   f <- c(0, 1)
   for (i in 2:n) {
     t <- f[2]
     f[2] <- sum(f)
     f[1] <- t
   }
   f[2]
 }

}

fib <- function(n)

       if(n <= 2){if(n>=0) 1 else 0 } else Recall(n-1) + Recall(n-2)</lang>

<lang R>print.table(lapply(0:20, recfibo)) print.table(lapply(0:20, iterfibo))</lang>

Ruby

Iterative

<lang ruby>def fibIter(n)

 return 0 if n == 0
 fibPrev, fib = 1, 1
 (n.abs - 2).times { fibPrev, fib = fib, fib + fibPrev }
 fib * (n<0 ? (-1)**(n+1) : 1)

end</lang>

Recursive

<lang ruby>def fibRec(n)

 if n <= -2
   (-1)**(n+1) * fibRec(n.abs)
 elsif n <= 1
   n.abs
 else
   fibRec(n-1) + fibRec(n-2)
 end

end</lang>

Matrix

<lang ruby>require 'matrix'

To understand why this matrix is useful for Fibonacci numbers, remember
that the definition of Matrix.**2 for any Matrix[[a, b], [c, d]] is
is [[a*a + b*c, a*b + b*d], [c*a + d*b, c*b + d*d]]. In other words, the
lower right element is computing F(k - 2) + F(k - 1) every time M is multiplied
by itself (it is perhaps easier to understand this by computing M**2, 3, etc, and
watching the result march up the sequence of Fibonacci numbers).

M = Matrix[[0, 1], [1,1]]

Matrix exponentiation algorithm to compute Fibonacci numbers.
Let M be Matrix [[0, 1], [1, 1]]. Then, the lower right element of M**k is
F(k + 1). In other words, the lower right element of M is F(2) which is 1, and the
lower right element of M**2 is F(3) which is 2, and the lower right element
of M**3 is F(4) which is 3, etc.
This is a good way to compute F(n) because the Ruby implementation of Matrix.**(n)
uses O(log n) rather than O(n) matrix multiplications. It works by squaring squares
((m**2)**2)... as far as possible
and then multiplying that by by M**(the remaining number of times). E.g., to compute
M**19, compute partial = ((M**2)**2) = M**16, and then compute partial*(M**3) = M**19.
That's only 5 matrix multiplications of M to compute M*19.

def self.fibMatrix(n)

 return 0 if n <= 0 # F(0)
 return 1 if n == 1 # F(1)
 # To get F(n >= 2), compute M**(n - 1) and extract the lower right element.
 return CS::lower_right(M**(n - 1))

end

Matrix utility to return
the lower, right-hand element of a given matrix.

def self.lower_right matrix

 return nil if matrix.row_size == 0
 return matrix[matrix.row_size - 1, matrix.column_size - 1]

end</lang>

Generative

<lang ruby>require 'generator'

def fibGen

   Generator.new do |g|
       f0, f1 = 0, 1
       loop do
           g.yield f0
           f0, f1 = f1, f0+f1
       end
   end

end</lang>

Usage:

irb(main):012:0> fg = fibGen
=> #<Generator:0xb7d3ead4 @cont_next=nil, @queue=[0], @cont_endp=nil, @index=0, @block=#<Proc:0xb7d41680@(irb):4>, @cont_yield=#<Continuation:0xb7d3e8a4>>
irb(main):013:0> 9.times { puts fg.next }
0
1
1
2
3
5
8
13
21
=> 9

Works with: Ruby version 1.9

"Fibers are primitives for implementing light weight cooperative concurrency in Ruby. Basically they are a means of creating code blocks that can be paused and resumed, much like threads. The main difference is that they are never preempted and that the scheduling must be done by the programmer and not the VM." [1]

<lang ruby>fib = Fiber.new do

 a,b = 0,1
 loop do
   Fiber.yield a
   a,b = b,a+b
 end

end 9.times {puts fib.resume}</lang>

Scala

Recursive

<lang scala>def fib(i:Int):Int = i match{

   case 1 => 0
   case 2 => 1
   case _ => fib(i-1) + fib(i-2)

}</lang>

Lazy sequence

<lang scala>//syntactic sugar for Stream.cons, this is unnecessary but makes the definition prettier //Stream.cons(head,stream) becomes head::stream //I think 2.8 will have #:: class PrettyStream[A](str: =>Stream[A]) {

   def ::(hd: A) = Stream.cons(hd, str)

} implicit def streamToPrettyStream[A](str: =>Stream[A]) = new PrettyStream(str)

def fib: Stream[Int] = 0 :: 1 :: fib.zip(fib.tail).map{case (a,b) => a + b}</lang>

Tail recursive

<lang scala>def fib(i:Int):Int = {

   def fib2(i:Int, a:Int, b:Int):Int = i match{
       case 1 => b
       case _ => fib2(i-1, b, a+b)
   }
   fib2(i,1,0)

}</lang>

Scheme

Iterative

<lang scheme>(define (fib-iter n)

 (do ((num 2 (+ num 1))
      (fib-prev 1 fib)
      (fib 1 (+ fib fib-prev)))
     ((>= num n) fib)))</lang>

Recursive

<lang scheme>(define (fib-rec n)

 (if (< n 2)
     n
     (+ (fib-rec (- n 1))
        (fib-rec (- n 2)))))</lang>

This version is tail recursive: <lang scheme>(define (fib n)

 (letrec ((fib_aux (lambda (n a b)
   (if (= n 0)
       a
       (fib_aux (- n 1) b (+ a b))))))
 (fib_aux n 0 1)))</lang>

Dijkstra Algorithm

<lang scheme>;;; Fibonacci numbers using Edsger Dijkstra's algorithm

http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF

(define (fib n)

 (define (fib-aux a b p q count)
   (cond ((= count 0) b)
         ((even? count)
          (fib-aux a
                   b
                   (+ (* p p) (* q q))
                   (+ (* q q) (* 2 p q))
                   (/ count 2)))
         (else
          (fib-aux (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (- count 1)))))
 (fib-aux 1 0 0 1 n))</lang>

Seed7

Recursive

<lang seed7>const func integer: fib (in integer: number) is func

 result
   var integer: result is 1;
 begin
   if number > 2 then
     result := fib(pred(number)) + fib(number - 2);
   elsif number = 0 then
     result := 0;
   end if;
 end func;</lang>

Original source: [2]

Iterative

This funtion uses a bigInteger result:

<lang seed7>const func bigInteger: fib (in integer: number) is func

 result
   var bigInteger: result is 1_;
 local
   var integer: i is 0;
   var bigInteger: a is 0_;
   var bigInteger: c is 0_;
 begin
   for i range 1 to pred(number) do
     c := a;
     a := result;
     result +:= c;
   end for;
 end func;</lang>

Original source: [3]

Slate

<lang slate>n@(Integer traits) fib [

 n <= 0 ifTrue: [^ 0].
 n = 1 ifTrue: [^ 1].
 (n - 1) fib + (n - 2) fib

].

slate[15]> 10 fib = 55. True</lang>

Smalltalk

<lang smalltalk>|fibo| fibo := [ :i |

  |ac t|
  ac := Array new: 2.
  ac at: 1 put: 0 ; at: 2 put: 1.
  ( i < 2 )
    ifTrue: [ ac at: (i+1) ]
    ifFalse: [
       2 to: i do: [ :l |
         t := (ac at: 2).
         ac at: 2 put: ( (ac at: 1) + (ac at: 2) ).
         ac at: 1 put: t
       ].
       ac at: 2.
    ]

].

0 to: 10 do: [ :i |

 (fibo value: i) displayNl

]</lang>

SNUSP

This is modular SNUSP (which introduces @ and # for threading).

Iterative

<lang snusp> @!\+++++++++# /<<+>+>-\ fib\==>>+<<?!/>!\ ?/\

 #<</?\!>/@>\?-<<</@>/@>/>+<-\ 
    \-/  \       !\ !\ !\   ?/#</lang>

Recursive

<lang snusp> /========\ />>+<<-\ />+<-\ fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#

     |  #+==/     fib(n-2)|+fib(n-1)|
     \=====recursion======/!========/</lang>

Standard ML

Recursion

This version is tail recursive. <lang sml>fun fib n =

let

fun fib' (0,a,b) = a | fib' (n,a,b) = fib' (n-1,a+b,a)

in

fib' (n,0,1)

   end</lang>

Tcl

Simple Version

These simple versions do not handle negative numbers -- they will return N for N < 2

Iterative

Translation of: Perl

<lang tcl>proc fibiter n {

   if {$n < 2} {return $n}
   set prev 1
   set fib 1
   for {set i 2} {$i < $n} {incr i} {
       lassign [list $fib [incr fib $prev]] prev fib
   }
   return $fib

}</lang>

Recursive

<lang tcl>proc fib {n} {

   if {$n < 2} then {expr {$n}} else {expr {[fib [expr {$n-1}]]+[fib [expr {$n-2}]]} }

}</lang>

The following

Works with: Tcl version 8.5

: defining a procedure in the ::tcl::mathfunc namespace allows that proc to be used as a function in expr expressions.

<lang tcl>proc tcl::mathfunc::fib {n} {

   if { $n < 2 } {
       return $n
   } else {
       return [expr {fib($n-1) + fib($n-2)}]
   }

}

or, more tersely

proc tcl::mathfunc::fib {n} {expr {$n<2 ? $n : fib($n-1) + fib($n-2)}}</lang>

E.g.:

<lang tcl>expr {fib(7)} ;# ==> 13

namespace path tcl::mathfunc #; or, interp alias {} fib {} tcl::mathfunc::fib fib 7 ;# ==> 13</lang>

Tail-Recursive

In Tcl 8.6 a tailcall function is available to permit writing tail-recursive functions in Tcl. This makes deeply recursive functions practical. The availability of large integers also means no truncation of larger numbers. <lang tcl>proc fib-tailrec {n} {

   proc fib:inner {a b n} {
       if {$n < 1} {
           return $a
       } elseif {$n == 1} {
           return $b
       } else {
           tailcall fib:inner $b [expr {$a + $b}] [expr {$n - 1}]
       }
   }
   return [fib:inner 0 1 $n]

}</lang>

% fib-tailrec 100
354224848179261915075

Handling Negative Numbers

Iterative

<lang tcl>proc fibiter n {

   if {$n < 0} {
       set n [expr {abs($n)}]
       set sign [expr {-1**($n+1)}]
   } else {
       set sign 1
   }
   if {$n < 2} {return $n}
   set prev 1
   set fib 1
   for {set i 2} {$i < $n} {incr i} {
       lassign [list $fib [incr fib $prev]] prev fib
   }
   return [expr {$sign * $fib}]

} fibiter -5 ;# ==> 5 fibiter -6 ;# ==> -8</lang>

Recursive

<lang tcl>proc tcl::mathfunc::fib {n} {expr {$n<-1 ? -1**($n+1) * fib(abs($n)) : $n<2 ? $n : fib($n-1) + fib($n-2)}} expr {fib(-5)} ;# ==> 5 expr {fib(-6)} ;# ==> -8</lang>

For the Mathematically Inclined

This works up to ${\displaystyle fib(70)}$ , after which the limited precision of IEEE double precision floating point arithmetic starts to show.

Works with: Tcl version 8.5

<lang tcl>proc fib n {expr {round((.5 + .5*sqrt(5)) ** $n / sqrt(5))}}</lang>

TI-89 BASIC

Unoptimized recursive implementation.

<lang ti89b>fib(n) Func

 If n = 0 or n = 1 Then
   Return n
 ElseIf n ≥ 2 Then
   Return fib(n-1) + fib(n-2)
 EndIf

EndFunc</lang>

UnixPipes

Uses fib and last as file buffers for computation. could have made fib as a fifo and changed tail -f to cat fib but it is not line buffered.

<lang bash>echo 1 |tee last fib ; tail -f fib | while read x do

  cat last | tee -a fib | xargs -n 1 expr $x + |tee last

done</lang>

UNIX Shell

Works with: bash version 3

<lang bash>#!/bin/bash

a=0 b=1 max=$1

for (( n=1; "$n" <= "$max"; $((n++)) )) do

 a=$(($a + $b))
 echo "F($n): $a"
 b=$(($a - $b))

done</lang>

Ursala

All three methods are shown here, and all have unlimited precision. <lang Ursala>#import std

import nat

iterative_fib = ~&/(0,1); ~&r->ll ^|\predecessor ^/~&r sum

recursive_fib = {0,1}^?<a/~&a sum^|W/~& predecessor^~/~& predecessor

analytical_fib =

%np+ -+

  mp..round; ..mp2str; sep`+; ^CNC/~&hh take^\~&htt %np@t,
  (mp..div^|\~& mp..sub+ ~~ @rlX mp..pow_ui)^lrlPGrrPX/~& -+
     ^\~& ^(~&,mp..sub/1.E0)+ mp..div\2.E0+ mp..add/1.E0,
     mp..sqrt+ ..grow/5.E0+-+-</lang>

The analytical method uses arbitrary precision floating point arithmetic from the mpfr library and then converts the result to a natural number. Sufficient precision for an exact result is always chosen based on the argument. This test program computes the first twenty numbers Fibonacci numbers by all three methods. <lang Ursala>#cast %nLL

examples = <.iterative_fib,recursive_fib,analytical_fib>* iota20</lang> output:

<
   <0,0,0>,
   <1,1,1>,
   <1,1,1>,
   <2,2,2>,
   <3,3,3>,
   <5,5,5>,
   <8,8,8>,
   <13,13,13>,
   <21,21,21>,
   <34,34,34>,
   <55,55,55>,
   <89,89,89>,
   <144,144,144>,
   <233,233,233>,
   <377,377,377>,
   <610,610,610>,
   <987,987,987>,
   <1597,1597,1597>,
   <2584,2584,2584>,
   <4181,4181,4181>>

V

Generate n'th fib by using binary recursion

<lang v>[fib

  [small?] []
    [pred dup pred]
    [+]
  binrec].</lang>

VBScript

Non-recursive, object oriented, generator

Defines a generator class, with a default Get property. Uses Currency for larger-than-Long values. Tests for overflow and switches to Double. Overflow information also available from class.

Class Definition:

<lang vb>class generator dim t1 dim t2 dim tn dim cur_overflow

Private Sub Class_Initialize cur_overflow = false t1 = ccur(0) t2 = ccur(1) tn = ccur(t1 + t2) end sub

public default property get generated on error resume next

generated = ccur(tn) if err.number <> 0 then generated = cdbl(tn) cur_overflow = true end if t1 = ccur(t2) if err.number <> 0 then t1 = cdbl(t2) cur_overflow = true end if t2 = ccur(tn) if err.number <> 0 then t2 = cdbl(tn) cur_overflow = true end if tn = ccur(t1+ t2) if err.number <> 0 then tn = cdbl(t1) + cdbl(t2) cur_overflow = true end if on error goto 0 end property

public property get overflow overflow = cur_overflow end property

end class </lang>

Invocation:

<lang vb>dim fib set fib = new generator dim i for i = 1 to 100 wscript.stdout.write " " & fib if fib.overflow then wscript.echo exit for end if next </lang>

Output:

Vedit macro language

Iterative

Calculate fibonacci(#1). Negative values return 0. <lang vedit>:FIBONACCI:

11 = 0
12 = 1

Repeat(#1) {

   #10 = #11 + #12
   #11 = #12
   #12 = #10

} Return(#11)</lang>

Visual Basic .NET

Platform: .NET

Works with: Visual Basic .NET version 9.0+

<lang vbnet>Function Fib(ByVal n As Integer) As Decimal

   Dim fib0, fib1, sum As Decimal
   Dim i As Integer
   fib0 = 0
   fib1 = 1
   For i = 1 To n
       sum = fib0 + fib1
       fib0 = fib1
       fib1 = sum
   Next
   Fib = fib0

End Function</lang>

XQuery

<lang xquery>declare function local:fib($n as xs:integer) as xs:integer {

 if($n < 2)
 then $n
 else local:fib($n - 1) + local:fib($n - 2)

};</lang>