# Algorithm Implementation/Mathematics/Fibonacci Number Program

(Redirected from Fibonacci number program)

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, ita 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) {
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
}
```

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

## Dyalog APL

#### Basic Tail-Recursive Version

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

#### Array-Oriented Version

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

## 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.6n).

### 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 log2(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
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
} 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;```