Last modified on 7 July 2014, at 11:43

Haskell/Solutions/Recursion

The factorial functionEdit

Exercises
1. Type the factorial function into a Haskell source file and load it into GHCi.
• Try examples like `factorial 5` and `factorial 1000`.
• What about `factorial (-1)`? Why does this happen?
2. The double factorial of a number n is the product of every other number from 1 (or 2) up to n. For example, the double factorial of 8 is 8 × 6 × 4 × 2 = 384, and the double factorial of 7 is 7 × 5 × 3 × 1 = 105. Define a `doublefactorial` function in Haskell.
1. Typing `factorial (-1)` should yield the message `*** Exception: stack overflow`. This is because, according to the definition, `factorial (-1)` is `(-1) * factorial (-2)`, which is `(-1) * (-2) * factorial (-3)`, which is... obviously, this never stops, so it will keep going until it runs out of memory.
2. `doublefactorial` can be defined as follows:
```doublefactorial 0 = 1
doublefactorial 1 = 1
doublefactorial n = n * doublefactorial (n-2)
```

Other recursive functionsEdit

Exercises
1. Expand out the multiplication 5 × 4 similarly to the expansion we used above for `factorial 3`.
2. Define a recursive function `power` such that `power x y` raises `x` to the `y` power.
3. You are given a function `plusOne x = x + 1`. Without using any other `(+)`s, define a recursive function `addition` such that `addition x y` adds `x` and `y` together.
4. (Harder) Implement the function `log2`, which computes the integer log (base 2) of its argument. That is, `log2` computes the exponent of the largest power of 2 which is less than or equal to its argument. For example, `log2 16 = 4`, `log2 11 = 3`, and `log2 1 = 0`. (Small hint: read the last phrase of the paragraph immediately preceding these exercises.)

1. 5 × 4:

• 4 isn't 1, so we recurse: work out 5 × 3
• 3 isn't 1, so we recurse
• 2 isn't 1, so we recurse
• 1 is 1, so we return 5
• We add the current number, 5, to the result of the recursion, 5. We get 10
• We add the current number, 5, to the result of the recursion, 10. We get 15
• We add the current number, 5, to the result of the recursion, 15. We get 20.

2.

```power x 0 = 1
power x y = x * power x (y-1)
```

3.

```addition x 0 = x
addition x y = plusOne (addition x (y-1))
```

4.

```log2 1 = 0
log2 n = 1 + log2 (n `div` 2) -- the "`" make div into infix notation
```

List-based recursionEdit

Exercises

Give recursive definitions for the following list-based functions. In each case, think what the base case would be, then think what the general case would look like, in terms of everything smaller than it.

1. `replicate :: Int -> a -> [a]`, which takes an element and a count and returns the list which is that element repeated that many times. E.g. `replicat 3 'a' = "aaa"`. (Hint: think about what replicate of anything with a count of 0 should be; a count of 0 is your 'base case'.)
2. `(!!) :: [a] -> Int -> a`, which returns the element at the given 'index'. The first element is at index 0, the second at index 1, and so on. Note that with this function, you're recurring both numerically and down a list.
3. (A bit harder.) `zip :: [a] -> [b] -> [(a, b)]`, which takes two lists and 'zips' them together, so that the first pair in the resulting list is the first two elements of the two lists, and so on. E.g. `zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]`. If either of the lists is shorter than the other, you can stop once either list runs out. E.g. `zip [1,2] "abc" = [(1, 'a'), (2, 'b')]`.

4. Define `length` using an auxiliary function and an accumulating parameter, as in the loop-like alternate version of `factorial`.

The answers for 1-3, in one block of code:

```replicat 0 _     = []
replicat n thing = thing : replicat (n-1) thing

[]     !! _ = error "Index too large" -- An empty list has no elements.
(x:_)  !! 0 = x
(x:xs) !! n = xs !! (n-1)

zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
```

`(x:xs)` does not match on an empty list so you can also have:

```zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _      _      = []
```

And here is the accumulating `length`:

```length xs = go 0 xs
where
go acc []     = acc
go acc (_:xs) = go (acc + 1) xs
```

After reading the whole article this example can be helpful for reader factorial program using recursion