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 F_n of natural numbers defined recursively:

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-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).

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.

Cf.

• Fibonacci n-step number sequences‎

References

• Wikipedia, Fibonacci number
• Wikipedia, Lucas number
• MathWorld, Fibonacci Number
• Some identities for r-Fibonacci numbers
• OEIS Fibonacci numbers
• OEIS Lucas numbers

0815

 
%<:0D:>~$<:01:~%>=<:a94fad42221f2702:>~>
}:_s:{x{={~$x+%{=>~>x~-x<:0D:~>~>~^:_s:?
 

ACL2

Fast, tail recursive solution:

(defun fast-fib-r (n a b)
   (if (or (zp n) (zp (1- n)))
       b
       (fast-fib-r (1- n) b (+ a b))))
 
(defun fast-fib (n)
   (fast-fib-r n 1 1))
 
(defun first-fibs-r (n i)
   (declare (xargs :measure (nfix (- n i))))
   (if (zp (- n i))
       nil
       (cons (fast-fib i)
             (first-fibs-r n (1+ i)))))
 
(defun first-fibs (n)
   (first-fibs-r n 0))

Output:

>(first-fibs 20)
(1 1 2 3 5 8 13 21 34 55 89
   144 233 377 610 987 1597 2584 4181 6765)

ActionScript

public function fib(n:uint):uint
{
    if (n < 2)
        return n;
 
    return fib(n - 1) + fib(n - 2);
}

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

Ada

Recursive

with Ada.Text_IO, Ada.Command_Line;
 
procedure Fib is
 
   X: Positive := Positive'Value(Ada.Command_Line.Argument(1));
 
   function Fib(P: Positive) return Positive is
   begin
      if P <= 2 then
         return 1;
      else
         return Fib(P-1) + Fib(P-2);
      end if;
   end Fib;
 
begin
   Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
   Ada.Text_IO.Put_Line(Integer'Image(Fib(X)));
end Fib;

Iterative, build-in integers

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;

Sample output:

 0
 1
 1
 2
 3
 5
 8
 13
 21
 34
 55

Iterative, long integers

Using the big integer implementation from a cryptographic library [1].

with Ada.Text_IO, Ada.Command_Line, Crypto.Types.Big_Numbers;
 
procedure Fibonacci is
 
   X: Positive := Positive'Value(Ada.Command_Line.Argument(1));
 
   Bit_Length: Positive := 1 + (696 * X) / 1000;
   -- that number of bits is sufficient to store the full result.
 
   package LN is new Crypto.Types.Big_Numbers
     (Bit_Length + (32 - Bit_Length mod 32));
     -- the actual number of bits has to be a multiple of 32
   use LN;
 
   function Fib(P: Positive) return Big_Unsigned is
      Previous: Big_Unsigned := Big_Unsigned_Zero;
      Result:   Big_Unsigned := Big_Unsigned_One;
      Tmp:      Big_Unsigned;
   begin
      -- Result = 1 = Fibonacci(1)
      for I in 1 .. P-1 loop
         Tmp := Result;
         Result := Previous + Result;
         Previous := Tmp;
         -- Result = Fibonacci(I+1))
      end loop;
      return Result;
   end Fib;
 
begin
   Ada.Text_IO.Put("Fibonacci(" & Integer'Image(X) & " ) = ");
   Ada.Text_IO.Put_Line(LN.Utils.To_String(Fib(X)));
end Fibonacci;

Output:

> ./fibonacci 777
Fibonacci( 777 ) = 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082

Aime

integer
fibs(integer n)
{
    integer w;
 
    if (n == 0) {
        w = 0;
    } elif (n == 1) {
        w = 1;
    } else {
        integer a, b, i;
 
        i = 1;
        a = 0;
        b = 1;
        while (i < n) {
            w = a + b;
            a = b;
            b = w;
            i += 1;
        }
    }
 
    return w;
}
 

ALGOL 68

Analytic

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

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

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;
  ROUND( (p**n + q**n) / sqrt 5 )
);
 
FOR i FROM 1 TO 30 WHILE
  print(whole(analytic fibonacci(i),0));
# WHILE # i /= 30 DO
  print(", ")
OD;
print(new line)

Output:

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

Iterative

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

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

PROC iterative fibonacci = (INT n)INT: 
  CASE n+1 IN
    0, 1, 1, 2, 3, 5
  OUT
    INT even:=3, odd:=5;
    FOR i FROM odd+1 TO n DO
      (ODD i|odd|even) := odd + even
    OD;
    (ODD n|odd|even)
  ESAC;
 
FOR i FROM 0 TO 30 WHILE
  print(whole(iterative fibonacci(i),0));
# WHILE # i /= 30 DO
  print(", ")
OD;
print(new line)

Output:

0, 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

Recursive

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

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

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

Generative

Translation of: Python

- note: This specimen retains the original Python coding style.

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

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

MODE YIELDINT = PROC(INT)VOID;
 
PROC gen fibonacci = (INT n, YIELDINT yield)VOID: (
  INT even:=0, odd:=1;
  yield(even);
  yield(odd);
  FOR i FROM odd+1 TO n DO
    yield( (ODD i|odd|even) := odd + even )
  OD
);
 
main:(
  # FOR INT n IN # gen fibonacci(30, # ) DO ( #
  ##   (INT n)VOID:(
        print((" ",whole(n,0)))
  # OD # ));
    print(new line)
)

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

Array (Table) Lookup

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

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

This uses a pre-generated list, requiring much less run-time processor usage, but assumes that INT is only 31 bits wide.

[]INT const fibonacci = []INT( -1836311903, 1134903170,
  -701408733, 433494437, -267914296, 165580141, -102334155,
  63245986, -39088169, 24157817, -14930352, 9227465, -5702887,
  3524578, -2178309, 1346269, -832040, 514229, -317811, 196418,
  -121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181,
  -2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13,
  -8, 5, -3, 2, -1, 1, 0, 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,
  1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
  39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
  701408733, 1134903170, 1836311903
)[@-46];
 
PROC VOID value error := stop;
 
PROC lookup fibonacci = (INT i)INT: (
  IF LWB const fibonacci <= i AND i<= UPB const fibonacci THEN
    const fibonacci[i]
  ELSE
    value error; SKIP
  FI
);
 
FOR i FROM 0 TO 30 WHILE
  print(whole(lookup fibonacci(i),0));
# WHILE # i /= 30 DO
  print(", ")
OD;
print(new line)

Output:

0, 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

Alore

def fib(n as Int) as Int
   if n < 2
      return 1
   end
   return fib(n-1) + fib(n-2)
end

AutoHotkey

Search autohotkey.com: sequence

Iterative

Translation of: C

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
}

Recursive and iterative

Source: AutoHotkey forum by Laszlo

/*
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 
}

AutoIt

Iterative

#AutoIt Version: 3.2.10.0
$n0 = 0
$n1 = 1
$n = 10
MsgBox (0,"Iterative Fibonacci ", it_febo($n0,$n1,$n))
 
Func it_febo($n_0,$n_1,$N)
   $first = $n_0
   $second = $n_1
   $next = $first + $second
   $febo = 0
   For $i = 1 To $N-3
      $first = $second
      $second = $next
      $next = $first + $second
   Next
   if $n==0 Then
      $febo = 0
   ElseIf $n==1 Then
      $febo = $n_0
   ElseIf $n==2 Then
      $febo = $n_1
   Else
      $febo = $next
   EndIf
   Return $febo
EndFunc
 

Recursive

#AutoIt Version: 3.2.10.0
$n0 = 0
$n1 = 1
$n = 10
MsgBox (0,"Recursive Fibonacci ", rec_febo($n0,$n1,$n))
Func rec_febo($r_0,$r_1,$R)
   if  $R<3 Then
      if $R==2 Then
	 Return $r_1
      ElseIf $R==1 Then
	 Return $r_0
      ElseIf $R==0 Then
	 Return 0
      EndIf
      Return $R
   Else
      Return rec_febo($r_0,$r_1,$R-1) + rec_febo($r_0,$r_1,$R-2)
   EndIf
EndFunc
 

AWK

As in many examples, this one-liner contains the function as well as testing with input from stdin, output to stdout.

$ awk 'func fib(n){return(n<2?n:fib(n-1)+fib(n-2))}{print "fib("$1")="fib($1)}'
10
fib(10)=55

Babel

main: 
    { argv 0 th $d
    fib
    %d cr << }
 
fib!: 
    { dup zero?
        { dup one?
            { cp <- 2 - fib -> 1 - fib + }
            { zap 1 }
        if }
        { zap 1 }
    if }
 
zero?!: { 0 = }
 
one?!: { 1 = }

BASIC

Works with: QBasic

Works with: FreeBASIC

Iterative

FUNCTION itFib (n)
    n1 = 0
    n2 = 1
    FOR k = 1 TO ABS(n)
        sum = n1 + n2
        n1 = n2
        n2 = sum
    NEXT k
    IF n < 0 THEN
        itFib = n1 * ((-1) ^ ((-n) + 1))
    ELSE
        itFib = n1
    END IF
END FUNCTION

Next version calculates each value once, as needed, and stores the results in an array for later retreival (due to the use of REDIM PRESERVE, it requires QuickBASIC 4.5 or newer):

DECLARE FUNCTION fibonacci& (n AS INTEGER)
 
REDIM SHARED fibNum(1) AS LONG
 
fibNum(1) = 1
 
'*****sample inputs*****
PRINT fibonacci(0)      'no calculation needed
PRINT fibonacci(13)     'figure F(2)..F(13)
PRINT fibonacci(-42)    'figure F(14)..F(42)
PRINT fibonacci(47)     'error: too big
'*****sample inputs*****
 
FUNCTION fibonacci& (n AS INTEGER)
    DIM a AS INTEGER
    a = ABS(n)
    SELECT CASE a
        CASE 0 TO 46
            SHARED fibNum() AS LONG
            DIM u AS INTEGER, L0 AS INTEGER
            u = UBOUND(fibNum)
            IF a > u THEN
                REDIM PRESERVE fibNum(a) AS LONG
                FOR L0 = u + 1 TO a
                    fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
                NEXT
            END IF
            IF n < 0 THEN
                fibonacci = fibNum(a) * ((-1) ^ (a + 1))
            ELSE
                fibonacci = fibNum(n)
            END IF
        CASE ELSE
            'limited to signed 32-bit int (LONG)
            'F(47)=&hB11924E1
            ERROR 6 'overflow
    END SELECT
END FUNCTION

Outputs (unhandled error in final input prevents output):

 0
 233
-267914296

Recursive

This example can't handle n < 0.

FUNCTION recFib (n)
    IF (n < 2) THEN
	recFib = n
    ELSE
	recFib = recFib(n - 1) + recFib(n - 2)
    END IF
END FUNCTION

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

DATA -1836311903,1134903170,-701408733,433494437,-267914296,165580141,-102334155
DATA 63245986,-39088169,24157817,-14930352,9227465,-5702887,3524578,-2178309
DATA 1346269,-832040,514229,-317811,196418,-121393,75025,-46368,28657,-17711
DATA 10946,-6765,4181,-2584,1597,-987,610,-377,233,-144,89,-55,34,-21,13,-8,5,-3
DATA 2,-1,1,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 TO 46) AS LONG
 
FOR n = -46 TO 46
    READ fibNum(n)
NEXT
 
'*****sample inputs*****
FOR n = -46 TO 46
    PRINT fibNum(n),
NEXT
PRINT
'*****sample inputs*****

Batch File

Recursive version

::fibo.cmd
@echo off
if "%1" equ "" goto :eof
call :fib %1
echo %errorlevel%
goto :eof
 
:fib
setlocal enabledelayedexpansion
if %1 geq 2 goto :ge2 
exit /b %1
 
:ge2
set /a r1 = %1 - 1
set /a r2 = %1 - 2
call :fib !r1!
set r1=%errorlevel%
call :fib !r2!
set r2=%errorlevel%
set /a r0 = r1 + r2
exit /b !r0!

Output:

>for /L %i in (1,5,20) do fibo.cmd %i

>fibo.cmd 1
1

>fibo.cmd 6
8

>fibo.cmd 11
89

>fibo.cmd 16
987

BBC BASIC

      PRINT FNfibonacci_r(1),  FNfibonacci_i(1)
      PRINT FNfibonacci_r(13), FNfibonacci_i(13)
      PRINT FNfibonacci_r(26), FNfibonacci_i(26)
      END
 
      DEF FNfibonacci_r(N)
      IF N < 2 THEN = N
      = FNfibonacci_r(N-1) + FNfibonacci_r(N-2)
 
      DEF FNfibonacci_i(N)
      LOCAL F, I, P, T
      IF N < 2 THEN = N
      P = 1
      FOR I = 1 TO N
        T = F
        F += P
        P = T
      NEXT
      = F
 

Output:

         1         1
       233       233
    121393    121393

bc

iterative

#! /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

Befunge

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

Brainf***

Works with: Brainf*** version implementations with unbounded cell size

The first cell contains n (10), the second cell will contain fib(n) (55), and the third cell will contain fib(n-1) (34).

++++++++++
>>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]

The following generates n fibonacci numbers and prints them, though not in ascii. It does have a limit due to the cells usually being 1 byte in size.

+++++ +++++	#0 set to n
>> +		Init #2 to 1
<<
[
	-	#Decrement counter in #0
	>>.	Notice: This doesn't print it in ascii
		To look at results you can pipe into a file and look with a hex editor
 
		Copying sequence to save #2 in #4 using #5 as restore space
	>>[-]	Move to #4 and clear
	>[-]	Clear #5
	<<<	#2
	[	Move loop
		- >> + > + <<<	Subtract #2 and add #4 and #5
	]
	>>>
	[	Restore loop
		- <<< + >>>	Subtract from #5 and add to #2
	]
 
	<<<<	Back to #1
		Non destructive add sequence using #3 as restore value
	[	Loop to add
		- > + > + <<	Subtract #1 and add to value #2 and restore space #3
	]
	>>
	[	Loop to restore #1 from #3
		- << + >>	Subtract from restore space #3 and add in #1
	]
 
	<< [-]	Clear #1
	>>>
	[	Loop to move #4 to #1
		- <<< + >>>	Subtract from #4 and add to #1
	]
	<<<<	Back to #0
]

Bracmat

Recursive

fib=.!arg:<2|fib$(!arg+-2)+fib$(!arg+-1)

 fib$30
 832040

Iterative

(fib=
  last i this new
.   !arg:<2
  |   0:?last:?i
    & 1:?this
    &   whl
      ' ( !i+1:<!arg:?i
        & !last+!this:?new
        & !this:?last
        & !new:?this
        )
    & !this
)

 fib$777
 1081213530912648191985419587942084110095342850438593857649766278346130479286685742885693301250359913460718567974798268702550329302771992851392180275594318434818082

Brat

Recursive

fibonacci = { x |
        true? x < 2, x, { fibonacci(x - 1) + fibonacci(x - 2) }
}

Tail Recursive

fib_aux = { x, next, result |
        true? x == 0,
                result,
                { fib_aux x - 1, next + result, next }
}
 
fibonacci = { x |
  fib_aux x, 1, 0
}

Memoization

cache = hash.new
 
fibonacci = { x |
  true? cache.key?(x)
    { cache[x] }
    {true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}
}

Burlesque

 
{0 1}{^^++[+[-^^-]\/}30.*\[e!vv
 

C

Recursive

long long int fibb(long long int a, long long int b, int n) {
return (--n>0)?(fibb(b, a+b, n)):(a);
}

Iterative

long long int fibb(int n) {
	int fnow = 0, fnext = 1, tempf;
	while(--n>0){
		tempf = fnow + fnext;
		fnow = fnext;
		fnext = tempf;
		}
		return fnow;	
}

Analytic

#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) );
}

Generative

Translation of: Python

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

#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 *)&lambda; 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");
}

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.

#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;
}

Library: GMP

This version does not have an upper bound.

#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;
}

Version using transform:

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
 
unsigned int fibonacci(unsigned int n) {
  if (n == 0) return 0;
  std::vector<int> v(n+1);
  v[1] = 1;
  transform(v.begin(), v.end()-2, v.begin()+1, v.begin()+2, std::plus<int>());
  // "v" now contains the Fibonacci sequence from 0 up
  return v[n];
}

Far-fetched version using adjacent_difference:

#include <numeric>
#include <vector>
#include <functional>
#include <iostream>
 
unsigned int fibonacci(unsigned int n) {
  if (n == 0) return 0;
  std::vector<int> v(n, 1);
  adjacent_difference(v.begin(), v.end()-1, v.begin()+1, std::plus<int>());
  // "array" now contains the Fibonacci sequence from 1 up
  return v[n-1];
}
 

Version which computes at compile time with metaprogramming:

#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;
}

The following version is based on fast exponentiation:

#include <iostream>
 
inline void fibmul(int* f, int* g)
{
  int tmp = f[0]*g[0] + f[1]*g[1];
  f[1] = f[0]*g[1] + f[1]*(g[0] + g[1]);
  f[0] = tmp;
}
 
int fibonacci(int n)
{
  int f[] = { 1, 0 };
  int g[] = { 0, 1 };
  while (n > 0)
  {
    if (n & 1) // n odd
    {
      fibmul(f, g);
      --n;
    }
    else
    {
      fibmul(g, g);
      n >>= 1;
    }
  }
  return f[1];
}
 
int main()
{
  for (int i = 0; i < 20; ++i)
    std::cout << fibonacci(i) << " ";
  std::cout << std::endl;
}

Output:

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

Using Zeckendorf Numbers

The nth fibonacci is represented as Zeckendorf 1 followed by n-1 zeroes. Here I define a class N which defines the operations increment ++() and comparison <=(other N) for Zeckendorf Numbers.

 
// Use Zeckendorf numbers to display Fibonacci sequence.
// Nigel Galloway October 23rd., 2012
int main(void) {
  char NG[22] = {'1',0};
  int x = -1;
  N G;
  for (int fibs = 1; fibs <= 20; fibs++) {
   for (;G <= N(NG); ++G) x++;
   NG[fibs] = '0';
   NG[fibs+1] = 0;
   std::cout << x << " ";
  }
  std::cout << std::endl;
  return 0;
}
 

Output:

1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946

Using Standard Template Library

Possibly less "Far-fetched version".

 
// Use Standard Template Library to display Fibonacci sequence.
// Nigel Galloway March 30th., 2013
#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
   int x = 1, y = 1;
   generate_n(std::ostream_iterator<int>(std::cout, " "), 21, [&]{int n=x; x=y; y+=n; return n;});
   return 0;
}
 

Output:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946

C#

Recursive

 
public static ulong Fib(uint n) {
    return (n < 2)? n : Fib(n - 1) + Fib(n - 2);
}
 

Tail-Recursive

 
public static ulong Fib(uint n) {
    return Fib(0, 1, n);
}
 
private static ulong Fib(ulong a, ulong b, uint n) {
    return (n < 1)? a :(n == 1)?  b : Fib(b, a + b, n - 1);
}
 

Iterative

 
public static ulong Fib(uint x) {
    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++) {
        int sum = prev + next;
        prev = next;
        next = sum;
        fibs.Add(sum); 
    }
    return fibs;
}
 

Eager-Generative

 
public static IEnumerable<long> Fibs(uint x) {
    IList<ulong> fibs = new List<ulong>();
 
    ulong prev = -1;
    ulong next = 1;
    for (int i = 0; i < x; i++)
    {
     long sum = prev + next;
        prev = next;
        next = sum;
        fibs.Add(sum); 
    }
    return fibs;
}
 

Lazy-Generative

 
public static IEnumerable<ulong> Fibs(uint x) {
    ulong prev = -1;
    ulong next = 1;
    for (uint i = 0; i < x; i++) {
        ulong sum = prev + next;
        prev = next;
        next = sum;
        yield return sum;
    }
}
 

Analytic

Only works to the 92^th fibonacci number.

 
private static double Phi = ((1d + Math.Sqrt(5d))/2d);
private static double D = 1d/Math.Sqrt(5d);
 
ulong Fib(uint n) {
    if(n > 92) throw new ArgumentOutOfRangeException("n", n, "Needs to be smaller than 93."); 
    return (ulong)((Phi^n) - (1d - Phi)^n))*D);
}
 

Matrix

Algorithm is based on

$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F(n+1)&F(n)\\F(n)&F(n-1)\end{pmatrix}$.

Needs System.Windows.Media.Matrix or similar Matrix class. Calculates in O(n).

 
public static ulong Fib(uint n) {
    var M = new Matrix(1,0,0,1);
    var N = new Matrix(1,1,1,0);
    for (uint i = 1; i < n; i++) M *= N;
    return (ulong)M[0][0];
}
 

Needs System.Windows.Media.Matrix or similar Matrix class. Calculates in O(logn).

 
private static Matrix M;
private static readonly Matrix N = new Matrix(1,1,1,0);
 
public static ulong Fib(uint n) {
    M = new Matrix(1,0,0,1);
    MatrixPow(n-1);
    return (ulong)M[0][0];
}
 
private static void MatrixPow(double n){
    if (n > 1) {
        MatrixPow(n/2);
        M *= M;
    }
    if (n % 2 == 0) M *= N;
}
 

Array (Table) Lookup

 
private static int[] fibs = new int[]{ -1836311903, 1134903170, 
  -701408733, 433494437, -267914296, 165580141, -102334155, 
  63245986, -39088169, 24157817, -14930352, 9227465, -5702887, 
  3524578, -2178309, 1346269, -832040, 514229, -317811, 196418, 
  -121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181, 
  -2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13, 
  -8, 5, -3, 2, -1, 1, 0, 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,
  1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
  39088169, 63245986, 102334155, 165580141, 267914296, 433494437,
  701408733, 1134903170, 1836311903};
 
public static int Fib(int n) {
    if(n < -46 || n > 46) throw new ArgumentOutOfRangeException("n", n, "Has to be between -46 and 47.")
    return fibs[n+46];
}
 

Cat

define fib {
  dup 1 <=
    []
    [dup 1 - fib swap 2 - fib +]
  if
}

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.

CMake

Iteration uses a while() loop. Memoization uses global properties.

set_property(GLOBAL PROPERTY fibonacci_0 0)
set_property(GLOBAL PROPERTY fibonacci_1 1)
set_property(GLOBAL PROPERTY fibonacci_next 2)
 
# var = nth number in Fibonacci sequence.
function(fibonacci var n)
  # If the sequence is too short, compute more Fibonacci numbers.
  get_property(next GLOBAL PROPERTY fibonacci_next)
  if(NOT next GREATER ${n})
    # a, b = last 2 Fibonacci numbers
    math(EXPR i "${next} - 2")
    get_property(a GLOBAL PROPERTY fibonacci_${i})
    math(EXPR i "${next} - 1")
    get_property(b GLOBAL PROPERTY fibonacci_${i})
 
    while(NOT next GREATER ${n})
      math(EXPR i "${a} + ${b}")  # i = next Fibonacci number
      set_property(GLOBAL PROPERTY fibonacci_${next} ${i})
      set(a ${b})
      set(b ${i})
      math(EXPR next "${next} + 1")
    endwhile()
    set_property(GLOBAL PROPERTY fibonacci_next ${next})
  endif()
 
  get_property(answer GLOBAL PROPERTY fibonacci_${n})
  set(${var} ${answer} PARENT_SCOPE)
endfunction(fibonacci)

# Test program: print 0th to 9th and 25th to 30th Fibonacci numbers.
set(s "")
foreach(i RANGE 0 9)
  fibonacci(f ${i})
  set(s "${s} ${f}")
endforeach(i)
set(s "${s} ... ")
foreach(i RANGE 25 30)
  fibonacci(f ${i})
  set(s "${s} ${f}")
endforeach(i)
message(${s})

 0 1 1 2 3 5 8 13 21 34 ... 75025 121393 196418 317811 514229 832040

Clojure

This is implemented idiomatically as an infinitely long, lazy sequence of all Fibonacci numbers:

(defn fibs []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

Thus to get the nth one:

(nth (fibs) 5)

So long as one does not hold onto the head of the sequence, this is unconstrained by length.

The one-line implementation may look confusing at first, but on pulling it apart it actually solves the problem more "directly" than a more explicit looping construct.

(defn fibs []
  (map first ;; throw away the "metadata" (see below) to view just the fib numbers
       (iterate ;; create an infinite sequence of [prev, curr] pairs
         (fn [[a b]] ;; to produce the next pair, call this function on the current pair
           [b (+ a b)]) ;; new prev is old curr, new curr is sum of both previous numbers
         [0 1]))) ;; recursive base case: prev 0, curr 1

A more elegant solution is inspired by the Haskell implementation of an infinite list of Fibonacci numbers:

(def fib (lazy-cat [0 1] (map + fib (rest fib))))

Then, to see the first ten,

user> (take 10 fib)
(0 1 1 2 3 5 8 13 21 34)

Here's a simple interative process (using a recursive function) that carries state along with it (as args) until it reaches a solution:

;; max is which fib number you'd like computed (0th, 1st, 2nd, etc.)
;; n is which fib number you're on for this call (0th, 1st, 2nd, etc.)
;; j is the nth fib number (ex. when n = 5, j = 5)
;; i is the nth - 1 fib number
(defn- fib-iter
  [max n i j]
  (if (= n max)
    j
    (recur max
           (inc n)
           j
           (+ i j))))
 
(defn fib
  [max]
  (if (< max 2)
    max
    (fib-iter max 1 0N 1N)))

"defn-" means that the function is private (for use only inside this library). The "N" suffixes on integers tell Clojure to use arbitrary precision ints for those.

CoffeeScript

Analytic

fib_ana = (n) ->
    sqrt = Math.sqrt
    phi = ((1 + sqrt(5))/2)
    return Math.round((Math.pow(phi, n)/sqrt(5)))

Iterative

fib_iter = (n) ->
    if n < 2
        return n
    [prev, curr] = 0, 1
    for i in [1..n]
       [prev, curr] = [curr, curr + prev]
    return curr

Recursive

fib_rec = (n) ->
    if n < 2
        return n
    else 
        return fib_rec(n-1) + fib_rec(n-2)

Common Lisp

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

(defun fibonacci-recursive (n)
  (if (< n 2)
      n
     (+ (fibonacci-recursive (- n 2)) (fibonacci-recursive (- n 1)))))

(defun fibonacci-iterative (n &aux (f0 0) (f1 1))
  (case n
    (0 f0)
    (1 f1)
    (t (loop for n from 2 to n
             for a = f0 then b and b = f1 then result
             for result = (+ a b)
             finally (return result)))))

(defun fibonacci-tail-recursive ( n &optional (a 0) (b 1))
  (if (= n 0) 
      a 
      (fibonacci-tail-recursive (- n 1) b (+ a b))))

Tail recursive and squaring:

(defun fib (n &optional (a 1) (b 0) (p 0) (q 1))
    (if (= n 1) (+ (* b p) (* a q))
     (fib (ash n -1) 
          (if (evenp n) a (+ (* b q) (* a (+ p q))))
          (if (evenp n) b (+ (* b p) (* a q)))
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q))))) ;p is Fib(2^n-1), q is Fib(2^n).
 
(print (fib 100000))

Not a function, just printing out the entire (for some definition of "entire") sequence with a for var = loop:

(loop for x = 0 then y and y = 1 then (+ x y) do (print x))

D

Here are four versions of Fibonacci Number calculating functions. FibD has an argument limit of magnitude 84 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. A Fibonacci Number generating function is added. All functions have support for negative arguments.

import std.stdio, std.conv, std.algorithm, std.math;
 
long sgn(alias unsignedFib)(int n) { // break sign manipulation apart
    immutable uint m = (n >= 0) ? n : -n;
    if (n < 0 && (n % 2 == 0))
        return -unsignedFib(m);
    else
        return unsignedFib(m);
}
 
long fibD(uint m) { // Direct Calculation, correct for abs(m) <= 84
    enum sqrt5r =  1.0L / sqrt(5.0L);         //  1 / sqrt(5)
    enum golden = (1.0L + sqrt(5.0L)) / 2.0L; // (1 + sqrt(5)) / 2
    return roundTo!long(pow(golden, m) * sqrt5r);
}
 
long fibI(in uint m) pure nothrow { // Iterative
    long thisFib = 0;
    long nextFib = 1;
    foreach (i; 0 .. m) {
        long tmp = nextFib;
        nextFib += thisFib;
        thisFib  = tmp;
    }
    return thisFib;
}
 
long fibR(uint m) { // Recursive
    return (m < 2) ? m : fibR(m - 1) + fibR(m - 2);
}
 
long fibM(uint m) { // memoized Recursive
    static long[] fib = [0, 1];
    while (m >= fib.length )
        fib ~= fibM(m - 2) + fibM(m - 1);
    return fib[m];
}
 
alias sgn!fibD sfibD;
alias sgn!fibI sfibI;
alias sgn!fibR sfibR;
alias sgn!fibM sfibM;
 
auto fibG(in int m) { // generator(?)
    immutable int sign = (m < 0) ? -1 : 1;
    long yield;
 
    return new class {
        final int opApply(int delegate(ref int, ref long) dg) {
            int idx = -sign; // prepare for pre-increment
            foreach (f; this)
                if (dg(idx += sign, f))
                    break;
            return 0;
        }
 
        final int opApply(int delegate(ref long) dg) {
            long f0, f1 = 1;
            foreach (p; 0 .. m * sign + 1) {
                if (sign == -1 && (p % 2 == 0))
                    yield = -f0;
                else
                    yield = f0;
                if (dg(yield)) break;
                auto temp = f1;
                f1 = f0 + f1;
                f0 = temp;
            }
            return 0;
        }
    };
}
 
void main(in string[] args) {
    int k = args.length > 1 ? to!int(args[1]) : 10;
    writefln("Fib(%3d) = ", k);
    writefln("D : %20d <- %20d + %20d",
             sfibD(k), sfibD(k - 1), sfibD(k - 2));
    writefln("I : %20d <- %20d + %20d",
             sfibI(k), sfibI(k - 1), sfibI(k - 2));
    if (abs(k) < 36 || args.length > 2)
        // set a limit for recursive version
        writefln("R : %20d <- %20d + %20d",
                 sfibR(k), sfibM(k - 1), sfibM(k - 2));
    writefln("O : %20d <- %20d + %20d",
             sfibM(k), sfibM(k - 1), sfibM(k - 2));
    foreach (i, f; fibG(-9))
        writef("%d:%d | ", i, f);
}

Output for n = 85:

Fib( 85) = 
D :   259695496911122586 <-   160500643816367088 +    99194853094755497
I :   259695496911122585 <-   160500643816367088 +    99194853094755497
O :   259695496911122585 <-   160500643816367088 +    99194853094755497
0:0 | -1:1 | -2:-1 | -3:2 | -4:-3 | -5:5 | -6:-8 | -7:13 | -8:-21 | -9:34 | 

Faster version

This is based on matrix exponentiation:

import std.stdio, std.bigint;
 
T fibonacciMatrix(T=BigInt)(size_t n) {
    int[size_t.sizeof * 8] binDigits;
    size_t nBinDigits;
    while (n > 0) {
        binDigits[nBinDigits] = n % 2;
        n /= 2;
        nBinDigits++;
    }
 
    T x=1, y, z=1;
    foreach_reverse (b; binDigits[0 .. nBinDigits]) {
        if (b) {
            x = (x + z) * y;
            y = y ^^ 2 + z ^^ 2;
        } else {
            auto x_old = x;
            x = x ^^ 2 + y ^^ 2;
            y = (x_old + z) * y;
        }
        z = x + y;
    }
 
    return y;
}
 
void main() {
    writeln(fibonacciMatrix(1_000_000));
}

With n = 1_000_000 it shows the result of almost 209 thousands digits in less than 4.5 seconds.

Dart

int fib(int n) {
  if(n==0 || n==1) {
    return n;
  }
  int prev=1;
  int current=1;
  for(int i=2;i<n;i++) {
    int next=prev+current;
    prev=current;
    current=next;    
  }
  return current;
}
 
int fibRec(int n) => n==0||n==1 ? n : fibRec(n-1)+fibRec(n-2);
 
main() {
  print(fib(11));
  print(fibRec(11));
}

Delphi

Iterative

 
function FibonacciI(N: Word): UInt64;
var
  Last, New: UInt64;
  I: Word;
begin
  if N < 2 then
    Result := N
  else begin
    Last := 0;
    Result := 1;
    for I := 2 to N do
    begin
      New := Last + Result;
      Last := Result;
      Result := New;
    end;
  end;
end;
 

Recursive

 
function Fibonacci(N: Word): UInt64;
begin
  if N < 2 then
    Result := N
  else
   Result := Fibonacci(N - 1) + Fibonacci(N - 2);
end;
 

Matrix

Algorithm is based on

$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F(n+1)&F(n)\\F(n)&F(n-1)\end{pmatrix}$.

 
function fib(n:Int64):int64;
 
	type TFibMat = array[0..1] of array[0..1] of int64;
 
	function FibMatMul(a,b:TFibMat):TFibMat;
	var     i,j,k:integer;
		tmp:TFibMat;
	begin
	for i:=0 to 1 do
	for j:=0 to 1 do
	begin
	tmp[i,j]:=0;
	for k:=0 to 1 do tmp[i,j]:=tmp[i,j]+a[i,k]*b[k,j];
	end;
	FibMatMul:=tmp;
	end;
 
	function FibMatExp(a:TFibMat;n:int64):TFibmat;
	begin
	if n<=1 then fibmatexp:=a else
	if (n mod 2 = 0) then FibMatExp:=FibMatExp(FibMatMul(a,a), n div 2) else
	if (n mod 2 = 1) then FibMatExp:=FibMatMul(a,FibMatExp(FibMatMul(a,a),(n) div 2));
	end;
 
 
var 
	matrix:TFibMat;
 
begin
matrix[0,0]:=1;
matrix[0,1]:=1;
matrix[1,0]:=1;
matrix[1,1]:=0;
if n>1 then
matrix:=fibmatexp(matrix,n-1);
fib:=matrix[0,0];
end;
 

DWScript

function fib(N : Integer) : Integer;
begin
  if N < 2 then Result := 1
  else Result := fib(N-2) + fib(N-1);
End;

E

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

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

Ela

Tail-recursive function:

fib = fib' 0 1           
      where fib' a b 0 = a                 
            fib' a b n = fib' b (a + b) (n - 1)

Infinite (lazy) list:

fib = fib' 1 1
      where fib' x y = & x :: fib' y (x + y)

Erlang

Recursive:

fib(0) -> 0;
fib(1) -> 1;
fib(N) when N > 1 -> fib(N-1) + fib(N-2).

Tail-recursive (iterative):

fib(N) -> fib(N,0,1).
fib(0,Res,_) -> Res;
fib(N,Res,Next) when N > 0 -> fib(N-1, Next, Res+Next).

Euphoria

'Recursive' version

Works with: Euphoria version any version

 
function fibor(integer n)
  if n<2 then return n end if
  return fibor(n-1)+fibor(n-2)
end function
 

'Iterative' version

Works with: Euphoria version any version

 
function fiboi(integer n)
integer f0=0, f1=1, f  
  if n<2 then return n end if
  for i=2 to n do
    f=f0+f1
    f0=f1
    f1=f   
  end for
  return f
end function
 

'Tail recursive' version

Works with: Euphoria version 4.0.0

 
function fibot(integer n, integer u = 1, integer s = 0)
  if n < 1 then
    return s
  else
    return fibot(n-1,u+s,u)
  end if
end function
 
-- example:
? fibot(10) -- says 55
 

'Paper tape' version

Works with: Euphoria version 4.0.0

 
include std/mathcons.e -- for PINF constant
 
enum ADD, MOVE, GOTO, OUT, TEST, TRUETO
 
global sequence tape = { 0, 
			 1, 
		       { ADD, 2, 1 }, 
		       { TEST, 1, PINF }, 
		       { TRUETO, 0 }, 
		       { OUT, 1, "%.0f\n" }, 
		       { MOVE, 2, 1 }, 
		       { MOVE, 0, 2 }, 
		       { GOTO, 3  } }
 
global integer ip
global integer test
global atom accum
 
procedure eval( sequence cmd )
	atom i = 1
	while i <= length( cmd ) do
		switch cmd[ i ] do
			case ADD then
				accum = tape[ cmd[ i + 1 ] ] + tape[ cmd[ i + 2 ] ]
				i += 2
 
			case OUT then
				printf( 1, cmd[ i + 2], tape[ cmd[ i + 1 ] ] ) 
				i += 2
 
			case MOVE then
				if cmd[ i + 1 ] = 0 then
					tape[ cmd[ i + 2 ] ] = accum
				else
					tape[ cmd[ i + 2 ] ] = tape[ cmd[ i + 1 ] ]
				end if
				i += 2
 
			case GOTO then
				ip = cmd[ i + 1 ] - 1 -- due to ip += 1 in main loop
				i += 1
 
			case TEST then
				if tape[ cmd[ i + 1 ] ] = cmd[ i + 2 ] then
					test = 1
				else
					test = 0
				end if
				i += 2
 
			case TRUETO then
				if test then
					if cmd[ i + 1 ] = 0 then
						abort(0)
					else
						ip = cmd[ i + 1 ] - 1
					end if
				end if
 
		end switch
		i += 1
	end while
end procedure
 
test = 0
accum = 0
ip = 1
 
while 1 do
 
	-- embedded sequences (assumed to be code) are evaluated
	-- atoms (assumed to be data) are ignored
 
	if sequence( tape[ ip ] ) then
		eval( tape[ ip ] ) 
	end if
	ip += 1
end while
 
 

FALSE

[[$0=~][1-@@\$@@+\$44,.@]#]f:
20n: {First 20 numbers}
0 1 n;f;!%%44,. {Output: "0,1,1,2,3,5..."}

Factor

Iterative

: fib ( n -- m )
    dup 2 < [
        [ 0 1 ] dip [ swap [ + ] keep ] times
        drop
    ] unless ;

Recursive

: fib ( n -- m )
    dup 2 < [
        [ 1 - fib ] [ 2 - fib ] bi +
    ] unless ;

Tail-Recursive

: fib2 ( x y n -- a )
  dup 1 <
    [ 2drop ]
    [ [ swap [ + ] keep ] dip 1 - fib2 ]
  if ;
: fib ( n -- m ) [ 0 1 ] dip fib2 ;

Matrix

Translation of: Ruby

USE: math.matrices
 
: fib ( n -- m )
    dup 2 < [
        [ { { 0 1 } { 1 1 } } ] dip 1 - m^n
        second second
    ] unless ;

Fancy

class Fixnum {
  def fib {
    match self -> {
      case 0 -> 0
      case 1 -> 1
      case _ -> self - 1 fib + (self - 2 fib)
    }
  }
}
 
15 times: |x| {
  x fib println
}
 

Falcon

Iterative

function fib_i(n)
 
    if n < 2: return n
 
    fibPrev = 1
    fib = 1
    for i in [2:n]
        tmp = fib
        fib += fibPrev
        fibPrev = tmp
    end
    return fib
end

Recursive

function fib_r(n)
    if n < 2 :  return n
    return fib_r(n-1) + fib_r(n-2)
end

Tail Recursive

function fib_tr(n)
    return fib_aux(n,0,1)       
end
function fib_aux(n,a,b)
   switch n
      case 0 : return a
      default: return fib_aux(n-1,a+b,a)
   end
end

Fantom

Ints have a limit of 64-bits, so overflow errors occur after computing Fib(92) = 7540113804746346429.

 
class Main
{
  static Int fib (Int n) 
  {
    if (n < 2) return n
    fibNums := [1, 0]
    while (fibNums.size <= n)
    {
      fibNums.insert (0, fibNums[0] + fibNums[1])
    }
    return fibNums.first
  }
 
  public static Void main ()
  {
    20.times |n| 
    {
      echo ("Fib($n) is ${fib(n)}")
    }
  }
}
 

Fexl

 
# fibonacci is the infinite list of all Fibonacci numbers.
#
# Note that this program uses the symbols "1" and "+".  You can specify
# the definitions of those symbols however you like, allowing you to use
# any system of arithmetic you need.  For example, you can use either the
# built-in long arithmetic, or infinite precision arithmetic, by simply
# defining "1" and "+" appropriately.
 
\fibonacci =
    (
    \fibonacci == (\x\y
        item x;
        \z = (+ x y)
        fibonacci y z
        )
 
    fibonacci 1 1
    )
 
# OK, so that's the list of *all* Fibonacci numbers.  If you want the nth number,
# you can extract it with the fib function as follows.  By the way, this *does*
# have the effect of caching, so once a particular point in the sequence is
# calculated, it doesn't have to be calculated again.
 
# (fib n) is the nth fibonacci number, starting with n==0, or 1 if n is negative.
\fib = (\n list_at fibonacci n 1)
 

Forth

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

Fortran

Recursive

In ISO Fortran 90 or later, use a RECURSIVE function:

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

Iterative

In ISO Fortran 90 or later:

    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

Test program

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

Output

0 0
1 1
1 1
2 2
3 3
5 5
8 8
13 13
21 21
34 34
55 55

freebasic

Extended sequence coded big integer.

 
 
'Fibonacci extended
'Freebasic version 24  Windows
Dim Shared ADDQmod(0 To 19) As Ubyte
Dim Shared ADDbool(0 To 19) As Ubyte
For z As Integer=0 To 19
    ADDQmod(z)=(z Mod 10+48)
    ADDbool(z)=(-(10<=z))
Next z 
Function plusINT(NUM1 As String,NUM2 As String) As String
    Dim As Byte flag
    #macro finish()
    three=Ltrim(three,"0")
    If three="" Then Return "0"
    If flag=1 Then Swap NUM2,NUM1
    Return three
    Exit Function
    #endmacro
    var lenf=Len(NUM1)
    var lens=Len(NUM2)
    If lens>lenf Then 
        Swap NUM2,NUM1
        Swap lens,lenf
        flag=1
    End If
 
    var diff=lenf-lens-Sgn(lenf-lens)
    var three="0"+NUM1
    var two=String(lenf-lens,"0")+NUM2
    Dim As Integer n2
    Dim As Ubyte addup,addcarry
 
    addcarry=0
 
    For n2=lenf-1 To diff Step -1 
        addup=two[n2]+NUM1[n2]-96
        three[n2+1]=addQmod(addup+addcarry)
        addcarry=addbool(addup+addcarry)
    Next n2 
    If addcarry=0 Then 
        finish()
    End If
    If n2=-1 Then 
        three[0]=addcarry+48
        finish()
    End If
 
    For n2=n2 To 0 Step -1 
        addup=two[n2]+NUM1[n2]-96
        three[n2+1]=addQmod(addup+addcarry)
        addcarry=addbool(addup+addcarry)
    Next n2
    three[0]=addcarry+48
    finish()
End Function
 
 
 
Function  fibonacci(n As Integer) As String
    Dim As String sl,l,term
    sl="0": l="1"
    If n=1 Then Return "0"
    If n=2 Then Return "1"
    n=n-2
    For x As Integer= 1 To n
        term=plusINT(l,sl)
        sl=l
        l=term
    Next x
    Function =term
End Function
 
'==============  EXAMPLE ===============
print "THE SEQUENCE TO 10:"
print
For n As Integer=1 To 10
    Print "term";n;": "; fibonacci(n)
Next n
print
print "Selected Fibonacci number"
print "Fibonacci 500"
print
print fibonacci(500)
Sleep
 

Output

THE SEQUENCE TO 10:

term 1: 0
term 2: 1
term 3: 1
term 4: 2
term 5: 3
term 6: 5
term 7: 8
term 8: 13
term 9: 21
term 10: 34

Selected Fibonacci number
Fibonacci 500

86168291600238450732788312165664788095941068326060883324529903470149056115823592
713458328176574447204501

F#

This is a fast [tail-recursive] approach using the F# big integer support.

 
let fibonacci n : bigint =
  let rec f a b n =
    match n with
    | 0 -> a
    | 1 -> b
    | n -> (f b (a + b) (n - 1))
  f (bigint 0) (bigint 1) n
> fibonacci 100;;
val it : bigint = 354224848179261915075I

Lazy evaluated using sequence workflow

let rec fib = seq { yield! [0;1];
                    for (a,b) in Seq.zip fib (Seq.skip 1 fib) -> a+b}

Lazy evaluated using the sequence unfold anamorphism

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 10000
 

GAP

fib := function(n)
  local a;
  a := [[0, 1], [1, 1]]^n;
  return a[1][2];
end;

GAP has also a buit-in function for that.

Fibonacci(n);

Gecho

0 1 dup wover + dup wover + dup wover + dup wover +

Prints the first several fibonacci numbers...

Go

Recursive

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

Iterative

import (
	"math/big"
)
 
func fib(n uint64) *big.Int {
	if n < 2 {
		return big.NewInt(int64(n))
	}
	a, b := big.NewInt(0), big.NewInt(1)
	for n--; n > 0; n-- {
		a.Add(a, b)
		a, b = b, a
	}
	return b
}

Groovy

Recursive

A recursive closure must be pre-declared.

def rFib
rFib = { it < 1 ? 0 : it == 1 ? 1 : rFib(it-1) + rFib(it-2) }

Iterative

def iFib = { it < 1 ? 0 : it == 1 ? 1 : (2..it).inject([0,1]){i, j -> [i[1], i[0]+i[1]]}[1] }

Test program:

(0..20).each { println "${it}:    ${rFib(it)}    ${iFib(it)}" }

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

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);
}

As Iterator

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;
	}
}

Used like:

for (i in new FibIter(10))
	Sys.println(i);

Haskell

With lazy lists

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

fib = 0 : 1 : zipWith (+) fib (tail fib)

The nth Fibonacci number is then just fib !! n. The above is equivalent to

fib = 0 : 1 : next fib where next (a: t@(b:_)) = (a+b) : next t

Also

fib = 0 : scanl (+) 1 fib

With matrix exponentiation

With the (rather slow) code from Matrix exponentiation operator

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]]

we can simply write

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

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

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

With recurrence relations

Using Fib[m=3n+r] recurrence identities:

fibsteps (a,b) n 
    | n <= 0 = (a,b)
    | True   = fibsteps (b, a+b) (n-1)
 
fibnums :: [Integer]
fibnums = map fst $ iterate (`fibsteps` 1) (0,1) 
 
fibN2 :: Integer -> (Integer, Integer)
fibN2 m | m < 10 = fibsteps (0,1) m
fibN2 m          = fibN2_next (n,r) (fibN2 n)
                     where (n,r) = quotRem m 3
 
fibN2_next (n,r) (f,g) | r==0 = (a,b)    -- 3n  ,3n+1
                       | r==1 = (b,c)    -- 3n+1,3n+2
                       | r==2 = (c,d)    -- 3n+2,3n+3   (*)
  where
      a = ( 5*f^3 + if even n then 3*f else (- 3*f) ) -- 3n
      d = ( 5*g^3 + if even n then (- 3*g) else 3*g ) -- 3(n+1)   (*)
      b = (   g^3 + 3 * g * f^2 - f^3               ) -- 3n+1
      c = (   g^3 + 3 * g^2 * f + f^3               ) -- 3n+2 

(fibN2 n) directly calculates a pair (f,g) of two consecutive Fibonacci numbers, (Fib[n], Fib[n+1]), from recursively calculated such pair at about n/3:

 *Main> take 10 $ show $ fst $ fibN2 (10^6)
 "1953282128"

The above should take less than 0.1s on modern PC to calculate.

Hope

Recursive

dec f : num -> num;
--- f 0 <= 0;
--- f 1 <= 1;
--- f(n+2) <= f n + f(n+1);

Tail-recursive

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;

With lazy lists

This language, being one of Haskell's ancestors, also has lazy lists. Here's the (infinite) list of all Fibonacci numbers:

dec fibs : list num;
--- fibs <= fs whererec fs == 0::1::map (+) (tail fs||fs);

The nth Fibonacci number is then just fibs @ n.

HicEst

REAL :: Fibonacci(10)
 
Fibonacci = ($==2) + Fibonacci($-1) + Fibonacci($-2)
WRITE(ClipBoard) Fibonacci ! 0 1 1 2 3 5 8 13 21 34

Icon and Unicon

Icon has built-in support for big numbers. First, a simple recursive solution augmented by caching for non-negative input. This examples computes fib(1000) if there is no integer argument.

procedure main(args)
    write(fib(integer(!args) | 1000)
end
 
procedure fib(n)
    static fCache
    initial {
        fCache := table()
        fCache[0] := 0
        fCache[1] := 1
        }
    /fCache[n] := fib(n-1) + fib(n-2)
    return fCache[n]
end

Library: Icon Programming Library

The above solution is similar to the one provided fib in memrfncs

Now, an O(logN) solution. For large N, it takes far longer to convert the result to a string for output than to do the actual computation. This example computes fib(1000000) if there is no integer argument.

procedure main(args)
    write(fib(integer(!args) | 1000000))
end
 
procedure fib(n)
    return fibMat(n)[1]
end
 
procedure fibMat(n)
    if n <= 0 then return [0,0]
    if n  = 1 then return [1,0]
    fp := fibMat(n/2)
    c := fp[1]*fp[1] + fp[2]*fp[2]
    d := fp[1]*(fp[1]+2*fp[2])
    if n%2 = 1 then return [c+d, d]
    else return [d, c]
end

IDL

Recursive

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

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

Iterative

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

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

Analytic

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

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:

   fibN=: (-&2 +&$: -&1)^:(1&<) M."0

Examples:

   fibN 12
144
   fibN  i.31
0 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

(This implementation is doubly recursive except that results are cached across function calls.)

Java

Iterative

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;
}

Recursive

public static long recFibN(final int n)
{
 return (n < 2) ? n : recFibN(n - 1) + recFibN(n - 2);
}

Analytic

This method works up to the 92^nd Fibonacci number. After that, it goes out of range.

public static long anFibN(final 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));
}

Tail-recursive

public static long fibTailRec(final int n)
{
 return fibInner(0, 1, n);
}
 
private static long fibInner(final long a, final long b, final int n)
{
 return n < 1 ? a : n == 1 ?  b : fibInner(b, a + b, n - 1);
}

JavaScript

Recursive

One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion:

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

Iterative

function fib(n)
{
 var
  a = 0,
  b = 1,
  t;
 while (n-- > 0)
 {
  t = a;
  a = b;
  b += t;
 }
 return a;
}
 
var i;
for (i = 0; i < 10; ++i)
 alert(fib(i));

Memoization

var fib = (function(cache){
    return cache = cache || {}, function(n){
        if (cache[n]) return cache[n];
        else return cache[n] = n == 0 ? 0 : n < 0 ? -fib(-n)
            : n <= 2 ? 1 : fib(n-2) + fib(n-1);
    };
})();
 

Y-Combinator

function Y(dn) {
    return (function(fn) {
        return fn(fn);
    }(function(fn) {
        return dn(function() {
            return fn(fn).apply(null, arguments);
        });
    }));
}
var fib = Y(function(fn) {
    return function(n) {
        if (n === 0 || n === 1) {
            return n;
        }
        return fn(n - 1) + fn(n - 2);
    };
});

Joy

Recursive

DEFINE fib == [small] [] [pred dup pred] [+] binrec.

Iterative

DEFINE fib == [1 0] dip [swap [+] unary] times popd.

Julia

fib(n) = n < 2 ? n : fib(n-1) + fib(n-2)

K

Recursive

{:[x<3;1;_f[x-1]+_f[x-2]]}

Recursive with memoization

Using a (global) dictionary c.

{c::.();{v:c[a:`$$x];:[x<3;1;:[_n~v;c[a]:_f[x-1]+_f[x-2];v]]}x}

Analytic

phi:(1+_sqrt(5))%2
{_((phi^x)-((1-phi)^x))%_sqrt[5]}

Sequence to n

{(x(|+\)\1 1)[;1]}

{x{x,+/-2#x}/!2}

LabVIEW

This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.

Lang5

[] '__A set : dip swap __A swap 2 compress collapse '__A set execute
    __A -1 extract nip ;  : nip swap drop ;  : tuck swap over ;
: -rot rot rot ; : 0= 0 == ; : 1+ 1 + ; : 1- 1 - ; : sum '+ reduce ;
: bi 'keep dip execute ;  : keep over 'execute dip ;
 
: fib dup 1 > if dup 1- fib swap 2 - fib + then ;
: fib  dup 1 > if "1- fib" "2 - fib" bi + then ;

Liberty BASIC

for i = 0 to 15
    print fiboR(i),fiboI(i)
next i
 
function fiboR(n)
    if n <= 1 then
        fiboR = n
    else
        fiboR = fiboR(n-1) + fiboR(n-2)
    end if
end function
 
function fiboI(n)
    a = 0
    b = 1
    for i = 1 to n
        temp = a + b
        a = b
        b = temp
    next i
    fiboI = a
end function
 

Lisaac

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

Logo

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

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 a(n,u,s) if n<2 then return u+s end return a(n-1,u+s,u) end
function trfib(i) return a(i,1,0) end
 
--table-recursive
fib_n = setmetatable({1, 1}, {__index = function(z,n) return z[n-1] + z[n-2] end})

LSL

Rez a box on the ground, and add the following as a New Script.

integer Fibonacci(integer n) {
	if(n<2) {
		return n;
	} else {
		return Fibonacci(n-1)+Fibonacci(n-2);
	}
}
default {
	state_entry() {
		integer x = 0;
		for(x=0 ; x<35 ; x++) {
			llOwnerSay("Fibonacci("+(string)x+")="+(string)Fibonacci(x));
		}
	}
}

Output:

Fibonacci(0)=0
Fibonacci(1)=1
Fibonacci(2)=1
Fibonacci(3)=2
Fibonacci(4)=3
Fibonacci(5)=5
Fibonacci(6)=8
Fibonacci(7)=13
Fibonacci(8)=21
Fibonacci(9)=34
Fibonacci(10)=55
Fibonacci(11)=89
Fibonacci(12)=144
Fibonacci(13)=233
Fibonacci(14)=377
Fibonacci(15)=610
Fibonacci(16)=987
Fibonacci(17)=1597
Fibonacci(18)=2584
Fibonacci(19)=4181
Fibonacci(20)=6765
Fibonacci(21)=10946
Fibonacci(22)=17711
Fibonacci(23)=28657
Fibonacci(24)=46368
Fibonacci(25)=75025
Fibonacci(26)=121393
Fibonacci(27)=196418
Fibonacci(28)=317811
Fibonacci(29)=514229
Fibonacci(30)=832040
Fibonacci(31)=1346269
Fibonacci(32)=2178309
Fibonacci(33)=3524578
Fibonacci(34)=5702887

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

Mathematica

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

fib[0] = 0
fib[1] = 1
fib[n_Integer] := fib[n - 1] + fib[n - 2]

An optimization is to cache the values already calculated:

fib[0] = 0
fib[1] = 1
fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]

MATLAB

Iterative

function F = fibonacci(n)
 
    Fn = [1 0]; %Fn(1) is F_{n-2}, Fn(2) is F_{n-1} 
    F = 0; %F is F_{n}
 
    for i = (1:abs(n))
        Fn(2) = F;
        F = sum(Fn);
        Fn(1) = Fn(2);
    end
 
    if n < 0
        F = F*((-1)^(n+1));
    end   
 
end

Dramadah Matrix Method

The MATLAB help file suggests an interesting method of generating the Fibonacci numbers. Apparently the determinate of the Dramadah Matrix of type 3 (MATLAB designation) and size n-by-n is the nth Fibonacci number. This method is implimented below.

function number = fibonacci2(n)
 
    if n == 1
        number = 1;
    elseif n == 0
        number = 0;
    elseif n < 0
        number = ((-1)^(n+1))*fibonacci2(-n);;
    else
        number = det(gallery('dramadah',n,3));
    end
 
end

Maxima

/* fib(n) is built-in; here is an implementation */
fib2(n) := (matrix([0, 1], [1, 1])^^n)[1, 2]$
 
fib2(100)-fib(100);
0
 
fib2(-10);
-55

MAXScript

Iterative

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

Recursive

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

Mercury

Mercury is both a logic language and a functional language. As such there are two possible interfaces for calculating a Fibonacci number. This code shows both styles. Note that much of the code here is ceremony put in place to have this be something which can actually compile. The actual Fibonacci number generation is contained in the predicate fib/2 and in the function fib/1. The predicate main/2 illustrates first the unification semantics of the predicate form and the function call semantics of the function form.

The provided code uses a very naive form of generating a Fibonacci number. A more realistic implementation would use memoization to cache previous results, exchanging time for space. Also, in the case of supplying both a function implementation and a predicate implementation, one of the two would be implemented in terms of the other. Examples of this are given as comments below.

fib.m

 
% The following code is derived from the Mercury Tutorial by Ralph Becket.
% http://www.mercury.csse.unimelb.edu.au/information/papers/book.pdf
:- module fib.
 
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
 
:- implementation.
:- import_module int.
 
:- pred fib(int::in, int::out) is det.
fib(N, X) :-
    ( if N =< 2
          then X = 1
          else fib(N - 1, A), fib(N - 2, B), X = A + B ).
 
:- func fib(int) = int is det.
fib(N) = X :- fib(N, X).
 
main(!IO) :-
    fib(40, X),
    write_string("fib(40, ", !IO),
    write_int(X, !IO),
    write_string(")\n", !IO),
 
    write_string("fib(40) = ", !IO),
    write_int(fib(40), !IO),
    write_string("\n", !IO).
 

Iterative algorithm

The much faster iterative algorithm can be written as:

 
:- pred fib_acc(int::in, int::in, int::in, int::in, int::out) is det.
 
fib_acc(N, Limit, Prev2, Prev1, Res) :-
    ( N < Limit ->
        % limit not reached, continue computation.
        ( N =< 2 ->
            Res0 = 1
        ;
            Res0 = Prev2 + Prev1
        ),
        fib_acc(N+1, Limit, Prev1, Res0, Res)
    ;
        % Limit reached, return the sum of the two previous results.
        Res = Prev2 + Prev1
    ).
 

This predicate can be called as

fib_acc(1, 40, 1, 1, Result)

It has several inputs which form the loop, the first is the current number, the second is a limit, ie when to stop counting. And the next two are accumulators for the last and next-to-last results.

Memoization

But what if you want the speed of the fib_acc with the recursive (more declarative) definition of fib? Then use memoization, because Mercury is a pure language fib(N, F) will always give the same F for the same N, guaranteed. Therefore memoization asks the compiler to use a table to remember the value for F for any N, and it's a one line change:

 
:- pragma memo(fib/2).
:- pred fib(int::in, int::out) is det.
fib(N, X) :-
    ( if N =< 2
          then X = 1
          else fib(N - 1, A), fib(N - 2, B), X = A + B ).
 

We've shown the definition of fib/2 again, but the only change here is the memoization pragma (see the reference manual). This is not part of the language specification and different Mercury implementations are allowed to ignore it, however there is only one implementation so in practice memoization is fully supported.

Memoization trades speed for space, a table of results is constructed and kept in memory. So this version of fib consumes more memory than than fib_acc. It is also slightly slower than fib_acc since it must manage its table of results but it is much much faster than without memoization. Memoization works very well for the Fibonacci sequence because in the naive version the same results are calculated over and over again.

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

Mirah

def fibonacci(n:int)
    return n if n < 2
    fibPrev = 1
    fib = 1
    3.upto(Math.abs(n)) do 
        oldFib = fib
        fib = fib + fibPrev
        fibPrev = oldFib
    end
    fib * (n<0 ? int(Math.pow(n+1, -1)) : 1)
end
 
puts fibonacci 1
puts fibonacci 2
puts fibonacci 3
puts fibonacci 4
puts fibonacci 5
puts fibonacci 6
puts fibonacci 7
 

МК-61/52

П0	1	lg	Вx	<->	+	L0	03	С/П	БП
03

Instruction: n В/О С/П, where n is serial number of the number of Fibonacci sequence; С/П for the following numbers.

ML/I

MCSKIP "WITH" NL
"" Fibonacci - recursive
MCSKIP MT,<>
MCINS %.
MCDEF FIB WITHS ()
AS <MCSET T1=%A1.
MCGO L1 UNLESS 2 GR T1
%T1.<>MCGO L0
%L1.%FIB(%T1.-1)+FIB(%T1.-2).>
fib(0) is FIB(0)
fib(1) is FIB(1)
fib(2) is FIB(2)
fib(3) is FIB(3)
fib(4) is FIB(4)
fib(5) is FIB(5)

Modula-3

Recursive

PROCEDURE Fib(n: INTEGER): INTEGER =
  BEGIN
    IF n < 2 THEN
      RETURN n;
    ELSE
      RETURN Fib(n-1) + Fib(n-2);
    END;
  END Fib;

MUMPS

Iterative

FIBOITER(N)
 ;Iterative version to get the Nth Fibonacci number
 ;N must be a positive integer
 ;F is the tree containing the values
 ;I is a loop variable.
 QUIT:(N\1'=N)!(N<0) "Error: "_N_" is not a positive integer."
 NEW F,I
 SET F(0)=0,F(1)=1
 QUIT:N<2 F(N)
 FOR I=2:1:N SET F(I)=F(I-1)+F(I-2)
 QUIT F(N)

USER>W $$FIBOITER^ROSETTA(30)
832040

Nemerle

Recursive

using System;
using System.Console;
 
module Fibonacci
{
    Fibonacci(x : long) : long
    {
        |x when x < 2 => x
        |_ => Fibonacci(x - 1) + Fibonacci(x - 2)
    }
 
    Main() : void
    {
        def num = Int64.Parse(ReadLine());
        foreach (n in $[0 .. num])
            WriteLine("{0}: {1}", n, Fibonacci(n));
    }
}

Tail Recursive

Fibonacci(x : long, current : long, next : long) : long
{
    match(x)
    {
        |0 => current
        |_ => Fibonacci(x - 1, next, current + next)
    }
}
 
Fibonacci(x : long) : long
{
    Fibonacci(x, 0, 1)
}

NetRexx

Translation of: REXX

/* NetRexx */
 
options replace format comments java crossref savelog symbols
 
numeric digits 210000                  /*prepare for some big 'uns.     */
parse arg x y .                        /*allow a single number or range.*/
if x == '' then do                     /*no input? Then assume -30-->+30*/
  x = -30
  y = -x
  end
 
if y == '' then y = x             /*if only one number, show fib(n)*/
loop k = x to y                   /*process each Fibonacci request.*/
  q = fib(k)
  w = q.length                    /*if wider than 25 bytes, tell it*/
  say 'Fibonacci' k"="q
  if w > 25 then say 'Fibonacci' k "has a length of" w
  end k
exit
 
/*-------------------------------------FIB subroutine (non-recursive)---*/
method fib(arg) private static
  parse arg n
  na = n.abs
 
  if na < 2 then return na             /*handle special cases.          */
  a = 0
  b = 1
 
  loop j = 2 to na
    s = a + b
    a = b
    b = s
    end j
 
  if n > 0 | na // 2 == 1 then return  s /*if positive or odd negative... */
                          else return -s /*return a negative Fib number.  */
 

NewLISP

Recursive

(define (fibonacci n)
(if (< n 2) 1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
(print(fibonacci 10)) ;;89

Nimrod

Analytic

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

Iterative

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

Recursive

proc Fibonacci(n: int): int64 =
  if n <= 2:
    result = 1
  else:
    result = Fibonacci(n - 1) + Fibonacci(n - 2)

Tail-recursive

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)

Continuations

iterator fib: int {.closure.} =
  var a = 0
  var b = 1
  while true:
    yield a
    swap a, b
    b = a + b
 
var f = fib
for i in 0.. <10:
  echo f()

MASM

 
TITLE i hate visual studio 4			(Fibs.asm)
;       __         __/--------\
;      >__ \      /  |        |\
;         \  \___/ @  \      /   \__________________
;           \____       \  /                         \\\
;                \____         Coded with love by:    |||
;                      \      Alexander Alvonellos    |||
;                       |          9/29/2011         / ||
;                       |                           |  MM
;                       |      |--------------|     |
;                       |<     |              |<    |
;                       |      |              |     |
;                       |mmmmmm|              |mmmmm|
;; Epic Win. 
 
INCLUDE Irvine32.inc
 
.data
	BEERCOUNT = 48;
	Fibs dd 0, 1, BEERCOUNT DUP(0);
 
.code
main PROC
; I am not responsible for this code.
; They made me write it, against my will.
	;Here be dragons
	mov esi, offset Fibs; offset array;  ;;were to start (start)
	mov ecx, BEERCOUNT; 		;;count of items (how many)
	mov ebx, 4; 		;;size (in number of bytes)
	call DumpMem;
 
	mov ecx, BEERCOUNT; 	;//http://www.wolframalpha.com/input/?i=F ib%5B47%5D+%3E+4294967295
	mov esi, offset Fibs
	NextPlease:;
		mov eax, [esi]; 	;//Get me the data from location at ESI
		add eax, [esi+4];	;//add into the eax the data at esi + another double (next mem loc)
		mov [esi+8], eax;	;//Move that data into the memory location after the second number
		add esi, 4;			;//Update the pointer
	loop NextPlease;	;//Thank you sir, may I have another?
 
 
	;Here be dragons
	mov esi, offset Fibs; offset array;  ;;were to start (start)
	mov ecx, BEERCOUNT; 		;;count of items (how many)
	mov ebx, 4; 		;;size (in number of bytes)
	call DumpMem;
 
	exit		; exit to operating system
main ENDP
 
END main
 

Objeck

Recursive

bundle Default {
  class Fib {
    function : Main(args : String[]), Nil {
      for(i := 0; i <= 10; i += 1;) {
        Fib(i)->PrintLine();
      };
    }
 
    function : native : Fib(n : Int), Int {
      if(n < 2) {
        return n;
      };
 
      return Fib(n-1) + Fib(n-2);
    }
  }
}

Objective-C

Recursive

 
-(long)fibonacci:(int)position
{
    long result = 0;
    if (position < 2) {
        result = position;
    } else {
        result = [self fibonacci:(position -1)] + [self fibonacci:(position -2)];
    }
    return result;    
} 

Iterative

 
+(long)fibonacci:(int)index {
    long beforeLast = 0, last = 1;
    while (index > 0) {
        last += beforeLast;
        beforeLast = last - beforeLast;
        --index;
    }
    return last;
}

OCaml

Iterative

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

Recursive

let rec fib_rec n =
  if n < 2 then
    n
  else
    fib_rec (n - 1) + fib_rec (n - 2)

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:

let fib n =
  let rec fib_aux n a b =
    match n with
    | 0 -> a
    | _ -> fib_aux (n-1) b (a+b)
  in
  fib_aux n 0 1

Arbitrary Precision

Using OCaml's Num module.

open Num
 
let fib =
  let rec fib_aux f0 f1 = function
    | 0 -> f0
    | 1 -> f1
    | n -> fib_aux f1 (f1 +/ f0) (n - 1)
  in
  fib_aux (num_of_int 0) (num_of_int 1)

compile with:

ocamlopt nums.cmxa -o fib fib.ml

O(log(n)) with arbitrary precision

open Num
 
let mul (a,b,c) (d,e,f) =
  (a*/d +/ b*/e, a*/e +/ b*/f, b*/e +/ c*/f)
 
let rec pow a n =
  if n=1 then a else
    let b = pow a (n/2) in
    if (n mod 2) = 0 then mul b b else mul a (mul b b)
 
let fib n =
  let (_,y,_) = (pow (Int 1, Int 1, Int 0) n) in
  string_of_num y
;;
Printf.printf "fib %d = %s\n" 300 (fib 300)

Output:

fib 300 = 22223224462942044552973989346190996720666693909649976499097960

Octave

Recursive

% recursive
function fibo = recfibo(n)
  if ( n < 2 )
    fibo = n;
  else
    fibo = recfibo(n-1) + recfibo(n-2);
  endif
endfunction

Iterative

% 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

Testing

% testing
for i = 0 : 20
  printf("%d %d\n", iterfibo(i), recfibo(i));
endfor

OPL

FIBON:
REM Fibonacci sequence is generated to the Organiser II floating point variable limit.
REM This method was derived from (not copied...) the original OPL manual that came with the CM and XP in the mid 1980s.
REM CLEAR/ON key quits.
REM Mikesan - http://forum.psion2.org/
LOCAL A,B,C
A=1 :B=1 :C=1
PRINT A,
DO
  C=A+B
  A=B
  B=C
  PRINT A,
UNTIL GET=1

Order

Recursive

#include <order/interpreter.h>
 
#define ORDER_PP_DEF_8fib_rec                     \
ORDER_PP_FN(8fn(8N,                               \
                8if(8less(8N, 2),                 \
                    8N,                           \
                    8add(8fib_rec(8sub(8N, 1)),   \
                         8fib_rec(8sub(8N, 2))))))
 
ORDER_PP(8fib_rec(10))

Tail recursive version (example supplied with language):

#include <order/interpreter.h>
 
#define ORDER_PP_DEF_8fib                                         \
ORDER_PP_FN(8fn(8N,                                               \
                8fib_iter(8N, 0, 1)))
 
#define ORDER_PP_DEF_8fib_iter                                    \
ORDER_PP_FN(8fn(8N, 8I, 8J,                                       \
                8if(8is_0(8N),                                    \
                    8I,                                           \
                    8fib_iter(8dec(8N), 8J, 8add(8I, 8J)))))
 
ORDER_PP(8to_lit(8fib(8nat(5,0,0))))

Memoization

#include <order/interpreter.h>
 
#define ORDER_PP_DEF_8fib_memo                                    \
ORDER_PP_FN(8fn(8N,                                               \
                8tuple_at(0, 8fib_memo_inner(8N, 8seq))))
 
 
#define ORDER_PP_DEF_8fib_memo_inner                                            \
ORDER_PP_FN(8fn(8N, 8M,                                                         \
                8cond((8less(8N, 8seq_size(8M)), 8pair(8seq_at(8N, 8M), 8M))    \
                      (8equal(8N, 0), 8pair(0, 8seq(0)))                        \
                      (8equal(8N, 1), 8pair(1, 8seq(0, 1)))                     \
                      (8else,                                                   \
                        8lets((8S, 8fib_memo_inner(8sub(8N, 2), 8M))            \
                              (8T, 8fib_memo_inner(8dec(8N), 8tuple_at(1, 8S))) \
                              (8U, 8add(8tuple_at(0, 8S), 8tuple_at(0, 8T))),   \
                              8pair(8U,                                         \
                                    8seq_append(8tuple_at(1, 8T), 8seq(8U))))))))
 
 
ORDER_PP(
8for_each_in_range(8fn(8N,
                       8print(8to_lit(8fib_memo(8N)) (,) 8space)),
                   1, 21)
)

Oz

Iterative

Using mutable references (cells).

fun{FibI N}
  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
end

Recursive

Inefficient (blows up the stack).

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

Tail-recursive

Using accumulators.

fun{Fib N}
   fun{Loop N A B}
      if N == 0 then
	 B
      else
	 {Loop N-1 A+B A}
      end
   end
in    
   {Loop N 1 0}
end

Lazy-recursive

declare
  fun lazy {FiboSeq}
     {LazyMap
      {Iterate fun {$ [A B]} [B A+B] end [0 1]}
      Head}
  end
 
  fun {Head A|_} A end
 
  fun lazy {Iterate F I}
     I|{Iterate F {F I}}
  end
 
  fun lazy {LazyMap Xs F}
     case Xs of X|Xr then {F X}|{LazyMap Xr F}
     [] nil then nil
     end
  end
in
  {Show {List.take {FiboSeq} 8}}

PARI/GP

Built-in

fibonocci(n)

Matrix

([1,1;1,0]^n)[1,2]

Analytic

This uses the Binet form.

fib(n)=my(phi=(1+sqrt(5))/2);round((phi^n-phi^-n)/sqrt(5))

The second term can be dropped since the error is always small enough to be subsumed by the rounding.

fib(n)=round(((1+sqrt(5))/2)^n/sqrt(5))

Algebraic

This is an exact version of the above formula. quadgen(5) represents φ and the number is stored in the form a + bφ. imag takes the coefficient of φ. This uses the relation

φⁿ = F_{n − 1} + F_nφ

and hence real(quadgen(5)^n) would give the (n-1)-th Fibonacci number.

fib(n)=imag(quadgen(5)^n)

A more direct translation (note that $\sqrt5=2\phi-1$) would be

fib(n)=my(phi=quadgen(5));(phi^n-(-1/phi)^n)/(2*phi-1)

Combinatorial

This uses the generating function. It can be trivially adapted to give the first n Fibonacci numbers.

fib(n)=polcoeff(x/(1-x-x^2)+O(x^(n+1)),n)

Binary powering

fib(n)={
  if(n<=0,
    if(n,(-1)^(n+1)*fib(n),0)
  ,
    my(v=lucas(n-1));
    (2*v[1]+v[2])/5
  )
};
lucas(n)={
  if (!n, return([2,1]));
  my(v=lucas(n >> 1), z=v[1], t=v[2], pr=v[1]*v[2]);
  n=n%4;
  if(n%2,
    if(n==3,[v[1]*v[2]+1,v[2]^2-2],[v[1]*v[2]-1,v[2]^2+2])
  ,
    if(n,[v[1]^2+2,v[1]*v[2]+1],[v[1]^2-2,v[1]*v[2]-1])
  )
};

Recursive

fib(n)={
  if(n<2,
    if(n<0,
      (-1)^(n+1)*fib(n)
    ,
      n
    )
  ,
    fib(n-1)+fib(n)
  )
};

Iterative

fib(n)={
  if(n<0,return((-1)^(n+1)*fib(n)));
  my(a=0,b=1,t);
  while(n,
    t=a+b;
    a=b;
    b=t;
    n--
  );
  a
};

One-by-one

This code is purely for amusement and requires n > 1. It tests numbers in order to see if they are Fibonacci numbers, and waits until it has seen n of them.

fib(n)=my(k=0);while(n--,k++;while(!issquare(5*k^2+4)&&!issquare(5*k^2-4),k++));k

Pascal

Recursive

function fib(n: integer): integer;
 begin
  if (n = 0) or (n = 1)
   then
    fib := n
   else
    fib := fib(n-1) + fib(n-2)
 end;

Iterative

function fib(n: integer): integer;
 var
  f0, f1, f2, k: integer;
 begin
  f0 := 0;
  f1 := 1;
  for k := 2 to n do
   begin
    f2:= f0 + f1;
    f0 := f1;
    f1 := f2;
   end;
  fib := f2;
 end;

Perl

Iterative

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

Recursive

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

Perl 6

Works with: Rakudo version #21 "Seattle"

Iterative

sub fib (Int $n --> Int) {
    $n > 1 or return $n;
    my ($prev, $this) = 0, 1;
    ($prev, $this) = $this, $this + $prev for 1 ..^ $n;
    return $this;
}

Recursive

proto fib (Int $n --> Int) {*}
multi fib (0)  { 0 }
multi fib (1)  { 1 }
multi fib ($n) { fib($n - 1) + fib($n - 2) }

(Unfortunately, rakudo does not yet implement the is cached trait, so this remains an inefficient solution.)

Analytic

sub fib (Int $n --> Int) {
    constant φ1 = 1 / constant φ = (1 + sqrt 5)/2;
    constant invsqrt5 = 1 / sqrt 5;
 
    floor invsqrt5 * (φ**$n + φ1**$n);
}

List Generator (built in)

Works with: Rakudo Star

This constructs the fibonacci sequence as a lazy infinite array.

my @fib := 0, 1, *+* ... *;

If you really need a function for it:

sub fib ($n) { @fib[$n] }

To support negative indices:

my @neg_fib := 0, 1, *-* ... *;
sub fib ($n) { $n >= 0 and @fib[$n] or @neg_fib[-$n]; }

PHP

Iterative

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;
}

Recursive

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

PicoLisp

Recursive

(de fibo (N)
   (if (>= 2 N)
      1
      (+ (fibo (dec N)) (fibo (- N 2))) ) )

Recursive with Cache

Using a recursive version doesn't need to be slow, as the following shows:

(de fibo (N)
   (cache '(NIL) (pack (char (hash N)) N)  # Use a cache to accelerate
      (if (>= 2 N)
         N
         (+ (fibo (dec N)) (fibo (- N 2))) ) ) )
 
(bench (fibo 1000))

Output:

0.012 sec
-> 43466557686937456435688527675040625802564660517371780402481729089536555417949
05189040387984007925516929592259308032263477520968962323987332247116164299644090
6533187938298969649928516003704476137795166849228875

Iterative

Recursive can only go so far until a stack overflow brings the whole thing crashing down.

(de fibo (N)
   (let (I 1 J 0)
      (do N
         (let (Tmp J)
            (inc 'J I)
            (setq I Tmp) ) )
      J) )

PIR

Recursive:

Works with: Parrot version tested with 2.4.0

.sub fib
  .param int n
  .local int nt
  .local int ft
  if n < 2 goto RETURNN
  nt = n - 1
  ft = fib( nt )
  dec nt
  nt = fib(nt)
  ft = ft + nt
  .return( ft )
RETURNN:
  .return( n )
  end
.end
 
.sub main :main
  .local int counter
  .local int f
  counter=0
LOOP: 
  if counter > 20 goto DONE
  f = fib(counter)
  print f
  print "\n"
  inc counter
  goto LOOP
DONE:
  end
.end

Iterative (stack-based):

Works with: Parrot version tested with 2.4.0

.sub fib
  .param int n
  .local int counter
  .local int f
  .local pmc fibs
  .local int nmo
  .local int nmt
 
  fibs = new 'ResizableIntegerArray'
  if n == 0 goto RETURN0
  if n == 1 goto RETURN1
  push fibs, 0
  push fibs, 1
  counter = 2
FIBLOOP:
  if counter > n goto DONE
  nmo = pop fibs
  nmt = pop fibs
  f = nmo + nmt
  push fibs, nmt
  push fibs, nmo
  push fibs, f
  inc counter
  goto FIBLOOP
RETURN0:
  .return( 0 )
  end
RETURN1:
  .return( 1 )
  end
DONE:
  f = pop fibs
  .return( f )
  end
.end
 
.sub main :main
  .local int counter
  .local int f
  counter=0
LOOP: 
  if counter > 20 goto DONE
  f = fib(counter)
  print f
  print "\n"
  inc counter
  goto LOOP
DONE:
  end
.end

Pike

Iterative

int     
fibIter(int n) {
    int fibPrev, fib, i;
    if (n < 2) {
        return 1;
    }
    fibPrev = 0;
    fib = 1;
    for (i = 1; i < n; i++) {
        int oldFib = fib;
        fib += fibPrev;
        fibPrev = oldFib;
    }
    return fib;
}

Recursive

int 
fibRec(int n) {
    if (n < 2) {
        return(1);
    }
    return( fib(n-2) + fib(n-1) );
}

PL/I

/* Form the n-th Fibonacci number, n > 1. */
get list (n);
f1 = 0; f2, f3 = 1;
do i = 1 to n-2;
   f3 = f1 + f2;
   f1 = f2;
   f2 = f3;
end;
put skip list (f3);

PL/SQL

Create or replace Function fnu_fibonnaci(p_iNumber integer)
return integer
is
  nuFib  integer;
  nuP  integer;
  nuQ  integer;
Begin
  if p_iNumber is not null then
     if p_iNumber=0 then
        nuFib:=0;
     Elsif p_iNumber=1 then
            nuFib:=1;
     Else
        nuP:=0;
        nuQ:=1;
        For nuI in 2..p_iNumber loop
            nuFib:=nuP+nuQ;
            nuP:=nuQ;
            nuQ:=nuFib;
        End loop;
     End if;
  End if;
  return(nuFib);
End fnu_fibonnaci;

Pop11

define fib(x);
lvars a , b;
    1 -> a;
    1 -> b;
    repeat x - 1 times
         (a + b, b) -> (b, a);
    endrepeat;
    a;
enddefine;

PostScript

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

%!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

PowerBASIC

Translation of: BASIC

There seems to be a limitation (dare I say, bug?) in PowerBASIC regarding how large numbers are stored. 10E17 and larger get rounded to the nearest 10. For F(n), where ABS(n) > 87, is affected like this:

      actual:             displayed:
F(88) 1100087778366101931 1100087778366101930
F(89) 1779979416004714189 1779979416004714190
F(90) 2880067194370816120 2880067194370816120
F(91) 4660046610375530309 4660046610375530310
F(92) 7540113804746346429 7540113804746346430

FUNCTION fibonacci (n AS LONG) AS QUAD
    DIM u AS LONG, a AS LONG, L0 AS LONG, outP AS QUAD
    STATIC fibNum() AS QUAD
 
    u = UBOUND(fibNum)
    a = ABS(n)
 
    IF u < 1 THEN
        REDIM fibNum(1)
        fibNum(1) = 1
        u = 1
    END IF
 
    SELECT CASE a
        CASE 0 TO 92
            IF a > u THEN
                REDIM PRESERVE fibNum(a)
                FOR L0 = u + 1 TO a
                    fibNum(L0) = fibNum(L0 - 1) + fibNum(L0 - 2)
                    IF 88 = L0 THEN fibNum(88) = fibNum(88) + 1
                NEXT
            END IF
            IF n < 0 THEN
                fibonacci = fibNum(a) * ((-1)^(a+1))
            ELSE
                fibonacci = fibNum(a)
            END IF
        CASE ELSE
            'Even without the above-mentioned bug, we're still limited to
            'F(+/-92), due to data type limits. (F(93) = &hA94F AD42 221F 2702)
            ERROR 6
    END SELECT
END FUNCTION
 
FUNCTION PBMAIN () AS LONG
    DIM n AS LONG
    #IF NOT %DEF(%PB_CC32)
        OPEN "out.txt" FOR OUTPUT AS 1
    #ENDIF
    FOR n = -92 TO 92
        #IF %DEF(%PB_CC32)
            PRINT STR$(n); ": "; FORMAT$(fibonacci(n), "#")
        #ELSE
            PRINT #1, STR$(n) & ": " & FORMAT$(fibonacci(n), "#")
        #ENDIF
    NEXT
    CLOSE
END FUNCTION

PowerShell

Iterative

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
}

Recursive

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

Prolog

Works with: SWI Prolog

Works with: GNU Prolog

Works with: YAP

 
fib(1, 1) :- !.
fib(0, 0) :- !.
fib(N, Value) :-
  A is N - 1, fib(A, A1),
  B is N - 2, fib(B, B1),
  Value is A1 + B1.
 

This naive implementation works, but is very slow for larger values of N. Here are some simple measurements (in SWI-Prolog):

?- time(fib(0,F)).
% 2 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 161943 Lips)
F = 0.
 
?- time(fib(10,F)).
% 265 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1458135 Lips)
F = 55.
 
?- time(fib(20,F)).
% 32,836 inferences, 0.016 CPU in 0.016 seconds (99% CPU, 2086352 Lips)
F = 6765.
 
?- time(fib(30,F)).
% 4,038,805 inferences, 1.122 CPU in 1.139 seconds (98% CPU, 3599899 Lips)
F = 832040.
 
?- time(fib(40,F)).
% 496,740,421 inferences, 138.705 CPU in 140.206 seconds (99% CPU, 3581264 Lips)
F = 102334155.

As you can see, the calculation time goes up exponentially as N goes higher.

Poor man's memoization

Works with: SWI Prolog

Works with: YAP

Works with: GNU Prolog

The performance problem can be readily fixed by the addition of two lines of code (the first and last in this version):

%:- dynamic fib/2.  % This is ISO, but GNU doesn't like it.
:- dynamic(fib/2).  % Not ISO, but works in SWI, YAP and GNU unlike the ISO declaration.
fib(1, 1) :- !.
fib(0, 0) :- !.
fib(N, Value) :-
  A is N - 1, fib(A, A1),
  B is N - 2, fib(B, B1),
  Value is A1 + B1,
  asserta((fib(N, Value) :- !)).

Let's take a look at the execution costs now:

?- time(fib(0,F)).
% 2 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 160591 Lips)
F = 0.
 
?- time(fib(10,F)).
% 37 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 552610 Lips)
F = 55.
 
?- time(fib(20,F)).
% 41 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 541233 Lips)
F = 6765.
 
?- time(fib(30,F)).
% 41 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 722722 Lips)
F = 832040.
 
?- time(fib(40,F)).
% 41 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 543572 Lips)
F = 102334155.

In this case by asserting the new N,Value pairing as a rule in the database we're making the classic time/space tradeoff. Since the space costs are (roughly) linear by N and the time costs are exponential by N, the trade-off is desirable. You can see the poor man's memoizing easily:

?- listing(fib).
:- dynamic fib/2.
 
fib(40, 102334155) :- !.
fib(39, 63245986) :- !.
fib(38, 39088169) :- !.
fib(37, 24157817) :- !.
fib(36, 14930352) :- !.
fib(35, 9227465) :- !.
fib(34, 5702887) :- !.
fib(33, 3524578) :- !.
fib(32, 2178309) :- !.
fib(31, 1346269) :- !.
fib(30, 832040) :- !.
fib(29, 514229) :- !.
fib(28, 317811) :- !.
fib(27, 196418) :- !.
fib(26, 121393) :- !.
fib(25, 75025) :- !.
fib(24, 46368) :- !.
fib(23, 28657) :- !.
fib(22, 17711) :- !.
fib(21, 10946) :- !.
fib(20, 6765) :- !.
fib(19, 4181) :- !.
fib(18, 2584) :- !.
fib(17, 1597) :- !.
fib(16, 987) :- !.
fib(15, 610) :- !.
fib(14, 377) :- !.
fib(13, 233) :- !.
fib(12, 144) :- !.
fib(11, 89) :- !.
fib(10, 55) :- !.
fib(9, 34) :- !.
fib(8, 21) :- !.
fib(7, 13) :- !.
fib(6, 8) :- !.
fib(5, 5) :- !.
fib(4, 3) :- !.
fib(3, 2) :- !.
fib(2, 1) :- !.
fib(1, 1) :- !.
fib(0, 0) :- !.
fib(A, D) :-
	B is A+ -1,
	fib(B, E),
	C is A+ -2,
	fib(C, F),
	D is E+F,
	asserta((fib(A, D):-!)).

All of the interim N/Value pairs have been asserted as facts for quicker future use, speeding up the generation of the higher Fibonacci numbers.

Continuation passing style

Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl

:- use_module(lambda).
fib(N, FN) :-
	cont_fib(N, _, FN, \_^Y^_^U^(U = Y)).
 
cont_fib(N, FN1, FN, Pred) :-
	(   N < 2 ->
	    call(Pred, 0, 1, FN1, FN)
	;
	    N1 is N - 1,
	    P = \X^Y^Y^U^(U is X + Y),
	    cont_fib(N1, FNA, FNB, P),
	    call(Pred, FNA, FNB, FN1, FN)
	).
 

With lazy lists

Works with SWI-Prolog and others that support freeze/2. Attributed to WillNess

fib(X) :-
    X=[0,1|Z],
    ffib(Z,X).
ffib(Z,X) :-
    X=[A|Y],
    Y=[B|_],
    N is A+B,
    freeze(Z, (Z=[N|W],ffib(W,Y)) ).
 

The predicate fib(Xs) unifies Xs with an infinite list whose values are the Fibonacci sequence. The list can be used like this:

?- fib(X), length(A,15), append(A,_,X), writeln(A).
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
 

Yet another implementation

One of my favorites; loosely similar to the first example, but without the performance penalty, and needs nothing special to implement. Not even a dynamic database predicate. Attributed to M.E. for the moment, but simply because I didn't bother to search for the many people who probably did it like this long before I did. If someone knows who came up with it first, please let us know.

% Fibonacci sequence generator
fib(C, [P,S], C, N)  :- N is P + S.
fib(C, [P,S], Cv, V) :- succ(C, Cn), N is P + S, !, fib(Cn, [S,N], Cv, V).
 
fib(0, 0).
fib(1, 1).
fib(C, N) :- fib(2, [0,1], C, N). % Generate from 3rd sequence on

Looking at performance:

 ?- time(fib(30,X)).
% 86 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 832040 
 ?- time(fib(40,X)).
% 116 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 102334155
 ?- time(fib(100,X)).
% 296 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
X = 354224848179261915075 

What I really like about this one, is it is also a generator- i.e. capable of generating all the numbers in sequence needing no bound input variables or special Prolog predicate support (such as freeze/3 in the previous example):

?- time(fib(X,Fib)).
% 0 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = Fib, Fib = 0 ;
% 1 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = Fib, Fib = 1 ;
% 3 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 2,
Fib = 1 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 3,
Fib = 2 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 4,
Fib = 3 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = Fib, Fib = 5 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 6,
Fib = 8
...etc.

It stays at 5 inferences per iteration after X=3. Also, quite useful:

 ?- time(fib(100,354224848179261915075)).
% 296 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
true .

?- time(fib(X,354224848179261915075)).
% 394 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = 100 .

Pure

Tail Recursive

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

PureBasic

Macro based calculation

Macro Fibonacci (n)
	Int((Pow(((1+Sqr(5))/2),n)-Pow(((1-Sqr(5))/2),n))/Sqr(5))
EndMacro

Recursive

Procedure FibonacciReq(n)
  If n<2
    ProcedureReturn n
  Else
    ProcedureReturn FibonacciReq(n-1)+FibonacciReq(n-2)
  EndIf
EndProcedure

Recursive & optimized with a static hash table

This will be much faster on larger n's, this as it uses a table to store known parts instead of recalculating them. On my machine the speedup compares to above code is

Fib(n) Speedup
20           2
25          23
30         217
40       25847
46     1156741

Procedure Fibonacci(n)
  Static NewMap Fib.i()
  Protected FirstRecursion
 
  If MapSize(Fib())= 0        ; Init the hash table the first run
    Fib("0")=0: Fib("1")=1
    FirstRecursion = #True
  EndIf
 
  If n >= 2
    Protected.s s=Str(n)
    If Not FindMapElement(Fib(),s)  ; Calculate only needed parts
      Fib(s)= Fibonacci(n-1)+Fibonacci(n-2)
    EndIf
    n = Fib(s)  
  EndIf
  If FirstRecursion ; Free the memory when finalizing the first call
    ClearMap(Fib())
  EndIf
  ProcedureReturn n
EndProcedure

Example

Fibonacci(0)= 0
Fibonacci(1)= 1
Fibonacci(2)= 1
Fibonacci(3)= 2
Fibonacci(4)= 3
Fibonacci(5)= 5

FibonacciReq(0)= 0
FibonacciReq(1)= 1
FibonacciReq(2)= 1
FibonacciReq(3)= 2
FibonacciReq(4)= 3
FibonacciReq(5)= 5

Purity

The following takes a natural number and generates an initial segment of the Fibonacci sequence of that length:

 
data Fib1 = FoldNat 
            <
              const (Cons One (Cons One Empty)),
              (uncurry Cons) . ((uncurry Add) . (Head, Head . Tail), id)
            >
 

This following calculates the Fibonacci sequence as an infinite stream of natural numbers:

 
type (Stream A?,,,Unfold) = gfix X. A? . X?
data Fib2 = Unfold ((outl, (uncurry Add, outl))) ((curry id) One One)
 

As a histomorphism:

 
import Histo
 
data Fib3 = Histo . Memoize 
            <
              const One, 
              (p1 => 
              <
                const One, 
                (p2 => Add (outl $p1) (outl $p2)). UnmakeCofree
              > (outr $p1)) . UnmakeCofree
            >
 

Python

Analytic

from math import *
 
def analytic_fibonacci(n):
  sqrt_5 = sqrt(5);
  p = (1 + sqrt_5) / 2;
  q = 1/p;
  return int( (p**n + q**n) / sqrt_5 + 0.5 )
 
for i in range(1,31):
  print analytic_fibonacci(i),

Output:

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

Iterative

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

Recursive

def fibRec(n):
    if n < 2:
        return n
    else:
        return fibRec(n-1) + fibRec(n-2)

Recursive with Memoization

def fibMemo():
    pad = {0:0, 1:1}
    def func(n):
        if n not in pad:
            pad[n] = func(n-1) + func(n-2)
        return pad[n]
    return func
 
fm = fibMemo()
for i in range(1,31):
    print fm(i),

Output:

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

Generative

def fibGen():
    f0, f1 = 0, 1
    while True:
        yield f0
        f0, f1 = f1, f0+f1

Example use

>>> fg = fibGen()
>>> for x in range(9): 
    print fg.next()
 
0
1
1
2
3
5
8
13
21
>>>

Qi

Recursive

 
(define fib
  0 -> 0
  1 -> 1
  N -> (+ (fib-r (- N 1))
          (fib-r (- N 2))))
 

Iterative

 
(define fib-0
  V2 V1 0 -> V2
  V2 V1 N -> (fib-0 V1 (+ V2 V1) (1- N)))
 
(define fib
  N -> (fib-0 0 1 N))
 

R

# recursive
recfibo <- function(n) {
  if ( n < 2 ) n
  else Recall(n-1) + Recall(n-2)
}
 
# print the first 21 elements
print.table(lapply(0:20, recfibo))
 
# iterative
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]
  }
}
 
print.table(lapply(0:20, iterfibo))
 
# iterative but looping replaced by map-reduce'ing
funcfibo <- function(n) {
  if (n < 2) 
    n
  else {
    generator <- function(f, ...) {
      c(f[2], sum(f))
    }
    Reduce(generator, 2:n, c(0,1))[2]
  }
}
 
print.table(lapply(0:20, funcfibo))

Note that an idiomatic way to implement such low level, basic arithmethic operations in R is to implement them C and then call the compiled code.

Output:

All three solutions print

 [1] 0    1    1    2    3    5    8    13   21   34   55   89   144  233  377 
[16] 610  987  1597 2584 4181 6765

Racket

Tail Recursive

 
(define (fibo number)
  (define (fibo-rec number n i)
    (if (<= number 0)
        i   
        (fibo-rec (- number 1) (+ n i) n)))
  (fibo-rec number 1 0))
 

REALbasic

Pass n to this function where n is the desired number of iterations. This example uses the UInt64 datatype which is as unsigned 64 bit integer. As such, it overflows after the 92nd iteration.

Function fibo(n as integer) As UInt64
 
  dim noOne as UInt64 = 1
  dim noTwo as UInt64 = 1	
  dim sum As UInt64
 
  for i as integer = 1 to n
      sum = noOne + noTwo
      noTwo = noOne
      noOne = sum
  Next
 
  Return noOne
End Function

Retro

Recursive

: fib ( n-m ) dup [ 0 = ] [ 1 = ] bi or if; [ 1- fib ] sip [ 2 - fib ] do + ;

Iterative

: fib ( n-N )
  [ 0 1 ] dip [ over + swap ] times drop ;

REXX

With 210,000 numeric digits, this REXX program can handle Fibonacci numbers past one million.
[Generally speaking, REXX can handle up to around 8 million digits.]

This version of the REXX program can also handle negative Fibonacci numbers.

/*REXX program calculates the Nth Fibonacci number, N can be zero or neg*/
numeric digits 210000                  /*prepare for some big 'uns.     */
parse arg x y .                        /*allow a single number or range.*/
if x=='' then do; x=-40; y=abs(x); end /*No input? Use range -40 ──► +40*/
if y=='' then y=x                      /*if only one number, show fib(n)*/
w=max(length(x),length(y))             /*used for making output pretty. */
fw=10                                  /*minmum maximum width.   Ka-razy*/
      do j=x to y;   q=fib(j)          /*process each Fibonacci request.*/
      fw=max(fw,length(q))             /*fib# length or the max so far. */
      say 'Fibonacci('right(j,w)") = " right(q,fw)   /*right justify  Q.*/
      if length(q)>10 then say 'Fibonacci('right(j,w)") has a length of" l
      end   /*j*/
exit                                   /*stick a fork in it, we're done.*/
/*─────────────────────────────────────FIB subroutine (non-recursive)───*/
fib:  procedure;    parse arg n;     na=abs(n);     a=0;     b=1
if na<2 then return na                 /*handle couple of special cases.*/
 
      do k=2 to na;    s=a+b           /*sum  the numbers  up to  │n│   */
      parse value  b s  with  a b      /*faster version of:   a=b;  s=b */
      end   /*k*/
 
if n>0 | na//2==1  then  return  s     /*if positive or odd negative ...*/
                         return -s     /*  return a negative Fib number.*/

output using the default input:

Fibonacci(-40) =  -102334155
Fibonacci(-39) =    63245986
Fibonacci(-38) =   -39088169
Fibonacci(-37) =    24157817
Fibonacci(-36) =   -14930352
Fibonacci(-35) =     9227465
Fibonacci(-34) =    -5702887
Fibonacci(-33) =     3524578
Fibonacci(-32) =    -2178309
Fibonacci(-31) =     1346269
Fibonacci(-30) =     -832040
Fibonacci(-29) =      514229
Fibonacci(-28) =     -317811
Fibonacci(-27) =      196418
Fibonacci(-26) =     -121393
Fibonacci(-25) =       75025
Fibonacci(-24) =      -46368
Fibonacci(-23) =       28657
Fibonacci(-22) =      -17711
Fibonacci(-21) =       10946
Fibonacci(-20) =       -6765
Fibonacci(-19) =        4181
Fibonacci(-18) =       -2584
Fibonacci(-17) =        1597
Fibonacci(-16) =        -987
Fibonacci(-15) =         610
Fibonacci(-14) =        -377
Fibonacci(-13) =         233
Fibonacci(-12) =        -144
Fibonacci(-11) =          89
Fibonacci(-10) =         -55
Fibonacci( -9) =          34
Fibonacci( -8) =         -21
Fibonacci( -7) =          13
Fibonacci( -6) =          -8
Fibonacci( -5) =           5
Fibonacci( -4) =          -3
Fibonacci( -3) =           2
Fibonacci( -2) =          -1
Fibonacci( -1) =           1
Fibonacci(  0) =           0
Fibonacci(  1) =           1
Fibonacci(  2) =           1
Fibonacci(  3) =           2
Fibonacci(  4) =           3
Fibonacci(  5) =           5
Fibonacci(  6) =           8
Fibonacci(  7) =          13
Fibonacci(  8) =          21
Fibonacci(  9) =          34
Fibonacci( 10) =          55
Fibonacci( 11) =          89
Fibonacci( 12) =         144
Fibonacci( 13) =         233
Fibonacci( 14) =         377
Fibonacci( 15) =         610
Fibonacci( 16) =         987
Fibonacci( 17) =        1597
Fibonacci( 18) =        2584
Fibonacci( 19) =        4181
Fibonacci( 20) =        6765
Fibonacci( 21) =       10946
Fibonacci( 22) =       17711
Fibonacci( 23) =       28657
Fibonacci( 24) =       46368
Fibonacci( 25) =       75025
Fibonacci( 26) =      121393
Fibonacci( 27) =      196418
Fibonacci( 28) =      317811
Fibonacci( 29) =      514229
Fibonacci( 30) =      832040
Fibonacci( 31) =     1346269
Fibonacci( 32) =     2178309
Fibonacci( 33) =     3524578
Fibonacci( 34) =     5702887
Fibonacci( 35) =     9227465
Fibonacci( 36) =    14930352
Fibonacci( 37) =    24157817
Fibonacci( 38) =    39088169
Fibonacci( 39) =    63245986
Fibonacci( 40) =   102334155

output when the following was used as input: 10000

Fibonacci(10000) =  3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958298727968298751063120057542878345321551510387081829896979161312785626503319548714021428753269818796204693609787990035096230229102636813149319527563022783762844154036058440257211433496118002309120828704608892396232883546150577658327125254609359112820392528539343462090424524892940390
170623388899108584106518317336043747073790855263176432573399371287193758774689747992630583706574283016163740896917842637862421283525811282051637029808933209990570792006436742620238978311147005407499845925036063356093388383192338678305613643535189213327973290813373264265263398976392272340788292817795358057099369104917547080893184105614632233821746563732124822638309210329770164805472624384237486241145309381220656491403275108664339451751216152654536133311131404243685480510676584349352383695965342807176877532834823434555736671973139274627362910821067928078471803532913117677892465908993863545932789
452377767440619224033763867400402133034329749690202832814593341882681768389307200363479562311710310129195316979460763273758925353077255237594378843450406771555577905645044301664011946258097221672975861502696844314695203461493229110597067624326851599283470989128470674086200858713501626031207190317208609408129832158107728207635318662461127824553720853236530577595643007251774431505153960090516860322034916322264088524885243315805153484962243484829938090507048348244932745373262456775587908918719080366205800959474315005240253270974699531877072437682590741993963226598414749819360928522394503970716544
3156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
Fibonacci(10000) has a length of 2090

Ruby

Iterative

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

Recursive

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

Recursive with Memoization

# Use the Hash#default_proc feature to
# lazily calculate the Fibonacci numbers.
 
fib = Hash.new do |f, n|
  f[n] = if n <= -2
           (-1)**(n+1) * f[n.abs]
         elsif n <= 1
           n.abs
         else
           f[n-1] + f[n-2]
         end
end
# examples: fib[10] => 55, fib[-10] => (-55/1)

Matrix

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

Generative

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

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." [2]

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}

using a lambda

def fib_gen
    a, b = 1, 1
    lambda {ret, a, b = a, b, a+b; ret}
end

irb(main):034:0> fg = fib_gen
=> #<Proc:0xb7cdf750@(irb):22>
irb(main):035:0> 9.times { puts fg.call}
1
1
2
3
5
8
13
21
34
=> 9

Binet's Formula

def fib
    phi = (1 + Math.sqrt(5)) / 2
    ((phi**self - (-1 / phi)**self) / Math.sqrt(5)).to_i
end

1.9.3p125 :001 > def fib
1.9.3p125 :002?>   phi = (1 + Math.sqrt(5)) / 2
1.9.3p125 :003?>   ((phi**self - (-1 / phi)**self) / Math.sqrt(5)).to_i
1.9.3p125 :004?>   end
 => nil 
1.9.3p125 :005 > (0..10).map(&:fib)
 => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Run BASIC

for i = 0 to 10
 print i;" ";fibR(i);" ";fibI(i)
next i
end
 
 function fibR(n)
 if n < 2 then fibR = n else fibR = fibR(n-1) + fibR(n-2)
 end function
 
 function fibI(n)
   b = 1
   for i = 1 to n
       t = a + b
       a = b
       b = t
   next i
fibI = a
end function

Rust

Iterative

 
fn fib(n: int, f: fn (num: i64) -> bool) -> (i64, int) {
    if n < 0 {
        // Let these variables be mutated, otherwise too slow
        let mut n1:i64 = 0, n2:i64 = -1, i:int = 0, tmp:i64;
        while i > n {
            f(n1);
            tmp = n1-n2;
            if (tmp > 0 && n2 > 0) { //Detect overflow
                io::println("\nReached the limit of i64, halting");
                return (n1, i);
            }
            n1 = n2;
            n2 = tmp;
            i -= 1;
        }
        (n1+n2, n)
    } else if n > 0 {
        // And these variables
        let mut n1:i64 = 0, n2:i64 = 1, i:int = 0, tmp:i64;
        while i < n {
            f(n1);
            tmp = n1+n2;
            if (tmp < 0) { //Detect overflow
                io::println("\nReached the limit of i64, halting");
                return (n1, i);
            }
            n1 = n2;
            n2 = tmp;
            i += 1;
        }
        (n2-n1, n)
    } else {
        f(0);
        (0,1)
    }
}
 
fn main() {
    let args = os::args();
    let n = if args.len() == 1 {
        10
    } else if args.len() > 1 {
        // Convert from a string
        match (int::from_str(args[1])) {
            Some(num)   => num,
            None        => 10 //Fall back to default
        }
    } else {
        /* Required to use the if as an expression.
         * We know that args.len() is always >= 1, the compiler
         * does not. fail lets it know that we can't get past here.
         */
        fail ~"No arguments given, somehow...";
    };
 
    /* Use the loop protocol to be able to do things
     * with the sequence given, in this case, print them out.
     * The loop itself returns a tuple with where it got to and
     * what the number is.
     */
    let (result, n) = for fib(n) |num| {
        //print out the sequence
        io::print(fmt!("%? ", num));
    };
 
    io::println(fmt!("\nThe %dth fibonacci number is: %?", n, result));
}
 

Recursive

Minimalist tail-recursive version, no overflow checking:

fn main() {
 
   fn fib(n: int) -> int {
 
     fn _fib(n: int, a: int, b: int) -> int {
       match (n, a, b) {
	 (0, _, _) => a,
	 _         => _fib(n-1, a+b, a)
       }
     }
 
     _fib(n, 0, 1)
 
   }
 
   for int::range(0,20) |n| {
     io::println(fmt!("%?", fib(n)))
   }
}

SAS

/* building a table with fibonacci sequence */
data fib;
a=0;
b=1;
do n=0 to 20;
   f=a;
   output;
   a=b;
   b=f+a;
end;
keep n f;
run;
 

Sather

The implementations use the arbitrary precision class INTI.

class MAIN is
 
  -- RECURSIVE --
  fibo(n :INTI):INTI
    pre n >= 0
  is
    if n < 2.inti then return n; end;
    return fibo(n - 2.inti) + fibo(n - 1.inti);
  end;
 
  -- ITERATIVE --
  fibo_iter(n :INTI):INTI
    pre n >= 0
  is
    n3w :INTI;
 
    if n < 2.inti then return n; end;
    last ::= 0.inti; this ::= 1.inti;
    loop (n - 1.inti).times!;
      n3w := last + this;
      last := this;
      this := n3w;
    end;   
    return this;
  end;
 
  main is
    loop i ::= 0.upto!(16);
      #OUT + fibo(i.inti) + " ";
      #OUT + fibo_iter(i.inti) + "\n";
    end;
  end;
 
end;

Scala

Recursive

def fib(i:Int):Int = i match{
    case 0 => 0
    case 1 => 1
    case _ => fib(i-1) + fib(i-2)
}

Lazy sequence

//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}

Following code works in Scala 2.8:

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

Tail recursive

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

foldLeft

// Fibonacci using BigInt with Stream.foldLeft optimized for GC (Scala v2.9 and above)
// Does not run out of memory for very large Fibonacci numbers 
def fib(n:Int) = {
 
  def series(i:BigInt,j:BigInt):Stream[BigInt] = i #:: series(j, i+j)
 
  series(1,0).take(n).foldLeft(BigInt("0"))(_+_)
}
 
// Small test
(0 to 13) foreach {n => print(fib(n).toString + " ")}
 
// result: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 
 

Scheme

Iterative

(define (fib-iter n)
  (do ((num 2 (+ num 1))
       (fib-prev 1 fib)
       (fib 1 (+ fib fib-prev)))
      ((>= num n) fib)))

Recursive

(define (fib-rec n)
  (if (< n 2)
      n
      (+ (fib-rec (- n 1))
         (fib-rec (- n 2)))))

This version is tail recursive:

(define (fib n)
  (let loop ((a 0) (b 1) (n n))
    (if (= n 0) a
        (loop b (+ a b) (- n 1)))))
 

Dijkstra Algorithm

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

sed

#!/bin/sed -f
 
# First we need to convert each number into the right number of ticks 
# Start by marking digits
s/[0-9]/<&/g
 
# We have to do the digits manually.
s/0//g; s/1/|/g; s/2/||/g; s/3/|||/g; s/4/||||/g; s/5/|||||/g
s/6/||||||/g; s/7/|||||||/g; s/8/||||||||/g; s/9/|||||||||/g
 
# Multiply by ten for each digit from the front.
:tens
s/|</<||||||||||/g
t tens
 
# Done with digit markers
s/<//g
 
# Now the actual work.
:split
# Convert each stretch of n >= 2 ticks into two of n-1, with a mark between
s/|\(|\+\)/\1-\1/g
# Convert the previous mark and the first tick after it to a different mark
# giving us n-1+n-2 marks.
s/-|/+/g
# Jump back unless we're done.
t split
# Get rid of the pluses, we're done with them.
s/+//g
 
# Convert back to digits
:back
s/||||||||||/</g
s/<\([0-9]*\)$/<0\1/g
s/|||||||||/9/g;
s/|||||||||/9/g; s/||||||||/8/g; s/|||||||/7/g; s/||||||/6/g;
s/|||||/5/g; s/||||/4/g; s/|||/3/g; s/||/2/g; s/|/1/g;
s/</|/g
t back
s/^$/0/

Seed7

Recursive

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;

Original source: [3]

Iterative

This funtion uses a bigInteger result:

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;

Original source: [4]

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

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
]

SNOBOL4

Recursive

	define("fib(a)")	:(fib_end)
fib	fib = lt(a,2) a	:s(return)
	fib = fib(a - 1) + fib(a - 2)	:(return)
fib_end
 
while	a = trim(input)	:f(end)
	output = a " " fib(a)	:(while)
end

Tail-recursive

        define('trfib(n,a,b)') :(trfib_end)
trfib   trfib = eq(n,0) a :s(return)
        trfib = trfib(n - 1, a + b, a) :(return)
trfib_end

Iterative

        define('ifib(n)f1,f2') :(ifib_end)
ifib    ifib = le(n,2) 1 :s(return)
        f1 = 1; f2 = 1
if1     ifib = gt(n,2) f1 + f2 :f(return)
        f1 = f2; f2 = ifib; n = n - 1 :(if1)
ifib_end

Analytic

Works with: Macro Spitbol

Works with: CSnobol

Note: Snobol4+ lacks built-in sqrt( ) function.

        define('afib(n)s5') :(afib_end)
afib    s5 = sqrt(5)
        afib = (((1 + s5) / 2) ^ n - ((1 - s5) / 2) ^ n) / s5
        afib = convert(afib,'integer') :(return)
afib_end

Test and display all, Fib 1 .. 10

loop    i = lt(i,10) i + 1 :f(show)
        s1 = s1 fib(i) ' ' ; s2 = s2 trfib(i,0,1) ' '
        s3 = s3 ifib(i) ' '; s4 = s4 afib(i) ' ' :(loop)
show    output = s1; output = s2; output = s3; output = s4
end

Output:

1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55
1 1 2 3 5 8 13 21 34 55

SNUSP

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

Iterative

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

Recursive

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

Softbridge BASIC

Iterative

 
Function Fibonacci(n)
   x = 0
   y = 1
   i = 0
   n = ABS(n)
   If n < 2 Then
   Fibonacci = n
   Else
   Do Until (i = n)
      sum = x+y
      x=y
      y=sum
      i=i+1
   Loop
   Fibonacci = x
   End If
 
End Function
 

Standard ML

Recursion

This version is tail recursive.

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

StreamIt

void->int feedbackloop Fib {
    join roundrobin(0,1);
    body in->int filter {
        work pop 1 push 1 peek 2 { push(peek(0) + peek(1)); pop(); }
    };
    loop Identity<int>;
    split duplicate;
    enqueue(0);
    enqueue(1);
}

Tcl

Simple Version

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

Iterative

Translation of: Perl

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
}

Recursive

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

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.

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

E.g.:

expr {fib(7)} ;# ==> 13
 
namespace path tcl::mathfunc #; or, interp alias {} fib {} tcl::mathfunc::fib
fib 7 ;# ==> 13

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.

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]
}

% fib-tailrec 100
354224848179261915075

Handling Negative Numbers

Iterative

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

Recursive

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

For the Mathematically Inclined

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

Works with: Tcl version 8.5

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

TI-83 BASIC

Unoptimized fibonacci program

  :Disp "0"              //Dirty, I know, however this does not interfere with the code
  :Disp "1"
  :Disp "1"
  :1→A
  :1→B
  :0→C
  :Goto 1
  :Lbl 1
  :A+B→C
  :Disp C
  :B→A
  :C→B
  :Goto 1  

Optimized fibonacci program, compute fibonacci for N

:Prompt N
:0→A
:1→B
:For(I,1,N)
  :A→C
  :B→A
  :C+B→B
:End
:A 

Binet's formula

:Prompt N
:.5(1+√(5))→P
:(P^N–(-1/P)^N)/√(5) 

TI-89 BASIC

Recursive

Optimized implementation (too slow to be usable for n higher than about 12).

fib(n)
when(n<2, n, fib(n-1) + fib(n-2))

Iterative

Unoptimized implementation (I think the for loop can be eliminated, but I'm not sure).

fib(n)
Func
Local a,b,c,i
0→a
1→b
For i,1,n
  a→c
  b→a
  c+b→b
EndFor
a
EndFunc

TSE SAL

 
 
// 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
 
 

TUSCRIPT

 
$$ MODE TUSCRIPT
ASK "What fibionacci number do you want?": searchfib=""
IF (searchfib!='digits') STOP
Loop n=0,{searchfib}
 IF (n==0) THEN
   fib=fiba=n
 ELSEIF (n==1) THEN
   fib=fibb=n
 ELSE
   fib=fiba+fibb, fiba=fibb, fibb=fib
 ENDIF
 IF (n!=searchfib) CYCLE
 PRINT "fibionacci number ",n,"=",fib
ENDLOOP
 

Output:

What fibionacci number do you want? >12
fibionacci number 12=144

Output:

What fibionacci number do you want? >31
fibionacci number 31=1346269 

Output:

What fibionacci number do you want? >46
fibionacci 46=1836311903

UnixPipes

This example is incorrect. There is a race between parallel commands. tee last might open and truncate the file before cat last opens it. Then cat last pipes the empty file to xargs, and expr reports a syntax error, and the script hangs forever. Please fix the code and remove this message.

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

UNIX Shell

Works with: bash version 3

#!/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

Recursive:

Works with: bash version 3

fib() {
  local n=$1
  [ $n -lt 2 ] && echo -n $n || echo -n $(( $( fib $(( n - 1 )) ) + $( fib $(( n - 2 )) ) ))
}

Ursala

All three methods are shown here, and all have unlimited precision.

#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+-+-

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 Fibonacci numbers by all three methods.

#cast %nLL
 
examples = <.iterative_fib,recursive_fib,analytical_fib>* iota20

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

[fib
   [small?] []
     [pred dup pred]
     [+]
   binrec].

Vala

Recursive

Using int, but could easily replace with double, long, ulong, etc.

 
int fibRec(int n){
	if (n < 2)
		return n;
	else
		return fibRec(n - 1) + fibRec(n - 2);
}
 

Iterative

Using int, but could easily replace with double, long, ulong, etc.

 
int fibIter(int n){
	if (n < 2)
		return n;
 
	int last = 0;
	int cur = 1;
	int next;
 
	for (int i = 1; i < n; ++i){
		next = last + cur;
		last = cur;
		cur = next;
	}
 
	return cur;
}
 

VBA

Like Visual Basic .NET, but with keyword "Public" and type Long instead of Decimal:

 
Public Function Fib(n As Integer) As Long
    Dim fib0, fib1, sum As Long
    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
 

The (slow) recursive version:

 
Public Function RFib(Term As Integer) As Long
  If Term < 2 Then RFib = Term Else RFib = RFib(Term - 1) + RFib(Term - 2)
End Function
 

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:

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

Invocation:

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

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 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393

Vedit macro language

Iterative

Calculate fibonacci(#1). Negative values return 0.

:FIBONACCI:
#11 = 0
#12 = 1
Repeat(#1) {
    #10 = #11 + #12
    #11 = #12
    #12 = #10
}
Return(#11)

Visual Basic .NET

Platform: .NET

Works with: Visual Basic .NET version 9.0+

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

Recursive

Works with: Visual Basic .NET version 9.0+

Function Seq(ByVal Term As Integer)
        If Term < 2 Then Return Term
        Return Seq(Term - 1) + Seq(Term - 2)
End Function

Whitespace

Iterative

This program generates Fibonacci numbers until it is forced to terminate.

It was generated from the following pseudo-Assembly.

push 0
push 1
 
0:
    swap
    dup
    onum
    push 10
    ochr
    copy 1
    add
    jump 0

Output:

$ wspace fib.ws | head -n 6
0
1
1
2
3
5

Recursive

This program takes a number n on standard input and outputs the nth member of the Fibonacci sequence.

; Read n.
push 0
dup
inum
load
 
; Call fib(n), ouput the result and a newline, then exit.
call 0
onum
push 10
ochr
exit
 
0:
    dup
    push 2
    sub
    jn 1   ; Return if n < 2.
    dup
    push 1
    sub
    call 0 ; Call fib(n - 1).
    swap   ; Get n back into place.
    push 2
    sub
    call 0 ; Call fib(n - 2).
    add    ; Leave the sum on the stack.
1:
    ret

Output:

$ echo 10 | wspace fibrec.ws
55

Wrapl

Generator

DEF fib() (
    VAR seq <- [0, 1]; EVERY SUSP seq:values;
    REP SUSP seq:put(seq:pop + seq[1])[-1];
);

To get the 17th number:

16 SKIP fib();

To get the list of all 17 numbers:

ALL 17 OF fib();

Iterator

Using type match signature to ensure integer argument:

TO fib(n @ Integer.T) (
    VAR seq <- [0, 1];
    EVERY 3:to(n) DO seq:put(seq:pop + seq[1]);
    RET seq[-1];
);

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)
};