Erlang 递归

La ricorsione è una parte importante di Erlang. Prima di tutto, vediamo come implementare un programma semplice di factorial per illustrare la ricorsione.

Esempio

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

Riguardo al programma sopra, ci sono alcuni punti da notare:

• Prima di tutto, definiamo una funzione chiamata fac(N).

• Possiamo definire la funzione ricorsiva fac(N) chiamando ricorsivamente fac(N).

L'output del programma sopra è:

Output

24

Metodo pratico della ricorsione

In questa sezione, esploreremo in dettaglio i diversi tipi di ricorsione e il loro uso in Erlang.

Ricorsione della lunghezza

Un metodo più pratico della ricorsione può essere visto da un semplice esempio per determinare la lunghezza di una lista. Una lista può avere più valori, come [1,2,3,4]. Vediamo come ottenere la lunghezza di una lista utilizzando la ricorsione.

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

Riguardo al programma sopra, ci sono alcuni punti da notare:

• Se la lista è vuota, la funzione len([]) è utilizzata per il caso speciale delle condizioni.

• [H|T] pattern to match a list of one or more elements, such as a list of length 1 is defined as [X|[]], and a list of length 2 is defined as [X|[Y|[]]].　　

• Note that the second element is the list itself. This means that we only need to count the first, and the function can call itself on the second element. The length count of each value given in the list is 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).

The answer to 1 + 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 additional 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 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 times as the integer specifies.

Let's 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).

L'output del programma sopra sarà -

Output

1,
1,
1,
1,
1,

List Reversal

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

Esempio

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

L'output del programma sopra sarà -

Output

[4,3,2,1]

Riguardo al programma sopra, ci sono alcuni punti da notare:

• Riutilizziamo il concetto di variabile temporanea per memorizzare ogni elemento della lista in una variabile chiamata Acc.

  Chiamiamo nuovamente tail_reverse, ma questa volta assicuriamo che l'ultimo elemento venga messo nella nuova lista.

  Poi chiamiamo tail_reverse su ogni elemento della lista.