Erlang - Recursion

Advertisements

Previous Page
Next Page  

Recursion is an important part of Erlang. First let’s see how we can implement simple recursion by implementing the factorial program.

Example

Live Demo 
-module(helloworld). 
-export([fac/1,start/0]). 

fac(N) when N == 0 -> 1; 
fac(N) when N > 0 -> N*fac(N-1). 

start() -> 
   X = fac(4), 
   io:fwrite("~w",[X]).

The following things need to be noted about the above program −

  • We are first defining a function called fac(N).

  • We are able to define the recursive function by calling fac(N) recursively.

The output of the above program is −

Output

24

Practical Approach to Recursion

In this section, we will understand in detail the different types of recursions and its usage in Erlang.

Length Recursion

A more practical approach to recursion can be seen with a simple example which is used to determine the length of a list. A list can have multiple values such as [1,2,3,4]. Let’s use recursion to see how we can get the length of a list.

Example

Live Demo 
-module(helloworld). 
-export([len/1,start/0]). 

len([]) -> 0; 
len([_|T]) -> 1 + len(T). 

start() -> 
   X = [1,2,3,4], 
   Y = len(X), 
   io:fwrite("~w",[Y]).

The following things need to be noted about the above program −

  • The first function len([]) is used for the special case condition if the list is empty.

  • The [H|T] pattern to match against lists of one or more elements, as a list of length one will be defined as [X|[]] and a list of length two will be defined as [X|[Y|[]]]. Note that the second element is a list itself. This means we only need to count the first one and the function can call itself on the second element. Given each value in a list counts as a length of 1.

The output of the above program will be −

Output

4

Tail Recursion

To understand how the tail recursion works, let’s understand how the following code in the previous section works.

Syntax

len([]) -> 0; 
len([_|T]) -> 1 + len(T).

The answer to 1 + len(Rest) needs the answer of len(Rest) to be found. The function len(Rest) itself then needed the result of another function call to be found. The additions would get stacked until the last one is found, and only then would the final result be calculated.

Tail recursion aims to eliminate this stacking of operation by reducing them as they happen.

In order to achieve this, we will need to hold an extra temporary variable as a parameter in our function. The aforementioned temporary variable is sometimes called accumulator and acts as a place to store the results of our computations as they happen in order to limit the growth of our calls.

Let’s look at an example of tail recursion −

Example

Live Demo 
-module(helloworld).
-export([tail_len/1,tail_len/2,start/0]). 

tail_len(L) -> tail_len(L,0). 
tail_len([], Acc) -> Acc; 
tail_len([_|T], Acc) -> tail_len(T,Acc+1). 

start() -> 
   X = [1,2,3,4], 
   Y = tail_len(X), 
   io:fwrite("~w",[Y]).

The output of the above program is −

Output

4

Duplicate

Let’s look at an example of recursion. This time around let’s write a function which takes an integer as its first parameter and then any other term as its second parameter. It will then create a list of as many copies of the term as specified by the integer.

Let’s look at how an example of this would look like −

Live Demo 
-module(helloworld). 
-export([duplicate/2,start/0]). 

duplicate(0,_) -> 
   []; 
duplicate(N,Term) when N > 0 ->
   io:fwrite("~w,~n",[Term]),
   [Term|duplicate(N-1,Term)]. 
start() -> 
   duplicate(5,1).

The output of the above program will be −

Output

1,
1,
1,
1,
1,

List Reversal

There are no bounds to which you can use recursion in Erlang. Let’s quickly now look at how we can reverse the elements of a list using recursion. The following program can be used to accomplish this.

Example

Live Demo 
-module(helloworld). 
-export([tail_reverse/2,start/0]). 

tail_reverse(L) -> tail_reverse(L,[]).

tail_reverse([],Acc) -> Acc; 
tail_reverse([H|T],Acc) -> tail_reverse(T, [H|Acc]).

start() -> 
   X = [1,2,3,4], 
   Y = tail_reverse(X), 
   io:fwrite("~w",[Y]).

The output of the above program will be −

Output

[4,3,2,1]

The following things need to be noted about the above program −

  • We are again using the concept of temporary variables to store each element of the List in a variable called Acc.

  • We then call tail_reverse recursively, but this time around, we ensure that the last element is put in the new list first.

  • We then recursively call tail_reverse for each element in the list.

Advertisements