Recursion Erlang

La récursion est une composante importante d'Erlang.Tout d'abord, regardons comment réaliser une récursion simple en implémentant le programme factorial.

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

Pour le programme ci-dessus, il est important de noter les points suivants :

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

• Nous pouvons définir une fonction récursive en appelant récursivement fac(N).

La sortie du programme ci-dessus est :

Sortie

24

Méthode pratique de récursion

Dans cette section, nous allons examiner en détail les différents types de récursion et leur utilisation en Erlang.

Récursion en longueur

Une méthode plus pratique de la récursion peut être observée à partir d'un exemple simple déterminant la longueur d'une liste. Une liste peut avoir plusieurs valeurs, comme [1,2,3,4]. Regardons comment obtenir la longueur d'une liste en utilisant la récursion.]}

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

Pour le programme ci-dessus, il est important de noter les points suivants :

• Si la liste est vide, la fonction len([]) est utilisée pour le cas spécial des conditions.

• Pour matcher une ou plusieurs éléments de la liste, comme la longueur de1La liste sera définie comme [X|[]], et la longueur sera　2　La liste sera définie comme [X|[Y|[]]] .　　

• Notez que le deuxième élément est la liste elle-même. Cela signifie que nous n'avons besoin de compter que le premier, et la fonction peut s'appeler elle-même sur le deuxième élément. La longueur de chaque valeur dans la liste donnée est comptée comme　1　.
  

La sortie du programme suivant sera

4

Récursion terminale

Pour comprendre comment fonctionne la récursion terminale, regardons le code suivant de la section précédente.

Grammaire

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

1 + La réponse de len (Rest) nécessite de trouver la réponse de len (Rest) elle-même. Ensuite, la fonction len (Rest) elle-même doit trouver le résultat d'une autre appel de fonction. La partie ajoutée se pile jusqu'à ce que la dernière soit trouvée, puis le résultat final peut être calculé.

La récursion terminale vise à éliminer ces opérations de pile en réduisant leur nombre à chaque opération.

Pour cela, nous devons conserver une variable temporaire supplémentaire en tant que paramètre dans la fonction. Le variable temporaire mentionné précédemment est parfois appelé accumulator, utilisé pour stocker l'endroit où se trouvent les résultats de calcul pour limiter la croissance des appels.

Regardons un exemple de récursion terminale

-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

4

Répétition (copie)

Regardons un exemple de récursion. Cette fois, écrivons une fonction qui prend un entier comme premier paramètre, puis prend tout autre élément comme second paramètre. Ensuite, elle crée une liste de répétitions du terme spécifié par l'entier.

Regardons un tel exemple-

-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 suivant sera-

Sortie

1,
1,
1,
1,
1,

Inversion de liste

En Erlang, on peut utiliser la récursion sans aucune limitation. Maintenant, regardons rapidement comment utiliser la récursion pour inverser les éléments d'une liste. On peut utiliser le programme suivant pour effectuer cette opération.

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

La sortie du programme suivant sera-

Sortie

[4,3,2,1]

Pour le programme ci-dessus, il est important de noter les points suivants :

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

  Ensuite, appeler récursivement tail_reverse, mais cette fois, nous nous assurons que l'élément final est placé en premier dans la nouvelle liste.

  Ensuite, appeler récursivement tail_reverse pour chaque élément de la liste.