Haskell/Recursividade

Este módulo encontra-se em processo de tradução. A sua ajuda é bem vinda.

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{aligned}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{aligned}}$

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

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ó:

Prelude> let fatorial 0 = 1 ; fatorial n = n * fatorial (n - 1)
Prelude> fatorial 6
720

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

Exercício

1. O que acontece se calcularmos fatorial (-1)?
2. Como já vimos antes, a ordem dos padrões é importante quando definimos uma função. Se fizéssemos

   fatorial n = n * fatorial (n - 1)
   fatorial 0 = 1
   

   e tentássemos calcular fatorial 6, o que aconteceria?
3. 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 fatorialDuplo em Haskell que faça esta conta.

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.

Exercício

1. Defina uma função recursiva chamada potencia tal que o resultado de potencia x y seja x elevado à potência y.
2. Lhe é dada a função maisUm x = x + 1. Sem usar (+) novamente, e usando apenas maisUm e (-), defina a função recursiva adicao tal que adicao x y resulte na soma de x e y. Considere apenas números inteiros não-negativos.
3. Escreva a função log2 que calcula o logaritmo de seu argumento na base 2. Por exemplo: log2 1024 = 10, log2 1 = 0, log2 11 = 3. Dica: use números inteiros, e use div x y (uma função nativa de Haskell) para calcular o quociente da divisão de x por y.

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

Nota: Se você tentar carregar length 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 length. Para usar sua função, tente renomeá-la, como minhaLength, ou length'. Além disso, a length contida no Prelude não é definida da mesma fora que fizemos aqui, mas isso não faz muita diferença para nós.

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:

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]

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.

Exercício

Escrevas as seguintes funções de forma recursiva. Note que todas elas já possuem uma versão nativa no Prelude. Você pode usar dois casos base, caso ache necessário, apesar de que todos podem ser resolvidos com apenas um.

1. replicar :: Int -> a -> [a], que recebe um contador n e um elemento, e retorna uma lista contendo n elementos iguais aos da entrada. Ex.: replicar 3 2 = [2,2,2]. A versão do Prelude chama-se replicate.
2. (!!!) :: [a] -> Int -> a, que recebe uma lista e um índice de posição, e retorna o elemento contido em tal posição dentro da lista. O primeiro elemento da lista está na posição 0. Ex.: "abcde" !!! 2 = 'c'. A versão do Prelude chama-se (!!).
3. ziper :: [a] -> [b] -> [(a,b)], que age como um ziper entre duas listas, isto é, pega um elemento de cada lista, forma uma dupla, e retorna uma lista de duplas. Ex.: ziper [1,2,3,4] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]. Perceba que a ação é interrompida quando o limite da lista mais curta é atingido. A versão do Prelude chama-se zip.
4. Redefina length usando uma função interna auxiliar e um parâmetro acumulador.

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.