Recursão do Erlang

A recursão é uma parte importante do Erlang. Primeiro, vamos ver como implementar um programa simples de factorial para realizar recursão.

Exemplo

-module(helloworld).　
-export([fac/1,start/0]).　
fac(N) quando N == 0　->　1;　
fac(N) quando N > 0　-> N*fac(N-1.　
start()　->　
　　　X = fac(4,　
　　　io:fwrite("~w",[X]).

Sobre o programa acima, é importante notar os seguintes pontos:

• Primeiro, definimos uma função chamada fac(N).

• Podemos definir uma função recursiva definindo fac(N) por chamadas recursivas.

A saída do programa acima é:

Saída

24

Método prático de recursão

Nesta seção, vamos entender em detalhes os diferentes tipos de recursão e sua utilização no Erlang.

Recursão de comprimento

Um método mais prático de recursão pode ser observado em um exemplo simples de determinar o comprimento de uma lista. Uma lista pode ter vários valores, como [1,2,3,4Vamos usar a recursão para ver como obter o comprimento de uma lista.

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

Sobre o programa acima, é importante notar os seguintes pontos:

• se a lista estiver vazia, o primeiro len([]) é usado para o caso especial da condição.

• o padrão [H|T] para combinar uma ou mais listas, como o comprimento de1a lista será definida como [X|[]], e o comprimento será　2　a lista será definida como [X|[Y|[]]] .　　

• Atenção, o segundo elemento é a lista em si. Isso significa que precisamos contar apenas o primeiro, e a função pode se chamar a si mesma no segundo elemento. A contagem de comprimento de cada valor na lista será　1　.
  

A saída do programa acima será

4

Tail recursion

Para entender como a tail recursion funciona, vamos entender como o seguinte código do último capítulo funciona.

Sintaxe

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

1 + A resposta de len (Rest) precisa encontrar a resposta de len (Rest). Em seguida, a função len (Rest) precisa encontrar o resultado de outra chamada de função. A parte adicionada se acumulará até encontrar a última, e então o resultado final pode ser calculado.

A tail recursion visa eliminar essas operações de pilha aumentando-as ao longo do tempo da operação.

Para isso, precisamos manter uma variável temporária extra como parâmetro na função. A variável temporária mencionada anteriormente às vezes é chamada de accumulator e é usada como um lugar para armazenar o resultado da computação, para limitar o crescimento das chamadas.

Vamos ver um exemplo de 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]).

A saída do programa acima é

4

Réplicas (cópia)

Vamos ver um exemplo de recursão. Desta vez, vamos escrever uma função que tome um inteiro como primeiro parâmetro e qualquer outro item como segundo parâmetro. Em seguida, ela criará uma lista de réplicas do termo especificado pelo inteiro.

Vamos ver um exemplo de tal-

-module(helloworld).　
-export([duplicate/2,start/0]).　
duplicate(0,_)　->　
　　　[];　
duplicate(N,Term) quando N > 0　->
　　　io:fwrite("~w,~n",[Term]),
　　　[Term|duplicate(N-1,Term)].　
start()　->　
　　　duplicate(5,1.

A saída do programa acima será-

Saída

1,
1,
1,
1,
1,

Inversão de lista

No há limites para a recursão em Erlang. Vamos rapidamente ver como usar a recursão para inverter os elementos de uma lista. Pode-se usar o seguinte programa para realizar essa operação.

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

A saída do programa acima será-

Saída

[4,3,2,1]

Sobre o programa acima, é importante notar os seguintes pontos:

• Novamente, usamos o conceito de variável temporária para armazenar cada elemento da lista em uma variável chamada Acc.

  Em seguida, chama recursivamente tail_reverse, mas dessa vez, garantimos que o último elemento seja colocado primeiro na nova lista.

  Em seguida, chama recursivamente tail_reverse para cada elemento da lista.