Haskell/Solutions/Recursion
Jump to navigation
Jump to search
The factorial function
[edit  edit source]Exercises 


factorial
can be defined as follows:factorial 0 = 1 factorial n = n * factorial(n  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)
. This will never stop, so the function will keep going until it runs out of memory. doubleFactorial
can be defined as follows:
doubleFactorial 0 = 1
doubleFactorial 1 = 1
doubleFactorial n = n * doubleFactorial (n2)
Other recursive functions
[edit  edit source]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 (y1)
3.
addition x 0 = x
addition x y = plusOne (addition x (y1))
4.
log2 1 = 0
log2 n = 1 + log2 (n `div` 2)  the "`" make div into infix notation
Listbased recursion
[edit  edit source]Exercises 

Give recursive definitions for the following listbased 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.

The answers for 13, in one block of code:
replicat 0 _ = []
replicat n thing = thing : replicat (n1) thing
[] !! _ = error "Index too large"  An empty list has no elements.
(x:_) !! 0 = x
(x:xs) !! n = xs !! (n1)
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