Learning goals 

  • To understand the structure of a recursive function definition
  • To be able to read and write recursive function definitions on lists
  • To be able to read and write recursion definitions that make use of multiple recursion or mutual recursion
  • To be able to write recursive function definitions in a structured fashion

Advice on Recursion (book, chapt 6.6)

  1. Define the type
  2. Enumerate the cases (write them down)
  3. Define the simple cases
  4. Define the other cases
  5. Generalize and simplify

Recursive Functions

In Haskell, it can be useful to do recursion with pattern matching. E.g.

fac 0 = 1
fac n = n * fac (n-1)

And so it is when you generally define recursions like this one. You have a base case and then the recursive case.

Recursion on Lists

Example

product :: Num a => [a] -> a
product [] = 1
product (n:ns) = n * product ns

Which can be used to define fac, like so: fac n = product [0..n].

Example 2

length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs

Example 3

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Multiple Arguments

zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = q]
-- Recursive case works by using the cons operator to prepend (x,y) to the list generated by the recursive call.
zip (x:xs) (y:ys) = (x,y) : zip xs ys
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
-- Similar to zip: prepends x to list created by recursive call with cons operator.
(x:xs) ++ ys = x : (xs ++ ys)

Quicksort

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort smalls ++ [x] ++ quicksort greats
	where
		smalls = [i | i <- xs, i <= x]
		greats = [j | j <- xs, j > x ]