Haskell Recursion Guide — Recursive Functions, Tail Recursion, and Patterns

In this tutorial, you will learn about Haskell Recursion Guide. We cover key concepts, practical examples, and best practices to help you master this topic.

Haskell recursion replaces loops with functions that call themselves, using pattern matching on base cases and recursive cases -- with tail recursion and accumulators enabling efficient computation that compiles to tight loops.

Basic Recursion

-- Factorial
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

-- List sum
sumList :: [Integer] -> Integer
sumList []     = 0
sumList (x:xs) = x + sumList xs

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

Tail Recursion

-- Tail recursive factorial (accumulator)
factorial' :: Integer -> Integer -> Integer
factorial' 0 acc = acc
factorial' n acc = factorial' (n - 1) (n * acc)

factorial n = factorial' n 1

-- Tail recursive reverse
reverse' :: [a] -> [a]
reverse' list = go list []
  where
    go []     acc = acc
    go (x:xs) acc = go xs (x:acc)

Multiple Recursion

-- Fibonacci (naive, exponential)
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

-- Fibonacci (efficient, linear)
fib' n = go n 0 1
  where
    go 0 a _ = a
    go n a b = go (n - 1) b (a + b)

Recursion on Trees

data Tree a = Empty | Node a (Tree a) (Tree a)

treeDepth :: Tree a -> Integer
treeDepth Empty        = 0
treeDepth (Node _ l r) = 1 + max (treeDepth l) (treeDepth r)

treeSum :: Num a => Tree a -> a
treeSum Empty         = 0
treeSum (Node v l r)  = v + treeSum l + treeSum r

Common Mistakes

1. Missing base case

Every recursive function needs at least one base case. Without it, the recursion never terminates.

2. Non-tail recursion on large input

sumList [1..1000000] overflows the stack. Use tail recursion with an accumulator or folds.

3. Naive Fibonacci

The naive fib 40 has exponential complexity. Use tail recursion or memoization for large values.

Practice Questions

1. What is the base case in recursion? The smallest input that returns a direct answer without recursing. Often empty list, 0, or null constructor.

2. What is tail recursion? The recursive call is the last operation in the function. GHC can optimize this to a loop (no stack growth).

3. Why is naive Fibonacci slow? Each call creates two recursive calls, leading to O(2^n) complexity. Tail-recursive version is O(n).

FAQ

{{< faq question="Does GHC optimize all tail calls?" >}} GHC performs tail-call optimization (TCO) for self-recursive tail calls. Mutual tail recursion may not always be optimized. {{< /faq >}}

{{< faq question="What is an accumulator?" >}} An extra parameter that accumulates intermediate results, passed through recursive calls to build the final answer. {{< /faq >}}

{{< faq question="Can I have mutual recursion?" >}} Yes. Functions calling each other: even 0 = True; even n = odd (n-1); odd 0 = False; odd n = even (n-1). {{< /faq >}}

What's Next

Now learn about higher-order functions.