Fibonacci Sequence in Erlang

Fibonacci Sequence in Erlang

We’ve seen the Fibonacci example in multiple languages, but none of them purely functional.

Erlang is a functional, dynamically-typed language designed to build concurrent, distributed, fault-tolerant systems. It is more than 30 years old however the feature set seems incredibly prescient to the challenges we face in the multi-core era today. It has a variety of paradigms that may be foreign to developers that are used to working in object oriented languages, but rather than a problem, things like immutable variables and the lack of loop constructs encourage an elegance in implementation.

Let us try few different algorithmic approaches to the Fibonacci sequence in Erlang. A classic example of implementing Fibonacci using recursion is the literal representation of the algorithm, which ends up being rather computationally intensive. It looks elegant but starts getting slow around N = 35. This is because N is recomputed recursively every time it is used!

fib_algo1(0) -> 0;  
fib_algo1(1) -> 1;  
fib_algo1(N) when N > 0 -> fib_algo1(N-1) + fib_algo1(N-2).  

Here's an example of a slightly better algorithm, where each value is accumulated in a list and looked up rather than recomputed. There's also an io: format print statement that returns the final sequence of N numbers. This algorithm is way faster than the inefficient version above.

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

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

The 3rd algorithm is the most efficient one. It computes the value but does not store it in a list. It also eliminates the risk of filling up memory with the list of previous numbers.

fib_algo3(1) -> 1;  
fib_algo3(2) -> 1;  
fib_algo3(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 the 3 algorithms in a module:-

-module(fibonacci).
-compile(export_all).

% get nth Fibonacci number without much memory usage
% quite fast, gets nth number with no list storage

test() ->  
    13 = fib_algo3(7),
    13 = fib_algo2(7),
    13 = fib_algo1(7),
    done.

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

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

% fibonacci sequence made by accumulating values in a list
fib_algo2(1) -> io:format("~p~n",[[1]]);  
fib_algo2(2) -> io:format("~p~n",[[1,1]]);  
fib_algo2(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]).

% inefficient recursive method for fibonacci computation
% very slow at N = 35
fib_algo1(0) -> 0;  
fib_algo1(1) -> 1;  
fib_algo1(N) when N > 1 -> fib_algo1(N-1) + fib_algo1(N-2).  
Subscribe to Merutan