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


 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. doublefactorial
can be defined as follows:
doublefactorial 0 = 1
doublefactorial 1 = 1
doublefactorial n = n * doublefactorial (n2)
Other recursive functions[edit]
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]
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
After reading the whole article this example can be helpful for readers factorial program using recursion