Fibonacci number program

In many beginning computer science courses, an introduction to the concept of recursion often includes a program to calculate and print Fibonacci numbers (or computing the factorial of a number). In general, however, a recursive algorithm to compute Fibonacci numbers is extremely inefficient when compared to other algorithms, such as iterative or matrix equation algorithms.

Haskell examples

Lazy infinite list

module Main where
import System.Environment

fibo = 1 : 1 : zipWith (+) fibo (tail fibo)

main = do
    args <- getArgs
    print (fibo !! (read(args!!0)-1))

Perl examples

One example

#! /usr/bin/perl
use bigint;

my ($a, $b) = (0, 1);
for (;;) {
    print "$a\n";
    ($a, $b) = ($b, $a+$b);
}

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
}

Command line iterative

perl -le '$a=1; print $a += $b while print $b += $a'

PostScript example

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

Python examples

Generator

#! /usr/bin/python

def fibo():
   A, B = 0, 1
   while True:
       A, B = B, A+B
       yield A

if __name__ == '__main__':
   import sys, itertools
   n = int(sys.argv[1])
   print '%d' % tuple(itertools.islice(fibo(), n-1, n))

Matrix equation

def mul(A, B):
    a, b, c = A
    d, e, f = B
    return a*d + b*e, a*e + b*f, b*e + c*f

def pow(A, n):
    if n == 1:     return A
    if n & 1 == 0: return pow(mul(A, A), n/2)
    else:          return mul(A, pow(mul(A, A), (n-1)/2))

def fib(n):
    if n < 2: return n
    return pow((1,1,0), n-1)[0]

This calculates the nth Fibonacci number in O(log N) time, from the matrix equation

and by using exponentiating by squaring.

Scheme examples

Binary recursion, snippet

(define fibo
 (lambda (x)
   (if (< x 2)
     x
     (+ (fibo (- x 1)) (fibo (- x 2))))))

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

Tail-end recursive, snippet

(define (fibo x) 
  (define (fibo-iter x a b)
     (if (= x 0) 
            a 
           (fibo-iter (- x 1) b (+ a b))))
  (fibo-iter x 0 1))

Runs in Θ(n) time.

Display all, snippet

(define (fibo-run a b) 
  (display a)
  (newline)
  (fibo-run b (+ a b)))

(define fibo-run-all (fibo-run 0 1))) 

C/C++/Java example

Recursive snippet

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

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

Ruby examples

 def fib(num)
   i, j = 0, 1
   while i <= num
     yield i
     i, j = j, i + j
   end
 end

 fib(10) {|i| puts i}

See also

• Fibonacci number
• Golden ratio
• Hello world program (Unrelated to the Fibonacci numbers, but contains many programming examples.)

External links

• Fibonacci series implementations and benchmark