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.

Contents

1 Common Lisp 1.1 Calculating fibonacci through Lucas' formula 2 Haskell examples 2.1 Lazy infinite list 3 Perl examples 3.1 One example 3.2 Binary recursion, snippet 3.3 Binary recursion with special Perl "caching", snippet 3.4 Iterative, snippet 3.5 Command line iterative 4 PostScript example 4.1 Iterative 4.2 Stack recursion 5 Python examples 5.1 Recursion 5.2 Generator 5.3 Matrix equation 6 Scheme examples 6.1 Binary recursion, snippet 6.2 Tail-end recursive, snippet 6.3 Display all, snippet 7 C/C++/Java example 7.1 Recursive snippet 8 Ruby examples 9 See also 10 External links

Common Lisp

Calculating fibonacci through Lucas' formula

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

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 -Mbigint -le '$a=1; print $a += $b while print $b += $a'

PostScript example

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

Python examples

Recursion

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

Generator

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

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

<math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n =

      \begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\
                      F\left(n\right)   & F \left(n-1\right) \end{bmatrix}

<math> 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 (http://www.inorg.chem.msu.ru/~cubbi/serious/fibonacci.html)