Erlang - Ricorsione

La ricorsione è una parte importante di Erlang. Per prima cosa vediamo come possiamo implementare la ricorsione semplice implementando il programma fattoriale.

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

Le seguenti cose devono essere annotate sul programma di cui sopra:

• Per prima cosa definiamo una funzione chiamata fac (N).

• Siamo in grado di definire la funzione ricorsiva chiamando ricorsivamente fac (N).

L'output del programma di cui sopra è:

Produzione

24

Approccio pratico alla ricorsione

In questa sezione, comprenderemo in dettaglio i diversi tipi di ricorsioni e il loro utilizzo in Erlang.

Ricorsione della lunghezza

Un approccio più pratico alla ricorsione può essere visto con un semplice esempio utilizzato per determinare la lunghezza di una lista. Un elenco può avere più valori come [1,2,3,4]. Usiamo la ricorsione per vedere come ottenere la lunghezza di un elenco.

Example

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

Le seguenti cose devono essere annotate sul programma di cui sopra:

• La prima funzione len([]) viene utilizzato per la condizione del caso speciale se l'elenco è vuoto.

• Il [H|T] modello da confrontare con elenchi di uno o più elementi, poiché un elenco di lunghezza uno verrà definito come [X|[]] e un elenco di lunghezza due sarà definito come [X|[Y|[]]]. Nota che il secondo elemento è una lista stessa. Ciò significa che dobbiamo solo contare il primo e la funzione può chiamare se stessa sul secondo elemento. Dato ogni valore in un elenco conta come una lunghezza di 1.

L'output del programma di cui sopra sarà:

Output

4

Ricorsione della coda

Per capire come funziona la ricorsione in coda, capiamo come funziona il codice seguente nella sezione precedente.

Syntax

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

La risposta a 1 + len (Riposo) necessita della risposta di len (Riposo) per essere trovata. La stessa funzione len (Rest) necessitava quindi del risultato di un'altra chiamata di funzione. Le aggiunte verranno impilate fino a trovare l'ultima, e solo allora verrà calcolato il risultato finale.

La ricorsione in coda mira a eliminare questo accumulo di operazioni riducendole man mano che si verificano.

Per ottenere ciò, avremo bisogno di mantenere una variabile temporanea aggiuntiva come parametro nella nostra funzione. La suddetta variabile temporanea è talvolta chiamata accumulatore e funge da luogo in cui memorizzare i risultati dei nostri calcoli mentre si verificano al fine di limitare la crescita delle nostre chiamate.

Diamo un'occhiata a un esempio di ricorsione della coda:

Example

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

L'output del programma di cui sopra è:

Output

4

Duplicare

Diamo un'occhiata a un esempio di ricorsione. Questa volta scriviamo una funzione che prende un intero come primo parametro e poi qualsiasi altro termine come secondo parametro. Quindi creerà un elenco di tutte le copie del termine specificate dall'intero.

Diamo un'occhiata a come apparirebbe un esempio di questo:

-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 di cui sopra sarà:

Produzione

1,
1,
1,
1,
1,

Inversione elenco

Non ci sono limiti a cui puoi usare la ricorsione in Erlang. Vediamo ora rapidamente come possiamo invertire gli elementi di una lista usando la ricorsione. Il seguente programma può essere utilizzato per eseguire questa operazione.

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 di cui sopra sarà:

Produzione

[4,3,2,1]

Le seguenti cose devono essere annotate sul programma di cui sopra:

• Stiamo ancora usando il concetto di variabili temporanee per memorizzare ogni elemento della lista in una variabile chiamata Acc.

• Quindi chiamiamo tail_reverse ricorsivamente, ma questa volta ci assicuriamo che l'ultimo elemento venga inserito per primo nel nuovo elenco.

• Quindi chiamiamo ricorsivamente tail_reverse per ogni elemento nell'elenco.