Recursion, as you may know, is a way of defining functions, in which the function is invoked within its own definition. This is a widely used concept, for example, when mathematical definitions are presented.
One of the most common examples is the definition of the set of natural numbers N (in this case consider that 0 is part of the set):
1) 0 pertence a N
2) Se n pertence a N, então n+1 pertence também a N
The previous definition, like most recursive definitions, is divided into two cases: the base case (or the case of a stop) and the recursive step, where we define rules for formulating more complex cases in terms of simpler cases.
It is important to note that, without the stop case (s), the function normally goes into an infinite loop / loop.
Applying the formula presented earlier to your problem, the number of occurrences of a given character ( c
) in an arbitrary list (where x
represents the head and xs
the tail) is:
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".
You can now try to apply the previous formula and try to define its function. Here's an example, too, if you'd like to compare your solution:
count :: Char -> String -> Int
count _ [] = 0 -- Caso de paragem/base
count c (x:xs)
| c == x = 1 + count c xs
| otherwise = count c xs