# 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 : Tech Blog for Geeks

Get the latest posts delivered right to your inbox