# Fibonacci numbers (Oz)

### From LiteratePrograms

**Other implementations**: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam |**Oz**| Pascal | PIR | PostScript | 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

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

## Implementation

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

<<Fib.oz>>=functorimportSystem Applicationdefinerecursive fib memoized fib iterative fib testdriverend

## 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}ifN < 2thenNelse{RecursiveFib N - 1} + {RecursiveFib N - 2}endend

## Memoized recursion

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating the *n*th 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}elseFibNinifN < 2thenFibN = NelseFibN = {MemoizedFib N - 1} + {MemoizedFib N - 2}end{Dictionary.put Memo N FibN} FibNendend

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}ifN < 1thenF1else{Fib (N - 1) F2 (F1 + F2)}endendin{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}forXin0..30do{System.showInfo "{" # {System.printName F} # " " # X # "} = " # {F X}}endend

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 |