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.
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 O (F(n)) time.
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}
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
Generator
#! /usr/bin/python
# -*- coding: iso-8859-1 -*-
import sys
def fibo():
yield 1
yield 1
A, B = 1, 1
while True:
A, B = B, A+B
yield B
I = fibo()
for tmp1 in xrange(int(sys.argv[1])):
R = I.next()
print R
Binary recursion, snippet
(define fibo
(lambda (x)
(if (< x 2)
x
(+ (fibo (- x 1)) (fibo (- x 2))))))
Runs in O (F(n)) time.
(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 O (n) time.
See also
