Fibonacci numbers (Oz)

From LiteratePrograms
Jump to: navigation, search
Other implementations: bc | C | C Plus Plus templates | dc | E | Erlang | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | Pascal | PIR | PostScript | Prolog | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by


 F(n) =
 \begin{cases}
   0             & n = 0 \\
   1             & n = 1 \\
   F(n-1)+F(n-2) & n > 1 \\
  \end{cases} .

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.


Contents

[edit] Implementation

We describe several different implementations for calculating the fibonacci numbers in Oz:

<<Fib.oz>>=
functor
import
   System
   Application
define
   recursive fib
   memoized fib
   iterative fib
   testdriver
end

[edit] Recursive

Here is a very simple recursive implementation. This will become slow on big numbers, because the numbers are recalculated for each recursion.

<<recursive fib>>=
fun {RecursiveFib N}
   if N < 2 then N else {RecursiveFib N - 1} + {RecursiveFib N - 2} end
end

[edit] Memoized recursion

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating the nth fibonacci number requires calculating two smaller fibonacci numbers, which in turn require two additional recursive calls each, and so on until all branches reach 1. As a consequence, the time required to calculate the fibonacci numbers is exponential in n (it is about Φn, where Φ is the golden ratio). To remedy this, we can employ memoization to cache previous computations:

<<memoized fib>>=
Memo = {NewDictionary}
fun {MemoizedFib N}
   if {Dictionary.member Memo N}
   then {Dictionary.get Memo N}
   else
      FibN
   in
      if N < 2 then FibN = N else FibN = {MemoizedFib N - 1} + {MemoizedFib N - 2} end
      {Dictionary.put Memo N FibN}
      FibN
   end
end

This memoized recursive implementation makes use of Oz's mutable Dictionary datatype to store and retrieve previously computed values.

[edit] Iteration

Another alternative for fast computation of fibonacci numbers is a simple linear-time iterative approach which calculates each fibonacci number successively. Although Oz supports mutable variables and for-loops, we have chosen here to implement a compact iterative routine that performs a tail-recursive, accumulative calculation:

<<iterative fib>>=
fun {IterativeFib N}
   fun {Fib N F1 F2}
     if N < 1 then F1 else {Fib (N - 1) F2 (F1 + F2)} end
   end
in
   {Fib N 0 1}
end

[edit] Test driver

The test driver procedure runFib computes and prints the fibonacci numbers from n = 0 up to n = 30.

<<testdriver>>=
proc {RunFib F}
   for X in 0..30 do
      {System.showInfo "{" # {System.printName F} # " " # X # "} = " # {F X}}
   end
end

We apply RunFib to each of the implementations described above, and then exit.

<<testdriver>>=
{RunFib RecursiveFib}
{RunFib MemoizedFib}
{RunFib IterativeFib}
{Application.exit 0}
Download code
hijacker
hijacker
hijacker
hijacker