Fibonacci Number ProgramIn 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 Θ(F(n)) time, which is Ω(1.6n). 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' 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 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.argv1) 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 -
\begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\ F\left(n\right) & F \left(n-1\right) \end{bmatrix} and by using exponentiating by squaring. 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.6n). (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))) 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.6n). 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 External links *Fibonacci series implementations and benchmark
|