Fibonacci numbers (Eiffel)

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

Contents 1 Implementation 1.1 Recursive 1.2 Iteration 2 Testing the FIBONACCI class

Implementation

There are several different ways to implement the Fibonacci numbers in Eiffel.

Recursive

The most direct translation of the mathematical definition is as a recursive function, which can be implemented as an Eiffel feature as follows:

<<recursive fibonacci>>=
fib (n: INTEGER): INTEGER
    require
        n_non_negative: n >= 0
    do
        inspect n
        when 0 then Result := 0
        when 1 then Result := 1
        else
            Result := fib (n-1) + fib (n-2)
        end     
    end

Iteration

Although it is based directly on the definition of a Fibonacci number, the recursive Fibonacci algorithm is extremely expensive, requiring time O(2ⁿ). It also performs a huge amount of redundant work because it computes many Fibonnaci values from scratch many times. A simple linear-time iterative approach which calculates each value of fib successively can avoid these issues:

<<iterative fibonacci>>=
fib_iterative (n: INTEGER): INTEGER
    require
        n_non_negative: n >= 0
    local
        prev1, prev2: INTEGER
        i: INTEGER
    do
        prev1 := 0
            -- Ensure correct behavior for n = 0
        if n = 0 then 
            Result := 0
        else
            Result := 1
        end
        from
            i := 1
        until
            i >= n
        loop
            prev2 := prev1
            prev1 := Result
            Result := prev2 + Result
            i := i + 1
        end     
    end

Testing the FIBONACCI class

We can pull both implementations together into a single class, in order to facilitate testing.

<<Fibonacci.e>>=
class FIBONACCI
create
    make
feature
    recursive fibonacci
    iterative fibonacci
    test
end

The test harness consists of the following feature:

<<test>>=
make
    local
        i: INTEGER
    do
        from 
            i := 0
        until
           i > 10
        loop
            io.put_integer (fib (i))
            io.put_new_line
            i := i + 1
        end
        from 
            i := 0
        until
            i > 10
        loop
            io.put_integer (fib_iterative (i))
            io.put_new_line
            i := i + 1
        end
    end

Download code