# Algorithm Implementation/Mathematics/Fibonacci Number Program

## CEdit

### Recursive versionEdit

``` unsigned int fib(unsigned int n){
if (n < 2)
return n;
else
return fib(n - 1) + fib(n - 2);
}
```

### Recursive version 2Edit

``` unsigned int fib(unsigned int n){
return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}
```

### Tail recursive versionEdit

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

### Lucas formEdit

```#include <math.h>

long fib(unsigned int n) {
double fi = (1 + sqrt(5))/2;
return (pow(fi, n) - pow(-fi, -n)) / sqrt(5);
}
```

### Iterative versionEdit

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

### Exponentiation by squaringEdit

``` unsigned int fib(unsigned int n){
unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
if (n <= 0)
return 0;
while (i > 0){
if (i % 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;
i = i / 2;
}
return a + b;
}
```

### Alternate exponentiation by squaringEdit

``` unsigned int fib(unsigned int n){
unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
if (n <= 0)
return 0;
while (i > 0){
while (i % 2 == 0){
t = d*(2*c + d);
c = c*c + d*d;
d = t;
i = i / 2;
}
t = d*(b + a) + c*b;
a = d*b + c*a;
b = t;
i--;
}
return a + b;
}
```

## C#Edit

### Iterative versionEdit

``` 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 formulaEdit

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

### Using long numbersEdit

```    static Num FibbonaciNumber(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++)
{
remainder = (longer[l] + remainder) / digit_base;
}
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();
}
}
```

## ErlangEdit

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

### Arithmetic versionEdit

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

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

## F#Edit

### Simple recursiveEdit

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

This version overflows pretty quickly, to compute larger numbers Int64 or bigint can be used.

## ForthEdit

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

## GoEdit

### Recursive SolutionEdit

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

### Iterative SolutionEdit

```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 versionEdit

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

### Tail-recursive versionEdit

``` 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 versionEdit

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

### Awesome recursive versionEdit

```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 versionEdit

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

## Dyalog APLEdit

#### Basic Tail-Recursive VersionEdit

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

#### Array-Oriented VersionEdit

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

## IoEdit

### Generic method versionEdit

``` 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 versionEdit

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

## JavaEdit

#### Recursive versionEdit

```    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 versionEdit

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

public long fib2(long n) {
return (n < 2) ? n : getValue(n - 1) + getValue(n - 2);
}
```

#### Iterative versionEdit

```    /**
* 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 VersionEdit

```  /**
* 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 versionEdit

```	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 versionEdit

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

## LinotteEdit

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

```clase Fib
publicos:
mensajes:
Fib nop
{
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)
}
```

## LuaEdit

``` 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 versionEdit

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

## MatlabEdit

### Recursive snippetEdit

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

### Iterative snippetEdit

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

## MaximaEdit

### Recursive versionEdit

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

### Lucas formEdit

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

### Iterative versionEdit

```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 squaringEdit

```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'CamlEdit

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

## PascalEdit

```  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 efficientEdit

```  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 argumentsEdit

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

## PerlEdit

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

#### Recursive versionsEdit

``` 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, snippetEdit

```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", snippetEdit

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

### Iterative, snippetEdit

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

## PHPEdit

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

### Recursive versionEdit

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

### OOP versionEdit

``` 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 versionEdit

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

## PythonEdit

### Recursive versionEdit

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

#### Recursive with memoizationEdit

```m = {0: 0, 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 formEdit

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

### Iterative versionEdit

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

### Exponentiation by squaringEdit

```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 / 2
return a + b
```

### Lucas sequence identitiesEdit

```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, recursionEdit

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

## REBOLEdit

#### Recursive versionEdit

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

## RubyEdit

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

### RecursiveEdit

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

### GeneratorEdit

``` 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 versionEdit

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

### Memoized VersionEdit

``` fibmemo=Hash.new{|h,k| h[k-1]+h[k-2]}
fibmemo[0]=0
fibmemo[1]=1

def fib n
fibmemo[n]
end
```

## SchemeEdit

### Tree-recursive versionEdit

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

### Iterative (tail-recursive) versionEdit

``` (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 versionEdit

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

### Lucas formEdit

``` (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 VersionEdit

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

## UCBLogoEdit

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

#### Recursive versionEdit

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

## VB.NETEdit

### Array oriented versionEdit

``` 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 VersionEdit

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

## JavaScriptEdit

### Recursive versionEdit

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

### Alternative recursive versionEdit

```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 versionEdit

```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 formEdit

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

### Binets formulaEdit

```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" versionEdit

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

## Common LispEdit

### Lucas formEdit

```(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 versionEdit

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

(print (fib 10))
```

## PostScriptEdit

### IterativeEdit

```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 recursionEdit

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 =
} repeat
```

## PL/SQLEdit

### Iterative snippetEdit

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