Algorithm Implementation/Mathematics/Fibonacci Number Program

Wikipedia has related information at Fibonacci number  and Computational complexity of mathematical operations.

Fibonacci is similar to a "hello world" for many functional programming languages, since it can involve paradigms like pattern matching, memoization, and bog-standard tail recursion (which is equivalent to iteration). However, iteration or tail-recursion in linear time is only the first step: more clever exponentiation runs in logarithmic time.

Although the Binet/Lucas formula is technically also exponentiation, its use of floating-point numbers makes it less attractive than the matrix-based solution. In addition, the above discussion of complexity and indeed most of the code here assumes that both addition and multiplication are done in a single step, which is not the case for big, exponentially-growing numbers easily created by fibonacci calculation.

C

An explanation of many of the following above can be found in nayuki's post.

Recursive version

unsigned int fib(unsigned int n) {  // This is exactly the same as a ternary expression  if (n < 2)  return n;  else  return fib(n - 1) + fib(n - 2); } 

Tail recursive version

// C++ default arguments used. If implemented in C, call with fib(n, 0, 1) instead. unsigned int fib(unsigned int n, unsigned int acc = 0, unsigned int prev = 1) {  if (n < 1)  return acc;  else  return fib(n - 1, prev + acc, acc); } 

Using Binet's formula

#include <math.h> const static double phi = (1 + sqrt(5)) / 2; long fib(unsigned int n) {  return (pow(phi, n) - pow(1 - phi, n)) / sqrt(5); } 

Iterative version

unsigned int fib(unsigned int n) {  unsigned int i = 0, j = 1, t;  if (n == 0)  return 0;  for (k = 1; k < n; ++k) {  t = i + j;  i = j;  j = t;  }  return j; } 

Alternate iterative version

// This version is more "parallel" in the sense of a more unrolled loop. unsigned int fib(int n) {  unsigned int i = 0, j = 1, k = 1;  for (; n >= 3; n -= 3) {  i = j + k;  j = i + k;  k = i + j;  }  return n == 0 ? i :  n == 1 ? j :  k; } 

Matrix exponentiation by squaring

// A 2x2 matrix: m00, m01; m10, m11. typedef struct mat22_s {  unsigned int m00, m01, m10, m11; } mat22_t; // Matrix multiplication. inline static mat22_t mat22_mul(mat22_t a, mat22_t b) {  return (mat22_t){  a.m00 * b.m00 + a.m01 * b.m10, a.m00 * b.m01 + a.m01 * b.m11,  a.m10 * b.m00 + a.m11 * b.m10, a.m10 * b.m01 + a.m11 * b.m11}; } // This is a less concise version written for clarity. The compiler should be able to optimize the boilerplate out. unsigned int fib(unsigned int n) {  // Matrix holds F(N-1), F(N); F(N), F(N+1).  // This is an identity matrix, also the 0th power of matrix.  mat22_t result = {1, 0, 0, 1};  mat22_t matrix = {1, 1, 1, 0};  for (; n > 0; n /= 2) {  if (n % 2 == 1) {  result = mat22_mul(matrix, result);  }  matrix = mat22_mul(matrix, matrix);  }  return result.m10; } 

Matrix exponentiation, compact

// A moderately compact version of the matrix calculation. unsigned int fib(unsigned int n) {  // [a b] is "result"; [c d] is "matrix".  unsigned int a = 1, b = 0, c = 0, d = 1, t;  if (n == 0)  return 0;  n = n - 1;  while (n > 0) {  if (n % 2 == 1) {  t = d * (b + a) + c * b;  a = d * b + c * a;  b = t;  }  t = d * (2 * c + d);  c = c * c + d * d;  d = t;  n = n / 2;  }  return a + b; } 

A similar alternative is based on Lucas numbers.

Matrix-derived fast doubling

// Nayuki's fast doubling code. Runs from high to low bits. #include <limits.h> static inline unsigned int log2i(unsigned int n) { #if defined(__has_builtin) && __has_builtin(__builtin_clz)  return sizeof (unsigned int) * CHAR_BIT - __builtin_clz(n) - 1; #else  return sizeof (unsigned int) * CHAR_BIT - 1; // pessimistic guess #endif } unsigned int fib(unsigned int n) {  // Two numbers for iteration. At the end, a = F(N) and b = F(N+1).  unsigned int a = 0, b = 1;  // log2i is not reliable for n = 0. We know better.  unsigned int mask = n == 0 ? 0 : 1 << log2i(n);  for (; mask > 0; mask /= 2) {  // F(2k) = F(k) * (2 * F(k+1) + F(k))  unsigned int new_a = a * (b * 2 - a);  // F(2k+1) = F(k+1)**2 + F(k)**2  unsigned int new_b = a * a + b * b;  a = new_a;   b = new_b;  if (n & mask) {  new_b = a + b;  a = b;  b = new_b;  }  }  return a; } 

C#

C# code is essentially the same as C with some static method specifiers.

Iterative version

static int fib(int n) {  int fib0 = 0, fib1 = 1;  for (int i = 2; i <= n; i++) {  int tmp = fib0;  fib0 = fib1;  fib1 = tmp + fib1;  }  return (n > 0 ? fib1 : 0); } 

Binet's formula

static int fibBINET(int n) {  double sqrt5 = Math.Sqrt(5.0);  double phi = (1 + sqrt5 ) / 2;  return (int)((Math.Pow(phi, n) - Math.Pow(-phi, -n)) / sqrt5); } 

Using long numbers

static Num FibonacciNumber(int n) {  Num n1 = new Num(0);  Num n2 = new Num(1);  Num n3 = new Num(1);  for (int i = 2; i <= n; i++) {  n3 = n2 + n1;  n1 = n2;  n2 = n3;  }  return n3; } struct Num {  const int digit_base = 0x40000000; // 2^30  List<int> digits;  public int Length { get { return digits.Count; } }  public int this[int index] { get { return digits[index]; } private set { digits[index] = value; } }  public Num(int i) {  digits = new List<int>();  while (i > 0) {  digits.Add(i % digit_base);  i /= digit_base;  }  }  public static Num operator +(Num a, Num b) {  Num n = new Num();  n.digits = new List<int>();  int l = Math.Min(a.Length,b.Length);  int remainder = 0;  for (int i = 0; i < l; i++) {  n.digits.Add((a[i] + b[i] + remainder) % digit_base);  remainder = (a[i] + b[i] + remainder) / digit_base;  }  Num longer = a.Length > b.Length ? a : b;  for (; l < longer.Length; l++) {  n.digits.Add((longer[l] + remainder) % digit_base);  remainder = (longer[l] + remainder) / digit_base;  }  if (remainder > 0) n.digits.Add(remainder);  return n;  }  public override string ToString() {  StringBuilder sb = new StringBuilder();  for (int i = Length - 1; i >= 0; i--) {  sb.AppendFormat("{0:D" + (digit_base.ToString().Length-1) + "}", this[i]);  }  return sb.ToString();  } } 

D

Basic Recursive Version

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

Iterative Version

ulong fib(uint n) { ulong fib0 = 0; ulong fib1 = 1; for (auto i = 2; i <= n; i++) { auto tmp = fib0; fib0 = fib1; fib1 = tmp + fib1; } return (n > 0 ? fib1 : 0); } 

Memoized Recursive Version

ulong fib(uint n){ static ulong[] memo; if (n < 0) return n; if (n < memo.length) return memo[n]; auto result = (n < 2) ? n : fib(n - 1) + fib(n - 2); memo.length = n + 1; memo[n] = result; return result; } 

Erlang

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

Arithmetic version

 fib(N) ->  S = math:sqrt(5),  round(math:pow(((1 + S) / 2), N) / S). 

algorithm taken from the Pascal "more efficient" version, below

F#

Simple recursive

 let rec fib x = if x < 2I then x else fib(x - 1I) + fib(x - 2I) 

This version uses F# System.Numerics.BigInteger type

Memoized recursive

open System.Collections.Generic let rec fib n =  let memo = Dictionary<_, _>()  let rec fibInner = function  | n when n = 0I -> 0I  | n when n = 1I -> 1I  | n -> fib(n - 1I) + fib(n - 2I)  if memo.ContainsKey(n) then memo.[n]  else  let res = fibInner n  memo.[n] <- res  res 

Tail recursive

let fib n =   let rec fibInner (n, a, b) =  if (n = 0I) then a  else fibInner ((n - 1I), b, (a + b))  fibInner (n, 0I, 1I) 

Iterative

let fib n =   if n < 2I then  n  else  let mutable fib1 = 0I  let mutable fib2 = 1I  let mutable i = 2I  let mutable tmp = 0I  while (i <= n) do  i <- i + 1I  tmp <- fib1  fib1 <- fib2  fib2 <- tmp + fib2  fib2 

Infinite Sequence Generator

let fibSeq =  Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0I, 1I) let fib n =  fibSeq |> (Seq.skip n) |> Seq.head 

Forth

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

Go

Recursive Solution

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

Iterative Solution

func fib(n int) int {  if n == 0 {  return 0  }  a, b := 0, 1  for i := 1; i < n; i++ {  a, b = b, a+b  }  return b } 

Haskell

List version

 fib n = fibs 0 1 !! n  where  fibs a b = a : fibs b (a + b) 

Tail-recursive version

 fib n | n < 0 = undefined  | otherwise = fib' n 0 1  where  fib' 0 a _ = a  fib' n a b = fib' (n - 1) b (a + b) 

Simple recursive version

 fib 0 = 0  fib 1 = 1  fib n = fib (n-1) + fib (n-2) 

Awesome recursive version

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] 

Or :

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

Or :

fibs = map fst $ iterate (\(a,b)->(b,a+b)) (0,1) 

Closed-form version

Defines arithmetic operations on a custom data type, and then uses it to run the explicit formula without going via floating point - no rounding or truncation. Calculates the ten millionth fibonacci number in a few seconds (it has roughly two million digits).

module Fib where -- A type for representing a + b * sqrt n -- The n is encoded in the type. data PlusRoot n a = a :+/ a  deriving (Eq, Read, Show) infix 6 :+/ -- Fetch the n in the root. class WithRoot n where  getRoot :: Num b => PlusRoot n a -> b instance (WithRoot n, Num a) => Num (PlusRoot n a) where  (a :+/ b) + (c :+/ d) = (a + c) :+/ (b + d)  x@(a :+/ b) * (c :+/ d) = (a * c + getRoot x * b * d) :+/ (a * d + b * c)  negate (a :+/ b) = negate a :+/ negate b  fromInteger = (:+/ 0) . fromInteger  -- I could implement these with (Ord a) but then we can't use the type  -- with e.g. complex numbers.  abs _ = error "PlusRoot.abs: unimplemented"  signum _ = error "PlusRoot.signum: unimplemented" instance (WithRoot n, Fractional a) => Fractional (PlusRoot n a) where  fromRational = (:+/ 0) . fromRational  recip x@(a :+/ b) = (a / r) :+/ (negate b / r)  where  r = a*a - getRoot x * b*b -- Type parameter to PlusRoot. It would be easy to declare similar -- types for Two or whatever, and get all the above arithmetic for free. newtype Five = Five Five instance WithRoot Five where  getRoot _ = 5 -- The formula is phi^n - xi^n / sqrt 5 -- but it's always an integer, i.e. phi^n - xi^n is always a multiple -- of sqrt 5, so the division isn't strictly necessary - just grab the -- relevant coefficient. fib :: Integer -> Integer fib n = case phi^n - xi^n of  -- The 'round' here is to make the types match; as discussed previously  -- n must be an integer so no actual rounding is done.  _ :+/ n -> round n  where  phi :: PlusRoot Five Rational  phi = (1 :+/ 1) / 2  xi = (1 :+/ negate 1) / 2 

For other versions, see :

• Haskell/Overview
• nayuki's fast doubling again, but recursive this time

Dyalog APL

Basic Tail-Recursive Version

fibonacci?{  ??0 1  ?=0:??? (1??,+/?)? ?-1 } 

Array-Oriented Version

fibonacci?{+/{?!??}(??)-?IO} 

Other Versions

See Fibonacci at the Dynamic Functions Database

Io

Generic method version

 fib := method(n,  if(n < 4,  (n + n % 2) / 2,  (n % 2 * 2 - 1) * fib((n + n % 3) / 2 - 1) ** 2 + fib((n - n % 3) / 2 + 1) ** 3  )  ) 

Polymorphic method version

 Number fibonacci := method((self - 1) fibonacci + (self -2) fibonacci)  1 fibonacci = 1  0 fibonacci = 0 

Java

Recursive version

public void run(int n) {  if (n <= 0) {  return;  }  run(n, 1, 0); } private void run(int n, int eax, int ebx) {  n--;  if (n == 0) {  System.out.println(eax + ebx);  return;  }  run(n, ebx, eax + ebx); } 

Variations on the recursive version

/* Recursive versions. Horribly inefficient. Use iterative/memoized versions instead */ public long fib(long n) {  if (n < 2) {  return 1;  }  return fib(n - 1) + fib(n - 2); } public long fib2(long n) {  return (n < 2) ? n : getValue(n - 1) + getValue(n - 2); } 

Iterative version

/** * Source based on  * http://20bits.com/2007/05/08/introduction-to-dynamic-programming/ * as at 9-May-2007 */ private long fibonacci(int n) {  long n2 = 0;  long n1 = 1;  long tmp;  for (int i = n; i >= 2; i--) {  tmp = n2;  n2 = n1;  n1 = n1 + tmp;  }  return n2 + n1; } 

Simpler Iterative Version

/** * returns the Nth number in the Fibonacci sequence */ public int fibonacci(int N) {  int lo = 0;  int hi = 1;  for (int i = 0; i < N; i++) {  hi = lo + hi;  lo = hi - lo;  }  return lo; } 

Memoized version

private int[] fibs; // array for memoized fibonacci numbers public int fib(int n) {  if (n < 2) {  return n;  }  if (fibs == null) { // initialise array to first size asked for  fibs = new int[n + 1];  }   else if (fibs.length < n) { // expand array  int[] newfibs = new int[n + 1]; // inefficient if looping through values of n  System.arraycopy(fibs, 0, newfibs, 0, fibs.length);  fibs = newfibs;  }  if (fibs[n] == 0) {  fibs[n] = fib(n - 1) + fib(n - 2);  }  return fibs[n]; } 

Iterative Memoized version

public int fib(int n) {  if (n < 2) {  return n;  }  int[] f = new int[n + 1];  f[0] = 0;  f[1] = 1;  for (int i = 2; i <= n; i++) {  f[i] = f[i - 1] + f[i - 2];  }  return f[n]; } 

Linotte

Fibonacci: Principal : Rôles :	n :: nombre Actions :	"Entrez un nombre :" !	n ?	fibo(n) ! Fibo : Rôles :	* n :: nombre Actions :	si n < 2 alors retourne n	retourne fibo(n-1) + fibo(n-2) 

Lexico (in Spanish)

clase Fib publicos: mensajes: Fib nop Fibonacci(deme n es una cantidad) es_funcion cantidad	{	los objetos uno, dos, tres, i, respuesta son cantidades	copie 0 en uno	copie 1 en dos	variando i desde 1 hasta n haga:	{	copie uno en respuesta	copie uno + dos en tres	copie dos en uno	copie tres en dos	}	retornar uno	} /**********************************/ tarea { el objeto f es un Fib muestre "el 5: ", f.Fibonacci(doy 5) } 

Lua

 function fib(n)  local a, b = 0, 1  while n > 0 do  a, b = b, a + b  n = n - 1  end  return a  end 

Recursive version

 function fib(n)  if n > 1 then n = fib(n - 1) + fib(n - 2) end  return n  end 

Matlab

Recursive snippet

function F = fibonacci_recursive(n) if n < 2   F = n; else  F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2); end 

Iterative snippet

function F = fibonacci_iterative(n) first = 0; second = 1; third = 0; for q = 1:n,  third = first + second;  first = second;  second = third; end F = first; 

Maxima

Recursive version

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

Lucas form

fib(n):=(%phi^n-(-%phi)^-n)/sqrt(5); 

Iterative version

fib(n) := block( [i,j,k], i : 1, j : 0, for k from 1 thru n do [i,j] : [j,i + j], return(j) )$ 

Exponentiation by squaring

fib(n) := block( [i,F,A], if n <= 0 then return(0), i : n - 1, F : matrix([1,0],[0,1]), A : matrix([0,1],[1,1]), while i > 0 do block( if oddp(i) then F : F.A, A : A^^2, i : quotient(i,2) ), return(F[2,2]) )$ 

O'Caml

 let fib n = let rec fibonacci n = match n with | 0 -> (0, 0) | 1 -> (0, 1) | m -> let (a, b) = fibonacci (m-1) in (b, a+b) in let (_, k) = fibonacci n in k;; 

Pascal

 function F(n: integer): integer;  begin  case n of  1,2: Result:=1  else Result:=F(n-1)+F(n-2) end;  end; 

A bit more efficient

 function F(n: integer): integer;  begin  Result:=Round(Power((1+sqrt(5))/2, n)/sqrt(5));  end; 

Note that Power is usually defined in Math, which is not included by default.

For most compilers it's possible to improve performance by using the Math.IntPower instead of the Math.Power.

Iterative version also for negative arguments

function fib(n:integer):extended; var i:integer;  fib0,fib1:extended; begin fib0:=0; fib1:=1; for i:=1 to abs(n) do  begin fib0:=fib0+fib1; fib1:=fib0-fib1; end;  if (n<0)and(not odd(n)) then fib0:=-fib0;  fib:=fib0; end: 

Perl

 sub fib {  my ($n, $a, $b) = (shift, 0, 1);  ($a, $b) = ($b, $a + $b) while $n-- > 0;  $a;  } 

Recursive versions

 sub fib {  my $n = shift;  return $n if $n < 2;  return fib($n - 1) + fib($n - 2);  }  # returns F_n in a scalar context  # returns all elements in the sequence up to F_n in a list context  # only one recursive call  sub fib {  my ($n) = @_;  return (0) if ($n == 0);  return (0, 1) if ($n == 1);  my @fib = fib($n - 1);  return (@fib, $fib[-1] + $fib[-2]);  } 

Binary recursion, snippet

sub fibo; sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)} 

Runs in Θ(F(n)) time, which is Ω(1.6ⁿ).

Binary recursion with special Perl "caching", snippet

use Memoize; memoize 'fibo'; sub fibo; sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)} 

Iterative, snippet

sub fibo {  my ($n, $a, $b) = (shift, 0, 1);  ($a, $b) = ($b, $a + $b) while $n-- > 0;  $a; } 

PHP

Iterative version

function generate_fibonacci_sequence($length) { for($l = [0, 1], $i = 2, $x = 0; $i < $length; $i++) { $l[] = $l[$x++] + $l[$x]; } return $l; } 

Recursive version

function fib($n) { if ($n < 2) { return $n; } return fib($n - 1) + fib($n - 2); } 

Ternary version

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

OOP version

class Fibonacci { public $Begin= 0; public $Next; public $Amount; public $i; public function __construct( $Begin, $Amount ) { $this->Begin= 0; $this->Next= 1; $this->Amount= $Amount; } public function _do() { for( $this->i = 0; $this->i < $this->Amount; $this->i++ ) { $Value = ( $this->Begin + $this->Next ); echo $this->Begin . ' + ' . $this->Next . ' = ' . $Value . '<br />'; $this->Begin= $this->Next; $this->Next= $Value; } } } $Fib = new fibonacci( 0, 6 ); echo $Fib->_do(); 

Alternate version

 function fib($n) { return round(pow(1.6180339887498948482, $n) / 2.2360679774998); } 

Python

Recursive version

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

Or :

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

Recursive with memoization

m = {0: 1, 1: 1} def fib(n): #assert n >= 0 if n not in m: m[n] = fib(n-1) + fib(n-2) return m[n] 

Lucas form

def fib(n): phi = (1 + sqrt(5))/2 return int((phi**n - (-phi)**-n)/sqrt(5)) 

Iterative version

def fib(n): i,j = 1,0 for k in range(1,n + 1): i,j = j, i + j return j 

Iterative version using Generator

def fib(n): a,b = 1,0 for i in range(n): yield b a, b = b, a+b 

Exponentiation by squaring

def fib(n): if n <= 0: return 0 i = n - 1 a,b = 1,0 c,d = 0,1 while i > 0: if i % 2 == 1: a,b = d*b + c*a, d*(b + a) + c*b c,d = c**2 + d**2, d*(2*c + d) i = i >> 1 return a + b 

Lucas sequence identities

def fib(n): if n <= 0: return 0 # n = 2**r*s where s is odd s, r = n, 0 while s & 1 == 0: r, s = r+1, s/2 # calculate the bit reversal t of (odd) s # e.g. 19 (10011) <=> 25 (11001) t = 0 while s > 0: if s & 1 == 1: t, s = t+1, s-1 else: t, s = t*2, s/2 # use the same bit reversal process # to calculate the sth Fibonacci number # using Lucas sequence identities u, v, q = 0, 2, 2 while t > 0: if t & 1 == 1: # u, v of x+1 u, v = (u + v) / 2, (5*u + v) / 2 q, t = -q, t-1 else: # u, v of 2*x u, v = u * v, v * v - q q, t = 2, t/2 # double s until we have # the 2**r*sth Fibonacci number while r > 0: u, v = u * v, v * v - q q, r = 2, r-1 return u 

Lucas sequence identities, recursion

As with the iterative version, this solution is also O(log n) with arbitrary precision.

def fib(n): def fib_inner(n): if n == 0: return 0, 2 m = n >> 1 # q = 2*(-1)**m q = -2 if (m & 1) == 1 else 2 u, v = fib_inner(m) u, v = u * v, v * v - q if n & 1 == 1: # u, v of 2m+1 u1 = (u + v) >> 1 return u1, 2*u + u1 else: # u, v of 2m return u, v if n <= 0: return 0 # the outermost loop is unrolled # to avoid calculating an unnecessary v m = n >> 1 u, v = fib_inner(m) if n & 1 == 1: # u of m+1 u1 = (u + v) >> 1 # u of 2m+1 return u*u + u1*u1 else: # u of 2m return u * v 

REBOL

Recursive version

fib: func [n [integer!]] [ either n < 2 [n] [(fib n - 1) + (fib n - 2)] ] 

Ruby

 class Integer  def fib  @n = self.abs  if @n < 2  return @n  else  return (@n-1).fib + (@n-2).fib  end  end  end 

Alternate:

 class Integer  def fib  @n = self.abs  (@n<2)?(return @n):(return (@n-1).fib+(@n-2).fib)  end  end  # you run it like this  puts 10.fib # output: 55  puts 15.fib # output: 610 

Recursive

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

Generator

 class FibGenerator  def initialize(n)  @n = n  end    def each  a, b = 1, 1  @n.times do  yield a  a, b = b, a+b  end  end    include Enumerable  end    def fibs(n)  FibGenerator.new(n)  end  #use like this  fibs(6).each do |x|  puts x  end 

Arithmetic version

 def f(n)  ((((1+Math.sqrt(5))/2)**n)/Math.sqrt(5)+0.5).floor  end 

Memoized Version

 fibmemo=Hash.new{|h,k| h[k-1]+h[k-2]}  fibmemo[0]=1  fibmemo[1]=1    def fib n  fibmemo[n]  end 

Scheme

Tree-recursive version

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

Iterative (tail-recursive) version

 (define (fib n)  (define (iter a b count)  (if (<= count 0)  a  (iter b (+ a b) (- count 1))))  (iter 0 1 n)) 

Named-let, Iterative version

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

Lucas form

 (define fib  (let* ((sqrt5 (inexact->exact (sqrt 5)))  (fi (/ (+ sqrt5 1) 2)))  (lambda (n)  (round (/ (- (expt fi n) (expt (- fi 1) n)) sqrt5))))) 

Logarithmic-time Version

This version squares the Fibonacci transformation, allowing calculations in log₂(n) time:

(define (fib-log n)  "Fibonacci, in logarithmic time."  (define (fib-iter a b p q count)  (cond ((= count 0) b)  ((even? count)  (fib-iter a b  (+ (* p p) (* q q))  (+ (* 2 p q) (* q q))  (/ count 2)))  (else (fib-iter (+ (* b q) (* a q) (* a p))  (+ (* b p) (* a q))  p q  (- count 1)))))  (fib-iter 1 0 0 1 n)) 

UCBLogo

to fib :n output (cascade :n [?1+?2] 1 [?1] 0) end 

Recursive version

to fib :n if :n<2 [output 1] output (fib :n-1)+(fib :n-2) end 

VB.NET

Array oriented version

Dim i As Integer = 2 Dim sequencelength As Integer = 50 Dim fibonacci(sequencelength) As Integer fibonacci(0) = 0 fibonacci(1) = 1 While i <> sequencelength  fibonacci(i) = fibonacci(i - 1) + fibonacci(i - 2)  i += 1 End While 

Recursive Version

Private Function fibonacci(ByVal i as integer) As Integer  If i < 1 Then  Return -1  ElseIf i < 2 Then  Return i  Else  Return fibonacci(i-1) + fibonacci(i-2)  End If End Function 

JavaScript

Recursive version

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

Alternative recursive version

function fib(n, prev, cur) {  if (prev == null) prev = 0;  if (cur == null) cur = 1;  if (n < 2) return cur;  return fib(n--, cur, cur + prev); } 

Prev and cur is optional arguments.

Iterative version

function fibonacci(n) {  var i = 1, j = 0, k, t;  for (k = 1; k <= Math.abs(n); k++) {  t = i + j;  i = j;  j = t;  }  if (n < 0 && n % 2 === 0) j = -j;  return j; } 

This example supports negative arguments.

Lucas form

function fibonacci(n) {  var sqrt5 = Math.sqrt(5);  var fi = (1 + sqrt5) / 2;  return Math.round((Math.pow(fi, n) - Math.pow(-fi, -n)) / sqrt5); } 

Binet's formula

function fibonacci(n) {  var sqrt5 = Math.sqrt(5);  var fi = (1 + sqrt5) / 2;  return Math.round((Math.pow(fi, n + 1) - Math.pow(1 - fi, n + 1)) / sqrt5); } 

Algorithm from the Pascal "more efficient" version

function fibonacci(n) {  var sqrt5 = Math.sqrt(5);  return Math.round(Math.pow(((1 + sqrt5) / 2), n) / sqrt5); } 

Common Lisp

Lucas form

(defun fib (n)  (cond  ((= n 0) 0)  ((or (= n 1) (= n 2)) 1)  ((= 0 (mod n 2)) (-  (expt (fib (+ (truncate n 2) 1)) 2)  (expt (fib (- (truncate n 2) 1)) 2)))  (t (+ (expt (fib (truncate n 2)) 2)  (expt (fib (+ (truncate n 2) 1)) 2))))) (fib (parse-integer (second *posix-argv*))) ; 

Recursive version

(defun fib (x)  (if (or (zerop x) (= x 1)) 1  (+ (fib (- x 1)) (fib (- x 2))))) (print (fib 10)) 

PostScript

Iterative

 20 % how many Fibonacci numbers to print    1 dup  3 -1 roll  {  dup  3 -1 roll  dup  4 1 roll  add  3 -1 roll  =  }  repeat 

Stack recursion

This example uses recursion on the stack.

 % the procedure  /fib  {  dup dup 1 eq exch 0 eq or not  {  dup 1 sub fib  exch 2 sub fib  add  } if  } def    % prints the first twenty fib numbers   /ntimes 20 def    /i 0 def  ntimes {  i fib =  /i i 1 add def  } repeat 

PL/SQL

Iterative snippet

CREATE OR REPLACE PROCEDURE fibonacci(lim NUMBER) AS  fibupper NUMBER(38);  fiblower NUMBER(38);  fibnum NUMBER(38);  i NUMBER(38);  BEGIN  fiblower := 0;  fibupper := 1;  fibnum := 1;  FOR i IN 1 .. lim  LOOP  fibnum := fiblower + fibupper;  fiblower := fibupper;  fibupper := fibnum;  DBMS_OUTPUT.PUT_LINE(fibnum);  END LOOP;  END;