Erlang - Récursivité

La récursivité est une partie importante d'Erlang. Voyons d'abord comment nous pouvons implémenter une récursion simple en implémentant le programme factoriel.

Exemple

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

Les choses suivantes doivent être notées à propos du programme ci-dessus -

  • Nous définissons d'abord une fonction appelée fac (N).

  • Nous sommes capables de définir la fonction récursive en appelant fac (N) récursivement.

La sortie du programme ci-dessus est -

Production

24

Approche pratique de la récursivité

Dans cette section, nous allons comprendre en détail les différents types de récursions et son utilisation à Erlang.

Récurrence de longueur

Une approche plus pratique de la récursivité peut être vue avec un exemple simple qui est utilisé pour déterminer la longueur d'une liste. Une liste peut avoir plusieurs valeurs telles que [1,2,3,4]. Utilisons la récursivité pour voir comment nous pouvons obtenir la longueur d'une liste.

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

Les choses suivantes doivent être notées à propos du programme ci-dessus -

  • La première fonction len([]) est utilisé pour la condition de cas particulier si la liste est vide.

  • le [H|T] motif à faire correspondre avec des listes d'un ou plusieurs éléments, comme une liste de longueur un sera défini comme [X|[]] et une liste de longueur deux sera définie comme [X|[Y|[]]]. Notez que le deuxième élément est une liste elle-même. Cela signifie que nous devons seulement compter le premier et que la fonction peut s'appeler sur le deuxième élément. Étant donné que chaque valeur dans une liste compte pour une longueur de 1.

La sortie du programme ci-dessus sera -

Output

4

Récurrence de la queue

Pour comprendre comment fonctionne la récursivité de queue, comprenons comment fonctionne le code suivant de la section précédente.

Syntax

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

La réponse à 1 + len (Rest) nécessite la réponse de len (Rest) à trouver. La fonction len (Rest) elle-même avait alors besoin du résultat d'un autre appel de fonction pour être trouvé. Les ajouts seraient empilés jusqu'à ce que le dernier soit trouvé, et alors seulement le résultat final serait calculé.

La récursivité de queue vise à éliminer cet empilement d'opérations en les réduisant au fur et à mesure qu'ils se produisent.

Pour ce faire, nous devrons contenir une variable temporaire supplémentaire en tant que paramètre dans notre fonction. La variable temporaire précitée est parfois appelée accumulateur et sert de lieu de stockage des résultats de nos calculs au fur et à mesure de leur déroulement afin de limiter la croissance de nos appels.

Regardons un exemple de récursion de queue -

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

La sortie du programme ci-dessus est -

Output

4

Dupliquer

Regardons un exemple de récursivité. Cette fois-ci, écrivons une fonction qui prend un entier comme premier paramètre, puis tout autre terme comme deuxième paramètre. Il créera ensuite une liste d'autant de copies du terme que spécifié par l'entier.

Regardons à quoi ressemblerait un exemple de ceci -

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

La sortie du programme ci-dessus sera -

Production

1,
1,
1,
1,
1,

Annulation de liste

Il n'y a pas de limites auxquelles vous pouvez utiliser la récursivité dans Erlang. Voyons maintenant rapidement comment inverser les éléments d'une liste en utilisant la récursivité. Le programme suivant peut être utilisé pour ce faire.

Exemple

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

La sortie du programme ci-dessus sera -

Production

[4,3,2,1]

Les choses suivantes doivent être notées à propos du programme ci-dessus -

  • Nous utilisons à nouveau le concept de variables temporaires pour stocker chaque élément de la liste dans une variable appelée Acc.

  • Nous appelons alors tail_reverse récursivement, mais cette fois-ci, nous nous assurons que le dernier élément est mis en premier dans la nouvelle liste.

  • Nous appelons ensuite récursivement tail_reverse pour chaque élément de la liste.