Haskell/Recursividade

Recursividade é uma forma de repetição que pode ser aplicada em muitos casos, não só da Matemática ou da Computação. Em Haskell, funções recursivas são fundamentais como veremos a diante.

Na Computação, diz-se que uma função é recursiva quando ela chama a si mesma. Ela geralmente possui pelo menos um caso base, que interrompe a recursividade, e um caso recursivo, que define a condição para que haja repetição. Ter um caso base bem definido é importante para impedir a repetição infinita da função.

Recursividade numérica

A melhor maneira de explicar recursividade é com exemplos claros.

A função fatorial

Na Matemática, mais especificamente em Análise Combinatória, usa-se bastante uma função chamada fatorial. É uma função que só pode ser aplicada a números não-negativos e inteiros: ela calcula o produto de todos os números inteiros menores que, ou igual ao argumento, e maiores que zero. O fatorial (representado por $n!$) de 6 seria:

$6!=6\times 5\times 4\times 3\times 2\times 1=720.$

Se definirmos que o fatorial de 0 é igual a 1, isto é, que $0!=1$, podemos definir $n!$ de forma recursiva. Vejamos:

$\begin{array}{cc}6!& =6\times (5!)\\ 6!& =6\times 5\times (4!)\\ 6!& =6\times 5\times 4\times (3!)\\ 6!& =6\times 5\times 4\times 3\times (2!)\\ 6!& =6\times 5\times 4\times 3\times 2\times (1!)\\ 6!& =6\times 5\times 4\times 3\times 2\times 1\times (0!)\\ 6!& =6\times 5\times 4\times 3\times 2\times 1\times 1\\ 6!& =720.\end{array}$

De forma generalizada: $n!=\{\begin{array}{cc}1,& \text{se }n=0\\ n\times (n-1)!& \text{se }n>0\end{array}$

Fica clara a recursvidade da função fatorial, pois ela é definida em termos de si mesma. E também são bastante evidentes os casos base e recursivo, e suas condições:

• Caso base: o fatorial de 0 é 1.
• Caso recursivo: o fatorial de qualquer outro número maior que zero, é igual a este número multiplicado pelo fatorial de seu predecessor.

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 fatorial novamente. Perceba o uso de parênteces na segunda linha: sem eles, Haskell interpretaria a segunda linha como sendo n * (fatorial n) - 1.

Para testar, é recomendável escrever fatorial num arquivo e carregá-lo no GHCi. Entretanto, por ser uma função simples, podemos escrever tudo numa linha só:

É importante saber que não há nada de mágico acontecendo. Nós já vimos alguns exemplos de funções que chamam outras para obtermos um resultado final. Numa função recursiva, a diferença é que em vez de chamar uma sub-função diferente, ela chama a si mesma, e o que muda são os argumentos de entrada.

Vejamos o que acontece quando chamamos fatorial 3:

• 3 não é 0 (o caso base), portanto, precisamos chamar fatorial 2
  • 2 não é 0, portanto, precisamos chamar fatorial 1
    • 1 não é 0, portanto, precisamos chamar fatorial 0
      • 0 é 0, portanto, chegamos ao caso base, e temos um valor numérico como resultado: 1.
    • Agora retornamos ao cálculo de fatorial 1 e podemos reescrever a expressão 1 * fatorial 0 como sendo 1 * 1, pois já calculamos fatorial 0.
  • Retornamos ao cálculo de fatorial 2. Com o resultado de fatorial 1 podemos reescrever a expressão atual: 2 * (1 * 1)
• Chegamos ao cálculo de fatorial 3. Usando o resultado de fatorial 2, a expressão atual pode ser reescrita como (3 * (2 * (1 * 1))), cujo resultado final é 6.

Perceba que temos a repetição do valor 1. Isso acontece porque definimos o caso base em 0. Poderíamos ter definido o caso base como fatorial 1 = 1, mas, geralmente, é melhor seguir a definição matemática, em vez de simplificá-la.

Laços de repetição, recursividade e parâmetros acumuladores

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 C, poderíamos usar o laço for para escrever uma fatorial da seguinte forma:

int fatorial(int n) {
    int res = 1;
    for ( ; n > 1 ; n--)
        res = n * res;
    return res;
}

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

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 n e res 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

aux é uma função auxiliar. É ela que, de fato, realiza o cálculo, enquanto que fatorial apenas a envolve. Na função aux, temos dois argumentos: n, que vem de fora, e é definido pelo usuário quando chama fatorial n; e res, 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 aux na cláusula otherwise.

Outras funções recursivas

Apesar de ser muito útil, não há nada de muito especial com a implementação de fatorial, 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 mult 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.

Recrusividade usando listas

Haskell possui muitas funções recursivas, principalmente as que atuam sobre listas. Considere a função length que, como já vimos, calcula o comprimento de uma lista. Ela pode ser definida de forma recursiva (lembre-se de casamento de padrões com listas):

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

A assinatura de tipo de length nos diz que ela recebe qualquer tipo de lista e retorna um Int. Na linha seguinte, temos o caso base, que estipula que uma lista vazia tem comprimento igual a 0. A terceira e última linha é o caso recursivo: somar 1 ao comprimento da cauda da lista. Neste caso, length será usada para calcular o comprimento de sucessivas caudas da mesma lista, cada vez mais curtas, até ser apenas uma lista vazia. Quando chegar a este ponto, uma soma de 1s e 0 será a expressão final que resultará no comprimento da lista de entrada.

Agora, vejamos a função concatenar, (++). Já sabemos como ela funciona:

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

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys

Apesar de parecer um pouco mais complicada que length, 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 (:), e adiciona a segunda lista ao fim da primeira, também com (:).

Podemos perceber um padrão nestas duas funções: em funções recursivas que envolvem listas, o caso base geralmente lida com uma lista vazia, e o caso recursivo manipula o dado da cabeça da lista, enquanto passa apenas cauda como argumento para a próxima etapa.

Conhecendo outras funções elementares

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 fatorial da mesma forma que fizemos aqui. Na verdade, ele usaria função product que calcula o produto dos valores de uma lista:

fatorial n = product [1..n]

É claro que o funcionamento de product 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.