0095: Email Tutorials – Recursive Functions in Haskell (Beginner‐Friendly)

FP8 Graham Hutton Video

Table of Contents

1. Why recursion matters in Haskell
2. Two ways to define factorial: using library functions vs recursion
3. How Haskell evaluates expressions (“turning the handle”)
4. What recursion is: base case + recursive case
5. Factorial by recursion (including divergence on negatives)
6. Recursion on lists: the key patterns [] and x:xs
7. Defining product recursively on lists
8. Defining length recursively (and why _ appears)
9. Defining reverse recursively (and why [x] is needed)
10. Recursion with multiple arguments: zip, drop, (++)
11. Bringing it all together: quicksort (recursion + list comprehensions)
12. Exercises you should try now
13. Glossary

1. Why recursion matters in Haskell

In a functional language like Haskell, a huge amount of programming is about defining functions that call themselves to solve smaller versions of the same problem. That idea—recursion—becomes your “looping mechanism,” especially when you work with lists.

The lecture’s big message is: recursion is not only for numbers; it’s also a natural way to process lists (and later, trees and other data). ([youtube.com][1])

2. Two ways to define factorial: library functions vs recursion

2.1 Factorial using other functions (very direct)

Mathematically, factorial means “multiply all numbers from 1 to n.”

In Haskell you can express that directly:

factorial :: Int -> Int
factorial n = product [1..n]

• [1..n] builds the list 1,2,3,...,n
• product multiplies every element in the list

This style is short and clear.

2.2 Factorial using recursion (the main topic today)

You can also define factorial in terms of itself:

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

This has the classic structure:

• a base case (stops recursion)
• a recursive case (reduces the problem size)

3. How Haskell evaluates expressions (“turning the handle”)

A helpful way to understand recursion is to watch evaluation step-by-step: computation proceeds by applying functions to arguments.

Using the “product list” version:

factorial 4
= product [1..4]
= product [1,2,3,4]
= 1 * 2 * 3 * 4
= 24

The key idea: you often need to evaluate inner parts first (like expanding [1..4]) before an outer function (like product) can finish.

4. What recursion is: base case + recursive case

A recursive function is defined in terms of itself.

Almost every beginner-friendly recursive definition follows this shape:

1. Base case: “If the input is the simplest possible form, return an immediate answer.”
2. Recursive case: “Otherwise, reduce the input and call the function again.”

If you forget the base case, or you reduce the input the wrong way, the function can run forever.

5. Factorial by recursion (including divergence on negatives)

5.1 Why factorial 0 = 1?

Because 1 is the identity for multiplication:

• 1 * x = x and x * 1 = x

So when the recursion reaches 0, returning 1 makes the whole multiplication chain work out correctly.

5.2 Turning the handle (example: factorial 3)

factorial 3
= 3 * factorial 2
= 3 * (2 * factorial 1)
= 3 * (2 * (1 * factorial 0))
= 3 * (2 * (1 * 1))
= 6

5.3 What happens for negative numbers?

With this definition, factorial (-1) never reaches the base case:

• factorial (-1) = (-1) * factorial (-2)
• factorial (-2) = (-2) * factorial (-3)
• …and so on forever

This is called diverging (not terminating). Also, in Haskell you usually write factorial (-1) with parentheses so the - isn’t misread as subtraction from something else.

6. Recursion on lists: the key patterns [] and x:xs

For lists, the “standard patterns” are:

• [] (empty list) → base case
• (x:xs) (non-empty list) → recursive case where x is the head and xs is the tail

This mirrors the “0 / n” pattern you saw for natural-number recursion.

7. Defining product recursively on lists

Here is the classic recursive version of product:

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

Why the base case is 1:

• If you used 0, then any multiplication would collapse to 0, giving nonsense answers.

Turning the handle on [2,3,4]:

product' [2,3,4]
= 2 * product' [3,4]
= 2 * (3 * product' [4])
= 2 * (3 * (4 * product' []))
= 2 * (3 * (4 * 1))
= 24

8. Defining length recursively (and why _ appears)

Length does not care what the elements are, only how many.

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

Why _?

• _ is a wildcard: “there is an element here, but I don’t need its value.”

Turning the handle on [1,2,3]:

length' [1,2,3]
= 1 + length' [2,3]
= 1 + (1 + length' [3])
= 1 + (1 + (1 + length' []))
= 1 + (1 + (1 + 0))
= 3

9. Defining reverse recursively (and why [x] is needed)

A simple recursive reverse:

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

Explanation:

• Reverse the tail xs
• Then append the head x to the end
• [x] is a singleton list, needed because (++) joins lists to lists (not a single value to a list).

Turning the handle on [1,2,3]:

reverse' [1,2,3]
= reverse' [2,3] ++ [1]
= (reverse' [3] ++ [2]) ++ [1]
= ((reverse' [] ++ [3]) ++ [2]) ++ [1]
= (([] ++ [3]) ++ [2]) ++ [1]
= [3,2,1]

10. Recursion with multiple arguments: zip, drop, (++)

10.1 zip

Pairs corresponding elements; stops when either list ends:

zip' :: [a] -> [b] -> [(a,b)]
zip' [] _          = []
zip' _  []         = []
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys

10.2 drop

Remove n elements from the front:

drop' :: Int -> [a] -> [a]
drop' 0 xs     = xs
drop' _ []     = []
drop' n (_:xs) = drop' (n-1) xs

Notice two base cases:

• dropping 0 → done
• dropping from empty list → return empty list (safe behavior)

10.3 Append (++)

Concatenate two lists by recursing on the first list:

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

This definition explains why ++ “walks along” the left list, copying its elements, then finally points to ys.

11. Bringing it all together: quicksort (recursion + list comprehensions)

Quicksort in Haskell is a famous “small but complete” program:

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) =
  qsort smaller ++ [x] ++ qsort larger
  where
    smaller = [a | a <- xs, a <= x]
    larger  = [b | b <- xs, b >  x]

What it’s doing:

1. Base case: empty list is already sorted.

2. Recursive case:

   • pick pivot x
   • split the rest into smaller and larger using list comprehensions
   • recursively sort both sides
   • glue together: sorted smaller + pivot + sorted larger

This example is included in the recursion lecture as a “now you can fully understand it” moment. ([youtube.com][1])

12. Exercises you should try now

Try defining these recursively (don’t use the Prelude versions while practicing):

1. and :: [Bool] -> Bool
2. concat :: [[a]] -> [a]
3. replicate :: Int -> a -> [a]
4. (!!) list indexing
5. elem :: Eq a => a -> [a] -> Bool

Then try the “sorted lists” challenge:

• merge :: Ord a => [a] -> [a] -> [a] (merge two sorted lists)
• msort :: Ord a => [a] -> [a] (merge sort)

If you want guided practice, the recursion practice page is a good companion. ([HPM Education][3])

13. Glossary

Recursion: Defining a function in terms of itself.

Base case: The case that stops recursion (e.g., factorial 0 = 1, length [] = 0).

Recursive case: The case that reduces the input and calls the function again.

Diverge / diverging: The function never terminates (often because the base case is never reached).

Evaluate / evaluation: Computing the result of an expression by applying functions to arguments (“turning the handle”).

Pattern matching: Splitting cases by matching shapes like 0 vs n, or [] vs (x:xs).

Empty list []: A list with no elements; usually the base case for list recursion.

Cons (:): Builds a non-empty list: x:xs.

Tail: Everything after the first element (the xs in x:xs).

Wildcard _: “There is something here but I don’t need its value.”

Singleton list [x]: A list containing exactly one element, often used with (++).

Ord a => constraint: Means values of type a can be ordered (needed for sorting).

Buy Book

Quizz & Progress Badge NFT