Recursão, como já deve saber, é uma forma de definir funções, na qual a função é invocada dentro da sua própria definição. Este é um conceito muito usado, por exemplo, quando são apresentadas definições matemáticas.
Um dos exemplos mais comuns é a definição do conjunto dos números naturais N (neste caso consideremos que o 0 faz parte do conjunto):
1) 0 pertence a N
2) Se n pertence a N, então n+1 pertence também a N
A definição anterior, como a maioria das definições recursivas, está dividida em dois casos: o caso base (ou caso de paragem) e o passo recursivo, onde definimos regras para formular casos mais complexos em termos de casos mais simples.
Importante notar que, sem o caso(s) de paragem, a função normalmente entra num ciclo/laço infinito.
Aplicando a fórmula apresentada anteriormente ao seu problema, o número de ocorrências de um dado caractere (c
) numa lista arbitrária (em que x
representa a cabeça e xs
a cauda) é:
1) 0 (zero) se a lista estiver vazia (caso base ou caso de paragem)
2) Caso a lista não estiver vazia o resultado depende da comparação de `c` com o primeiro elemento da lista:
- Se c é igual a x então o resultado é 1 + "número total de ocorrências de c na restante lista"
- Se c é diferente de x, o resultado corresponde apenas ao "número total de ocorrências de c na restante lista".
Pode tentar agora, aplicar a fórmula anterior e tentar definir a sua função. Fica aqui também um exemplo, caso queira comparar a sua solução:
count :: Char -> String -> Int
count _ [] = 0 -- Caso de paragem/base
count c (x:xs)
| c == x = 1 + count c xs
| otherwise = count c xs