Before you begin
Why this matters
Recursion underlies every repetition in Haskell: map, folds, and mapM_ are themselves recursive functions. It is also how every language handles data that contains smaller copies of itself, such as trees. If you can follow one step at a time, you can predict a recursive function’s result and find out why one never finishes.
What this helps you reason about
- Spot a function that can never stop calling itself, before you run the code.
- Predict the order of IO actions before and after a function uses itself.
- Recognize when a recursive sum builds up waiting work, and how to avoid it.
Haskell has no loop statements. To repeat work, a function is defined in terms of itself on a smaller input. This lesson follows those definitions one step at a time: how they stop, how they move toward stopping, and how results combine.
Already know this? The short version
- Haskell has no loop statements; repetition is recursion, written directly or through map, folds, and mapM_, which are themselves recursive.
- Equations are tried top to bottom, so the base case equation comes first; a guard such as n <= 0 covers values a literal pattern misses, and -Wincomplete-patterns cannot detect a base case that is never reached.
- In a do block, actions after the recursive use run only after the whole nested sequence has finished, so they run innermost first.
- total (x:rest) = x + total rest leaves every addition waiting until the empty list is reached; foldl' keeps one running total instead, and so does sum from GHC 9.2 on.
- GHC’s stack limit (-K) defaults to 80% of physical memory, so deep recursion usually costs memory rather than crashing.
Words in this lesson (7)
- recursive function
- A function whose definition uses itself on a smaller argument.
- equation
- One line of a function definition, such as countdown 0 = putStrLn "liftoff". GHC tries a function’s equations from top to bottom and uses the first one that matches.
- base case
- The case, an input or a condition such as the pattern 0 or the guard n <= 0, that the function answers without using itself. Reaching it stops the recursion.
- recursive case
- An input the function answers by using itself on a smaller input.
- guard
- A Boolean test after |, such as | n <= 0. It is checked after the pattern matches and chooses which right-hand side to use.
- do block
- A way to write a sequence of actions, one per line. IO actions in a do block run in the order they are written. do works for other kinds of actions too, such as Maybe computations.
- strict left fold
- foldl' from Data.List. It walks a list from the left and computes the running result at each step, so no additions wait.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / A call to itself
What happens when a function uses itself?
A recursive function is a function whose definition uses itself. countdown 3 is an action that prints 3 and then runs countdown 2. That action prints 2 and runs countdown 1, and so on.
Each use of countdown has its own n. countdown 3 and countdown 2 are separate applications of the same function to different arguments.
countdown :: Int -> IO ()
countdown 0 = putStrLn "liftoff"
countdown n = do
print n
countdown (n - 1)Each application of countdown has its own n.
Coming from Python: A Python for loop has no matching Haskell statement; you write a recursive function, or use map, foldr, or mapM_.
Precisely: no call stack picture
GHC does not evaluate Haskell by pushing one frame per function call the way C does. The stepper shows where evaluation is happening and the bindings visible there. It does not show a stack of waiting calls.
Experiment
Follow a countdown to its base case
countdown n is an IO action that prints n and then runs countdown (n - 1). Equations are tried in order, so countdown 0 matches the first equation and stops the repetition. Without it, every n matches the second equation.
Why it matters Haskell has no loop statements. Repetition is written as recursion like this, or with functions such as map and mapM_ that are themselves defined by recursion. The first equation is the base case, and the second must move toward it.
Predict the output before running. Then delete the first equation, countdown 0 = ..., and run again.
countdown :: Int -> IO ()
countdown 0 = putStrLn "liftoff"
countdown n = do
print n
countdown (n - 1)
main :: IO ()
main = countdown 3
What to look for
Watch which equation each stop is in and the value of n at that stop. GHCi shows one location per stop, not a stack of frames. The last stop is in the first equation; liftoff prints after it. Without the first equation, n goes below 0 and the stops continue. The runner then ends the run with a message that begins "Stopped after".
Expected output
3
2
1
liftoff02 / Base case
What makes the recursion stop?
The base case is the case, an input or a condition, that the function answers directly, without using itself. Every other input is the recursive case: the function uses itself on a smaller input. Equations, and the guards below, are tried from top to bottom, so write the base case first. Without a base case, every argument matches the recursive equation, and the repetition never finishes on its own.
The recursion must also reach the base case. countdown (n - 1) makes n smaller by one each time, so any positive number reaches 0. But countdown (-1) runs countdown (-2), then countdown (-3), and moves away from 0, so in practice it never stops. A guard can cover every value that should stop. It is a Boolean test after |, such as | n <= 0, and otherwise is a guard that is always true.
countdown :: Int -> IO ()
countdown n
| n <= 0 = putStrLn "liftoff" -- base case
| otherwise = do -- recursive case
print n
countdown (n - 1)Check two things: a base case exists, and every use gets closer to it.
Precisely: patterns, guards, and Int
The pattern 0 matches the value zero and nothing else, while the guard n <= 0 covers every non-positive value. GHC can warn about incomplete patterns with -Wincomplete-patterns, but it cannot detect a base case that is never reached. Without the guard, countdown (-1) would reach 0 again after Int wraps around past its smallest value. In GHC on a 64-bit computer an Int has 64 bits (the Haskell Report promises at least 30), so that would take about 2^64 steps.
03 / The way back
What runs after the recursive action has finished?
In a do block, actions run in order. The action after visit (level - 1) cannot start until that whole nested sequence has finished.
So actions written before the recursive use happen on the way down, while the nested sequences are still being started: visit 3 first, then visit 2, then visit 1. Actions written after it happen on the way back, while those sequences are finishing: visit 1 first, then visit 2, then visit 3.
visit :: Int -> IO ()
visit 0 = return ()
visit level = do
putStrLn ("enter " ++ show level)
visit (level - 1)
putStrLn ("leave " ++ show level)Actions before the recursive use run on the way down; actions after it run on the way back.
Precisely: what “the way back” means here
A do block is a shorter way to write >>, which joins two IO actions into one that runs the first, then the second. The body of visit level is putStrLn (enter ...) >> (visit (level - 1) >> putStrLn (leave ...)). The leave action comes after the whole of visit (level - 1) in that nesting, so it runs once that sequence is complete. Nothing returns to a waiting call; the order comes from how the actions are joined.
Experiment
Watch work happen on the way back
In a do block, actions run in order. The action after visit (level - 1) cannot run until that whole nested sequence has finished, so the leave lines come out newest first.
Why it matters Where you put work relative to the recursive call decides its order. This is how a recursive function can reverse a sequence without a separate reverse step.
Predict the order of all six lines before running. Then move the leave line above the recursive call and predict again.
visit :: Int -> IO ()
visit 0 = return ()
visit level = do
putStrLn ("enter " ++ show level)
visit (level - 1)
putStrLn ("leave " ++ show level)
main :: IO ()
main = visit 3
What to look for
Watch the output and the value of level at each stop. Sometimes the output ends in enter or leave with no number yet: putStrLn writes the text it has, then show level is computed. After the stop in visit 0, the leave actions that were waiting run: level 1 first, then 2, then 3. After the edit, each leave line comes right after its enter line: enter 3, leave 3, enter 2, leave 2, enter 1, leave 1, and the last stop is in visit 0.
Expected output
enter 3
enter 2
enter 1
leave 1
leave 2
leave 304 / Combining results
How do the answers come together?
A recursive function usually returns a value built from a smaller answer. The pattern (x:rest) splits a list into its first element and the rest. total [4, 2, 7] is 4 + total [2, 7], which is 4 + (2 + total [7]), which is 4 + (2 + (7 + total [])).
total [] is the base case: 0. Only then can the additions finish, from the end of the list back to the start: 7, then 9, then 13.
total :: [Int] -> Int
total [] = 0
total (x:rest) = x + total restAssume the smaller application gives the right answer, then use it.
Experiment
Combine results from smaller calls
total (x:rest) = x + total rest splits the list into its first element and the rest. total [] = 0 answers the empty list directly. The additions finish from the end of the list back to the start.
Why it matters You do not need to follow every call to check a recursive function. Check that the base case is right. Then check that each call combines a correct smaller answer correctly.
Predict what each call returns before running. Then change the 2 in the list to 5 and predict the new total.
total :: [Int] -> Int
total [] = 0
total (x:rest) = x + total rest
main :: IO ()
main = print (total [4, 2, 7])
What to look for
Watch x and rest at each stop. GHCi stops once for each list cell, each time with a shorter rest, and then in total [] = 0. It does not stop for the additions: x + total rest needs total rest first, so every addition waits until the empty list is reached, and 13 appears when the run ends. After the edit, the run prints 16.
Expected output
1305 / Depth
How deep can it go, and what makes waiting work pile up?
GHC keeps pending work on a stack, but that stack starts small and grows in chunks as needed, up to a limit set by the -K runtime option. The default limit is 80% of physical memory, so there is no small depth limit to hit. But deep recursion still costs memory. To finish x + total rest, every x must wait on that stack until total rest is known. For a list of a million numbers, a million additions wait at once.
A strict left fold adds as it goes, keeping only the running total. For long lists, prefer it. The built-in sum works the same way from GHC 9.2 on; in older versions, including the stepper’s GHC 9.0, it may build up waiting additions like total does.
import Data.List (foldl')
total :: [Int] -> Int
total = foldl' (+) 0Repetition in Haskell is built on recursion; choose a form that does not build up waiting work.
Coming from JavaScript: In JavaScript a deep recursion soon throws RangeError; in GHC it usually keeps going and uses more memory, because the default stack limit is 80% of physical memory.
Precisely: waiting additions and a lazy running total
These are two different problems. The additions waiting in total are on GHC’s stack, one per element. A lazy left fold, foldl (+) 0, has the other problem: its running total becomes a chain of thunks (stored additions not yet done) on the heap, such as (0 + 4) + 2, and nothing is added until the result is needed. foldl' evaluates the running total at each step, so neither the stack nor the heap grows with the list. The 80% default for -K applies to recent GHC versions; deep recursion more often uses a lot of memory than crashes.
06 / Try it
Can you follow a fresh example?
Predict the output before revealing the answer. Ask where the print sits relative to the recursive use.
showAll :: Int -> IO ()
showAll 0 = return ()
showAll n = do
showAll (n - 1)
print n
main :: IO ()
main = showAll 3
What does this print, and why in that order?
Reveal the reasoning
1, then 2, then 3. showAll 3 first runs showAll 2, which first runs showAll 1, which first runs showAll 0. showAll 0 does nothing. Then the print in showAll 1 runs, then the one in showAll 2, then the one in showAll 3. The print comes after the recursive use, so it runs on the way back.
Practice tickets
- REC-101 · Fix the parcel check number → Free
- REC-102 · Count every nested folder → Sign in · Pro
- REC-103 · Show the reporting chain → Sign in · Pro