# Fibonacci numbers (Oz)

(Redirected from Fail Article)
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.

##  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


##  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


##  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.

##  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


##  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}

hijacker
hijacker
hijacker
hijacker