## Haskell – 145 – elementi base del linguaggio – 8 Continuo da qui, copio qui.

Ricorsività
In imperative languages like C and Java, the most basic control structure is a loop (like a `for` loop). However, `for` loops don’t make much sense in Haskell because they require destructive update (the index variable is constantly being updated). Instead, Haskell uses recursion.

A function is recursive if it calls itself (see the appendix on Recursion [prossimamente] for more). Recursive functions exist also in C and Java but are used less than they are in functional languages. The prototypical recursive function is the factorial function. In an imperative language, you might write this as something like:

``````int factorial(int n) {
int fact = 1;
for (int i=2; i <= n; i++)
fact = fact * i;
return fact;
}``````

While this code fragment will successfully compute factorials for positive integers, it somehow ignores the basic definition of factorial, usually given as: This definition itself is exactly a recursive definition: namely the value of `n!` depends on the value of `(n-1)!`. If you think of `!` as a function, then it is calling itself. We can translate this definition almost verbatim into Haskell code:

``````factorial 1 = 1
factorial n = n * factorial (n-1)``````

This is likely the simplest recursive function you’ll ever see, but it is correct.

Note: Of course, an imperative recursive version could be written:

``````int factorial(int n) {
if (n == 1)
return 1;
else
return n * factorial(n-1);
}``````

but this is likely to be much slower than the loop version in C.

Recursion can be a difficult thing to master. It is completely analogous to the concept of induction in mathematics (see the chapter Recursion [prossimamente] for a more formal treatment of this). However, usually a problem can be thought of as having one or more base cases and one or more recursive-cases. In the case of factorial, there is one base case (when `n=1`) and one recursive case (when `n>1`). For designing your own recusive algorithms, it is often useful to try to differentiate these two cases.

Turning now to the task of exponentiation, suppose that we have two positive integers `a` and `b`, and that we want to calculate `a^b`. This problem has a single base case: namely when `b` is 1. The recursive case is when `b>1`. We can write a general form as: Again, this translates directly into Haskell code:

``````exponent a 1 = a
exponent a b = a * exponent a (b-1)``````

Just as we can define recursive functions on integers, so can we define recursive functions on lists. In this case, usually the base case is the empty list `[]`, and the recursive case is a cons list (i.e., a value consed on to another list).

Consider the task of calculating the length of a list. We can again break this down into two cases: either we have an empty list or we have a non-empty list. Clearly the length of an empty list is zero. Furthermore, if we have a cons list, then the length of this list is just the length of its `tail` plus one. Thus, we can define a `length` function as:

``````my_length [] = 0
my_length (x:xs) = 1 + my_length xs``````

Note: Whenever we provide alternative definitions for standard Haskell functions, we prefix them with `my_` so the compiler doesn’t become confused.

Similarly, we can consider the `filter` function. Again, the base case is the empty list, and the recursive case is a cons list. However, this time, we’re choosing whether to keep an element, depending on whether or not a particular predicate holds. We can define the `filter` function as:

``````my_filter p [] = []
my_filter p (x:xs) =
if p x
then x : my_filter p xs
else my_filter p xs``````

In this code, when presented with an empty list, we simply return an empty list. This is because `filter` cannot add elements; it can only remove them.

When presented with a list of the form `x:xs`, we need to decide whether or not to keep the value `x`. To do this, we use an `if` statement and the predicate `p`. If `p x` is `true`, then we return a list that begins with `x` followed by the result of filtering the tail of the list. If `p x` is false, then we exclude `x` and return the result of filtering the tail of the list.

We can also define `map` and both fold functions using explicit recursion. See the exercises for the definition of `map` and the chapter Language advanced [prossimamente] for the folds.

Esercizi
The fibonacci sequence is defined by: Write a recursive function `fib` that takes a positive integer `n` as a parameter and calculates `Fn`.

Attenzione 😯: questo è un caso che già una volta mi ha fatto hangare il ‘puter. È un problema di GHCi che non accetta le funzioni su più righe, occorre creare un file e caricarlo.

fib.hs

``````fib 1 = 1
fib 2 = 2
fib n = fib (n - 2) + fib (n -1)``````
``````Prelude> :l fib
[1 of 1] Compiling Main             ( fib.hs, interpreted )
*Main> fib 5
8
*Main> fib 10
89``````

Define a recursive function `mult` that takes two positive integers `a` and `b` and returns `a*b`, but only uses addition (i.e., no fair just using multiplication). Begin by making a mathematical definition in the style of the previous exercise and the rest of this section.

mult.hs

``````mult a 1 = a
mult a b = a + mult a (b -1)``````
``````Prelude> :l mult
[1 of 1] Compiling Main             ( mult.hs, interpreted )
*Main> mult 6 7
42``````

Define a recursive function `my_map` that behaves identically to the standard function `map`.

my_map

``````doppio x = 2 * x

my_map f [] = []
my_map f (x : xs) = f x : my_map f xs``````
``````Prelude> :l my_map
[1 of 1] Compiling Main             ( my_map.hs, interpreted )