# Fibonacci numbers (E)

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

Here we present several ways to compute the Fibonacci numbers using the language E.

## Recursion

The recursive definition can be translated directly into E as follows:

<<fib_recursive.e>>=#!/usr/bin/env rune pragma.syntax("0.9") def fib(n :(int >= 0)) :int { switch (n) { match == 0 { return 0 } match == 1 { return 1 } match _ { return fib(n-1) + fib(n-2) } } } testing

Here we've used a guard to ensure that the `fib`

function cannot be passed a negative number (which would result in an infinite recursion).

We can test the `fib`

function using a simple for-loop

<<testing>>=for i in 0..20 { print(" ", fib(i)) }

which produces the following output:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

## Recursion with memoization

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating fib(*n*) 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 fib(*n*) is exponential in *n* (it is about Φ^{n}, where Φ is the golden ratio). To remedy this, we can employ memoization to cache previous computations.

The memoization cache is an E *FlexMap* consisting of entries composed of a key `n`

, and a corresponding value `fib(n)`

. We initialize the map with the first two Fibonacci numbers (the `.diverge()`

turns the initial constant map into a mutable FlexMap):

<<fibmap>>=def fibs := [0 => 0, 1 => 1].diverge()

The memoized `fib`

function recursively computes and stores the value of `fib(n)`

if it hasn't been previously stored in the `fibs`

map. Otherwise it simply returns the memoized value of `fib(n)`

.

<<fib object>>=fibmap def fib(n :(int >= 0)) :int { if (!fibs.maps(n)) { fibs[n] := fib(n-1) + fib(n-2) } return fibs[n] }

We can now use the memoized `fib`

function just as we used the purely recursive one:

<<fib_memo.e>>=#!/usr/bin/env rune pragma.syntax("0.9") fib object for i in 0..20 { print(" ", fib(i)) }

One interesting test of our memoized `fib`

function is to compare the execution time required for the purely recursive and memoized version of `fib`

:

$ time ./fib_recursive.e 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 real 5m3.129s user 4m26.099s sys 0m4.572s

$ time ./fib_memo.e 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 real 0m12.297s user 0m10.252s sys 0m0.601s

The memoized version of the `fib`

function is clearly substantially faster than the purely recursive version. In addition, based on timing results for a simple E Hello World program

$ time ./helloworld.e Hello World! real 0m10.667s user 0m9.293s sys 0m0.563s

it's clear that a significant chunk of the reported execution time for the memoized `fib`

function is startup overhead for the E interpreter.

Download code |