Erlang Recursion

Recursion is an important part of Erlang. Firstly, let's see how to implement simple recursion by implementing the factorial program.

Instance

-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]).

For the above program, the following points should be noted:

• Firstly, we define a function named fac(N).

• We can define a recursive function by calling fac(N) recursively.

The output of the above program is:

Output

24

Practical Method of Recursion

In this section, we will learn in detail about the different types of recursion and their usage in Erlang.

Recursive Length

A more practical method of recursion can be seen from a simple example 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 to get the length of a list.

-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]).

For the above program, the following points should be noted:

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

• [H|T] pattern to match a list with one or more elements, such as a list of length1The list will be defined as [X|[]], and the length will be　2　The list will be defined as [X|[Y|[]]] .　　

• Note that the second element is the list itself. This means that we only need to count the first one, and the function can call itself on the second element. The length of the list given for each value is counted as　1　.
  

The output of the above program will be

4

Tail Recursion

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

Syntax

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

1 + The answer to len (Rest) needs to find the answer to len (Rest). Then the function len (Rest) itself needs to find the result of another function call. The added part will stack up until the last one is found, and then the final result can be calculated.

Tail recursion aims to eliminate this stack operation by reducing them as they occur.

To achieve this, we need to keep an extra temporary variable as a parameter in the function. The temporary variable mentioned earlier is sometimes called an accumulator, used as a place to store the result of the calculation to limit the growth of calls.

Let's take a look at an example of tail recursion

-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

4

Duplicate (Copy)

Let's look at a recursive example. This time, let's write a function that takes an integer as the first parameter and then any other item as the second parameter. Then, it will create a list of terms as many as the integer specifies.

Let's take a look at such an example-

-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

In Erlang, recursion can be used without any restrictions. Now let's quickly take a look at how to use recursion to reverse the elements of a list. The following program can be used to perform this operation.

Instance

-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]

For the above program, the following points should be noted:

• We use the concept of temporary variables again to store each element of the list in a variable named Acc.

  Then recursively call tail_reverse, but this time, we ensure that the last element is placed in the new list first.

  Then recursively call tail_reverse for each element in the list.