Haskell/Recursividade: diferenças entre revisões

Em Haskell, podemos escrever esta função usando em termos de si mesma usando casamento de padrões:

 

fatorial 0 = 1

fatorial n = n * fatorial (n - 1)

 

A primeira linha é o caso base, e a segunda, é o caso recursivo, que chama <code>fatorial</code> novamente. Perceba o uso de parênteces na segunda linha: sem eles, Haskell interpretaria a segunda linha como sendo <code>n * (fatorial n) - 1</code>.

{{Exercício|1=

# O que acontece se calcularmos <code>fatorial (-1)</code>?

fatorial n = n * fatorial (n - 1)

fatorial 0 = 1

# O ''fatorial duplo'' de um número é a multiplicação dos sucessores intercalados, partindo de 1 (ou 2) até o argumento. Por exemplo: o fatorial duplo de 8 é 8 × 6 × 4 × 2 = 384; o fatorial duplo de 7 é 7 × 5 × 3 × 1 = 105. Defina uma função <code>fatorialDuplo</code> em Haskell que faça esta conta.

}}

Em linguagens de programação imperativas, usam-se ''laços de repetição'' no mesmo contexto em que usamos recursividade em Haskell. Por exemplo, em [[w:C (linguagem de programação)|C]], poderíamos usar o laço ''for'' para escrever uma <code>fatorial</code> da seguinte forma:

 

int fatorial(int n) {

int res = 1;

return res;

}

 

O laço ''for'' faz com que <code>res</code> seja multiplicada por <code>n</code> repetidamente. Depois de cada repetição, a operação <code>n--</code> é realizada, isto é, <code>n</code> é decrescido de uma unidade. O laço é interrompido quando a condição <code>n > 1</code>, não for mais válida, ou seja, quando <code>n</code> já não for maior que <code>1</code>.

Não é possível criar uma versão parecida em Haskell, pois a linguagem não permite a alteração de valores de uma variável, como acontece com <code>n</code> e <code>res</code> na versão em C. Entretanto, é possível converter um laço num forma recursiva equivalente. Para isso, fazemos com que cada variável do laço torne-se um argumento de uma função recursiva. Por exemplo:

 

fatorial n = aux n 1

where aux n res

| n > 1 = aux (n - 1) (res * n)

| otherwise = res

 

<code>aux</code><ref group=nota>É mais comum que funções auxiliares em Haskell sejam chamadas de <code>go</code> (''go'' significa "ir", ou "vai", em inglês), ou <code>worker</code> ("trabalhador", em inglês), do que <code>aux</code>.</ref> é uma função auxiliar. É ela que, de fato, realiza o cálculo, enquanto que <code>fatorial</code> apenas a envolve. Na função <code>aux</code>, temos dois argumentos: <code>n</code>, que vem de fora, e é definido pelo usuário quando chama <code>fatorial n</code>; e <code>res</code>, que chamamos de ''parâmetro acumulador'', pois ele acumula os resultados parciais do cálculo do fatorial, e depois é enviado para a saída de <code>aux</code> na cláusula <code>otherwise</code>.

Apesar de ser muito útil, não há nada de muito especial com a implementação de <code>fatorial</code>, e também existem muitas outras funções recursivas na Matemática. Por exemplo, a própria multiplicação pode ser definida recursivamente. Sabemos que, para números inteiros, trata-se da repetição da operação de adição, isto é, 5 × 4 é o mesmo que 5 + 5 × 3, que é o mesmo que 5 + 5 + 5 × 2, e assim em diante. Portanto, em Haskell poderíamos definir a função <code>mult</code> que realiza multiplicação desta forma:

 

mult _ 0 = 0 -- caso base: n * 0 = 0

mult n m = n + (mult n (n - 1)) -- caso recursivo: n + (n * (m-1))

 

Olhando estes exemplos de forma mais ampla, podemos ver como recursividade numérica se encaixa num padrão mais geral. O caso base geralmente consiste de um valor específico (geralmente 0 ou 1), no qual a resposta pode ser calculada imediatamente. O caso recursivo computa o resultado ao chamar a função de forma recursiva, mudando os argumentos a cada chamada, e manipulando o resultado de alguma forma para produzir uma resposta final. Os "argumentos diferentes" são geralmente uma unidade menor que o argumento anterior.

Haskell possui muitas funções recursivas, principalmente as que atuam sobre listas.<ref group=nota>Este fato não é coincidência: sem variáveis mutáveis, recursividade é a única forma de implementarmos estruturas de controle para conseguirmos lidar com uma grande quantidade de dados. Isso pode parecer uma limitação da linguagem, mas a impressão só dura até que você se acostume.</ref> Considere a função <code>length</code> que, como já vimos, calcula o comprimento de uma lista. Ela pode ser definida de forma recursiva ([[Haskell/Casamento de padrões, if e let#Padrões com n-uplas e listas|lembre-se de casamento de padrões com listas]]):

 

length :: [a] -> Int

length [] = 0

length (x:xs) = 1 + length xs

 

{{Nota|Se você tentar carregar <code>length</code> desta forma no GHCi, quando usá-la, uma mensagem de erro será exibida alertando sobre "ocorrência ambígua". Isso quer dizer que a mesma função foi carregada duas vezes, o que faz sentido, já que o Prelude já possui uma <code>length</code>. Para usar sua função, tente renomeá-la, como <code>minhaLength</code>, ou <code>length'</code>. Além disso, a <code>length</code> contida no Prelude não é definida da mesma fora que fizemos aqui, mas isso não faz muita diferença para nós.}}

No Prelude, ela é implementada recursivamente com ajuda de <code>(:)</code>, o operador cons:

 

(++) :: [a] -> [a] -> [a]

[] ++ ys = ys

(x:xs) ++ ys = x : xs ++ ys

 

Apesar de parecer um pouco mais complicada que <code>length</code>, ainda é um caso fácil de se entender. A anotação de tipo nos diz que ela recebe duas listas do mesmo tipo e retorna uma terceira lista também do mesmo tipo. O caso base diz que concatenar uma lista vazia e uma lista não-vazia, resulta na própria lista não-vazia. O caso recursivo cria uma expressão desmembrando a primeira lista até que ela esteja toda representada na notação <code>(:)</code>, e adiciona a segunda lista ao fim da primeira, também com <code>(:)</code>.

Mesmo sendo extremamente importantes em Haskell, nem sempre escrevemos funções recursivas. Na verdade, geralmente usamos funções mais básicas contidas nas muitas bibliotecas disponíveis. Estas, por sua vez, são a responsáveis por lidar com a recursividade. Por exemplo, um programador experiente não escreveria <code>fatorial</code> da mesma forma que fizemos aqui. Na verdade, ele usaria função <code>product</code> que calcula o produto dos valores de uma lista:

 

fatorial n = product [1..n]

 

É claro que o funcionamento de <code>product</code> envolve recursividade com listas, mas nós, os programadores ou usuários, sequer tivemos que lidar com a análise de casos base ou recursivos.<ref group=nota>Na verdade, nem mesmo <code>product</code> é definida de forma recursiva, pois ela delega a tarefa da repetição para uma outra função, chamada <code>foldl</code>, que veremos nos capítulos seguintes.</ref>