Erlang - Recursão

A recursão é uma parte importante do Erlang. Primeiro, vamos ver como podemos implementar recursão simples implementando o programa fatorial.

Exemplo

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

As seguintes coisas precisam ser observadas sobre o programa acima -

Estamos primeiro definindo uma função chamada fac (N).
Podemos definir a função recursiva chamando fac (N) recursivamente.

O resultado do programa acima é -

Resultado

Abordagem prática para recursão

Nesta seção, entenderemos em detalhes os diferentes tipos de recursões e seu uso em Erlang.

Recursão de comprimento

Uma abordagem mais prática para a recursão pode ser vista com um exemplo simples que é usado para determinar o comprimento de uma lista. Uma lista pode ter vários valores, como [1,2,3,4]. Vamos usar a recursão para ver como podemos obter o comprimento de uma lista.

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

As seguintes coisas precisam ser observadas sobre o programa acima -

A primeira função len([]) é usado para a condição de caso especial se a lista estiver vazia.
o [H|T] padrão para combinar com listas de um ou mais elementos, como uma lista de comprimento um será definido como [X|[]] e uma lista de comprimento dois será definida como [X|[Y|[]]]. Observe que o segundo elemento é a própria lista. Isso significa que só precisamos contar o primeiro e a função pode chamar a si mesma no segundo elemento. Dado que cada valor em uma lista conta como um comprimento de 1.

O resultado do programa acima será -

Output

Recursão de cauda

Para entender como funciona a recursão de cauda, vamos entender como funciona o código a seguir na seção anterior.

Syntax

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

A resposta para 1 + len (Rest) precisa da resposta de len (Rest) para ser encontrada. A própria função len (Rest) então precisava do resultado de outra chamada de função para ser encontrada. As adições seriam empilhadas até que a última fosse encontrada, e somente então o resultado final seria calculado.

A recursão de cauda visa eliminar esse empilhamento de operações, reduzindo-os à medida que acontecem.

Para conseguir isso, precisaremos manter uma variável temporária extra como um parâmetro em nossa função. A variável temporária mencionada é algumas vezes chamada de acumulador e atua como um local para armazenar os resultados de nossos cálculos à medida que eles acontecem, a fim de limitar o crescimento de nossas chamadas.

Vejamos um exemplo de recursão de cauda -

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

O resultado do programa acima é -

Output

Duplicado

Vejamos um exemplo de recursão. Desta vez, vamos escrever uma função que tenha um inteiro como seu primeiro parâmetro e qualquer outro termo como seu segundo parâmetro. Em seguida, ele criará uma lista de tantas cópias do termo quanto especificado pelo número inteiro.

Vejamos como seria um exemplo disso -

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

O resultado do programa acima será -

Resultado

1,
1,
1,
1,
1,

Lista de reversão

Não há limites para os quais você possa usar a recursão em Erlang. Vejamos rapidamente como podemos reverter os elementos de uma lista usando recursão. O programa a seguir pode ser usado para fazer isso.

Exemplo

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

O resultado do programa acima será -

Resultado

[4,3,2,1]

As seguintes coisas precisam ser observadas sobre o programa acima -

Estamos novamente usando o conceito de variáveis temporárias para armazenar cada elemento da Lista em uma variável chamada Acc.
Nós então ligamos tail_reverse recursivamente, mas desta vez, garantimos que o último elemento seja colocado primeiro na nova lista.
Em seguida, chamamos recursivamente tail_reverse para cada elemento na lista.