# Fibonacci numbers (Mercury)

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

## Recursion

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

Mercury is descendant of Prolog.

Here you specify relations. Then you specify the modes of in/out combinations of the relation parameters that you will implement and the determinism of the solutions. Then facts and rules.

The determinism possibilities are the following:

- have exactly one solution, then that mode is deterministic (det);
- either have no solutions or have one solution, then that mode is semideterministic (semidet);
- have at least one solution but may have more, then that mode is multisolution (multi);
- have zero or more solutions, then that mode is nondeterministic (nondet);
- fail without producing a solution, then that mode has a determinism of failure.
- If no possible calls to a particular mode of a predicate or function can return to the caller, then that mode has a determinism of erroneous.

This module will implement fibonacci /2 with the *function* pattern, similar to the *predicate* pattern but with a more familiar layout.

<<fibonacci.m>>=:- modulefibonacci.:- interface.:- funcfibonacci(int)= int./* an alternative way, using predicates would be * :- pred fibonacci( int, int). */ /* mode first_param as input '=' result as output is deterministic (has one solution) */:- modefibonacci(in)=outis det.:- implementation.:- import_module int./* fibonacci(N) = F implies ( cond_goal -> then_goal * ; cond_goal -> then_goal * ; else_goal * ) */ fibonacci(N)= F :-(N = 0 -> F = 0;N = 1 -> F = 1;/* else */ F = fibonacci(N - 1)+ fibonacci(N - 2)).

Test module:

<<fibotest.m>>=:- modulefibotest.:- interface.:- import_module io.:- predmain(io.state,io.state).:- modemain(di,uo)is det.:- implementation.:- import_module fibonacci.main --> io.write_string("fibonacci(7) = "),io.write_int(fibonacci(7)),io.nl.

Compilation and run

- compile fibonacci.m exporting interfaces (-i)
- compile fibotest.m specifying the interfaces used (without extension)

>mmc -i fibonacci.m >mmc fibotest.m fibonacci > >fibotest >fibonacci(7) = 13 >

## Tail Recursive

<<fibonacci_tr.m>>=:- modulefibonacci_tr.:- interface.:- funcfibonacci(int)= int.:- modefibonacci(in)=outis det.:- implementation.:- import_module int.fibonacci(N)= F :- F = fibo_tr(N,1,0)./* tail recursive private function */:- funcfibo_tr(int,int,int)= int.:- modefibo_tr(in,in,in)=outis det.fibo_tr(N,Next,Result)= F :-(N = 0 -> F = Result;/* else */ F = fibo_tr(N - 1,Result + Next,Next)).

Download code |