Rixiform Inc.

Fibonacci Sequence Recursion in Erlang

February 16th 2008

Erlang uses recursion extensively – so lets do some classic Fibonacci sequence recursion code katas for Erlang. Note, that I define things a little differently than the Wikipedia example I just linked to. In the algorithms below, I have defined the first first two elements as = 1 and there is no N defined for 0. So: fib(1) = 1, fib(2)=1, and fib(N) where N > 2 = fib(N -1) fib(N – 2).

For fun, lets try a few different algorithmic approaches to this sequence. The classic example of Fibonacci sequence recursion is a literal representation of the algorithm, which ends up being rather computationally intensive. It looks rather elegant but starts getting massively slow around N = 35. This is because N is recomputed recursively every time it is used!

fib_slow(1) -> 1;
fib_slow(2) -> 1;
fib_slow(N) -> fib_slow(N-1) + fib_slow(N-2).

Here’s an example of a different algorithm, where each value is accumulated in a list and looked up rather than recomputed. There also is a io:format print statement that returns the final sequence of N numbers. This method is a lot faster than the inefficient version above. You can set N = 1,000 without much fuss. If you comment out the print statement you can get to N = 20,000 speedily.

fib_list(1) -> io:format("~p~n",[[1]]);
fib_list(2) -> io:format("~p~n",[[1,1]]);
fib_list(N) when N > 2 -> 
    hd( fib_list1(N-1,[1,1]) ).

% delegate for numbers greater than 2
fib_list1(1,L) ->
    io:format("~p~n",[lists:reverse(L)]),
    L;
fib_list1(N,L) ->
    [H1,H2|_T] = L,
    fib_list1(N-1,[H1 + H2 | L]).

The final method computes the value but does not store it in a list. This one is the fastest (although I have not benchmarked them). This method also eliminates the risk of filling up memory with the list of previous numbers. N = 50,000 breezes by with this algorithm on my 2.2 Ghz Intel Dual Core MacBook Pro.

fib(1) -> 1;
fib(2) -> 1;
fib(N) when N > 2 -> fib1(N,1,1).

fib1(3,P1,P2) -> P1 + P2; 
fib1(N,P1,P2) ->
fib1(N-1,P2, P1 + P2).

Here are all of the different approaches (in reverse orer) in a module.

-module(fib2).
-compile(export_all).
% get nth fibonacci no storage
% quite fast, get's nth number with no list storage

test() ->
    13 = fib(7),
    13 = fib_list(7),
    13 = fib_slow(7),
    horray.

fib(1) -> 1;
fib(2) -> 1;
fib(N) when N > 2 -> fib1(N,1,1).

fib1(3,P1,P2) -> P1 + P2; 
fib1(N,P1,P2) ->
    fib1(N-1,P2, P1 + P2).

% fib sequence made by accumulating values in a list
% pretty fast even at N = 20,000.
fib_list(1) -> io:format("~p~n",[[1]]);
fib_list(2) -> io:format("~p~n",[[1,1]]);
fib_list(N) when N > 2 -> 
    hd( fib_list1(N-1,[1,1]) ).

%delegate for numbers > 2
fib_list1(1,L) ->
    io:format("~p~n",[lists:reverse(L)]),
    L;
fib_list1(N,L) ->
    [H1,H2|_T] = L,
    fib_list1(N-1,[H1 + H2 | L]).

% ineficient recursive method for fibonacci computation
% very slow at N = 35
fib_slow(1) -> 1;
fib_slow(2) -> 1;
fib_slow(N) -> fib_slow(N-1) + fib_slow(N-2).