# Fibonacci numbers (Erlang)

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 are the fibo functions possible in this all functional language and runtime.

To test them we pass the function as parameter to the print_nfibos/2.

## The fibonacci function

<<regular recursive fibonacci>>=
fibo(0) -> 0 ;
fibo(1) -> 1 ;
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .


## Tail recursive fibonacci

Given that the series of pairs of consecutive fibo values can be expressed in the following way

S0 = (fib0, fib1) = (0, 1) ;

for n >= 1, succ (fibn-1, fibn) = (fibn, fibn+1) = (fibn, fibn-1 + fibn) ;

Naming (fibn-1, fibn) as (result, next) then succ (result, next) = (next, (result+next))

<<tail recursive fibonacci>>=
fibo2_tr( 0, Result, _Next) -> Result ;  %% last recursion output
fibo2_tr( Iter, Result, Next) when Iter > 0 -> fibo2_tr( Iter -1, Next, Result + Next) .
fibo2( N) -> fibo2_tr( N, 0, 1) .


## Fast tail recursive fibonacci

Using the following formula we can derive a few useful identities to speed up the computation.

Here are the useful identities:

Fn + m = Fn − 1Fm + FnFm + 1 = (Fn + 1Fn)Fm + FnFm + 1
Fn + m + 1 = FnFm + Fn + 1Fm + 1

If we can keep track of pairs of fibonacci numbers we end up with an algorithm identical to exponentiation by squaring:

<<fast fibonacci>>=
fibo3(N) ->
{Fib, _} = fibo3(N, {1, 1}, {0, 1}),
Fib.
fibo3(0, _, Pair) -> Pair;
fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 ->
SquareFib1 = Fib1*Fib1,
fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair);
fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) ->
fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}).


## Test module

Let's print N fibonacci numbers in ascending order.

<<fib.erl>>=
-module(fib).
-export([fibo/1, fibo2/1, fibo3/1, print_nfibos/2]).
%% print fibo arg. and result, with function as parameter
print_nfibos( N, FiboFunc) -> printfibos( N, FiboFunc, 0).
printfibos( 0, FiboFunc, N) ->  %% last recursion
Res = FiboFunc(N),
io:fwrite("~w ~w~n", [N, Res]) ;
printfibos( Iter, FiboFunc, N) when Iter > 0 ->
Res = FiboFunc(N),
io:fwrite("~w ~w~n", [N, Res]),
printfibos( Iter -1, FiboFunc, N +1).
regular recursive fibonacci
tail recursive fibonacci
fast fibonacci


## Testing with the bytecode interpreter

erl> c(fib). %% compile fib.erl to bytecode
{ok,fib}
> fib:print_nfibos(10, fun fib:fibo/1). %% print n fibo values with function fib:fibo/1


produces the output

0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
ok


Change the second parameter to "fun fib:fibo2/1" or "fun fib:fibo3/1" and you will get the same result, but faster.