Fibonacci number program

Time you got around to sponsoring a child

In many beginning computer science courses, an introduction to the concept of recursion often includes a program to calculate and print Fibonacci numbers. In general, however, a recursive algorithm to compute Fibonacci numbers is extremely inefficient when compared to an iterative algorithm. In addition, an iterative algorithm is generally more intuitive and easier to write.

Table of contents

1 Definiton
2 Perl examples

2.1 1
2.2 2 - Recursive (inefficient)
2.3 3 - Efficient
2.4 4 - Iterative (efficient)

3 Python examples

3.5 1 - Generator (efficient iterative)

4 Haskell examples

4.6 1 - Infinite list (efficient)

5 Scheme examples

5.7 1 - Inefficient
5.8 2 - Tail-end recursive (efficient)

6 See also

Definiton

Mathematical definition:

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

Perl examples

1

! /usr/bin/perl
use bigint;
my ($a, $b) = (0, 1);
for (;;) {
   print("$a\

");
   ($a, $b) = ($b, $a+$b);

}

2 - Recursive (inefficient)

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

The above algorithm is the classical recursive solution, and is very inefficient. The algorithm runs in O (F(n)) time. In Perl, this can easily be solved by having the function cache calculated values, turning the program into one that runs in linear time:

3 - Efficient

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

The solution below uses an iterative algorithm:

4 - Iterative (efficient)

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

                $a}

Python examples

1 - Generator (efficient iterative)

def fib():
   yield 1

   yield 1

   a, b = 1, 1

   while True:

       a, b = b, a+b

       yield b

This is an optimized algorithm so it runs in linear time. It is a generator that returns a list's next element when called.

Haskell examples

1 - Infinite list (efficient)

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

This is an optimized algorithm so it runs in linear time. It creates an infinite list, but only the necessary elements are computed due to Haskell being lazy.

Scheme examples

1 - Inefficient

(define fab
 (lambda (x)

   (if (< x 2)

     x

     (+ (fab (- x 1)) (fab (- x 2))))))

The above algorithm runs in O (F(n)) time, since it uses tree recursion and often unnecessarily recalculates values. The algorithm shown below, on the other hand, runs in O (n) time, much faster:

2 - Tail-end recursive (efficient)

(define (fab x) 
  (define (fab-iter x a b)

     (if (= x 0) 

            a 

           (fab-iter (- x 1) b (+ a b))))

  (fab-iter x 0 1))

Since the second algorithm proceeds iteratively, each Fibonacci value is calculated at most once, rather than several times as in the first algorithm.

The first algorithm is called recursive, while the second algorithm, not quite iterative, is called tail-end recursive. Tail-end recursion is practically the same as iteration with regard to running time, since the processes are equivalent: indeed, an intelligent compiler can often compile a tail-recursive program into an iterative equivalent.