Recursion explained
A function that calls itself, the base case that stops it, the call stack that holds the calls that are waiting, and the backtracking that solves a maze. Three demos run on a live robot, including one with no base case, and you can change them and press Run.
Recursion is a function that calls itself. It sounds like a trick, or a mistake, and the first time you meet it your instinct is that it cannot possibly work. It does work, because each call is a fresh copy of the function with its own variables, and because every call is given a smaller problem than the one it was handed. Somewhere at the bottom the problem gets small enough to answer outright, and all the waiting copies finish one after another. On this page a small robot works out a route, runs out of memory on purpose, and then solves a maze by backtracking, and each demo below is a real program you can change and run.
Two parts make a recursive function, and it is broken without either:
- The base case: the smallest problem, answered with no further call.
- The recursive case: a smaller version of the same problem, handed to the function itself, and something done with the answer that comes back.
A function that calls itself
Here is a route made of four legs. Adding them up is a loop in most people's hands, but it is also a recursive idea: the length of a route is its first leg, plus the length of the rest of the route. The rest of the route is a shorter route, and the shortest route of all, the one with no legs, is 0 cm long.
The program
from bugbot import *
connect()
PLAN = [12, 8, 20, 5] # a route: four legs, in cm
def total(legs, depth=1):
print(" " * depth + "total(%s)" % legs)
plot("how deep the stack is", depth)
wait(0.1)
if not legs: # the base case
print(" " * depth + "no legs left, so 0")
return 0
rest = total(legs[1:], depth + 1) # the recursive case
print(" " * depth + "%d + %d = %d" % (legs[0], rest, legs[0] + rest))
plot("how deep the stack is", depth)
wait(0.1)
return legs[0] + rest
length = total(PLAN)
print("the route is", length, "cm long")
forward(60, distance=length)
Read the printed output from the top and you can see the shape of it. Each call prints itself, indented one step further, until total([]) prints no legs left, so 0. Nothing has been added up yet at that point. Then the answers come back the other way: 0, then 5, then 25, then 33, then 45. The chart is the same thing drawn: it climbs one step per call to a depth of 5, and comes back down one step at a time.
The line that matters most is this one:
rest = total(legs[1:], depth + 1)
legs[1:] is the list without its first item, so every call gets a shorter list than the one before. That is what makes the base case certain to be reached. If a recursive call is not given a smaller problem, the function is not recursive, it is just stuck.
The call stack
The reason a function can call itself without the copies getting muddled is the call stack. Every time any function is called, the computer pushes a stack frame onto the stack: a small block of memory holding that call's own arguments and local variables, and the line to go back to when it finishes. When the call returns, its frame is popped off and the one underneath carries on exactly where it left off.
So during the demo above there were five total frames on the stack at once, each with its own legs and its own depth, and each waiting for the one above it. depth in that program is just a number being carried along to make the printing tidy. The real stack underneath it is what the chart is drawing.
This is the price of recursion. Frames take memory, and the stack is not endless.
What happens with no base case
Take the base case out and every call makes another call. Nothing stops. Python notices before the memory runs out, and raises a RecursionError.
The program
from bugbot import *
connect()
deepest = 0
def dig(depth):
global deepest
deepest = depth
if depth % 100 == 0: # plot every hundredth call
plot("how deep the stack is", depth)
wait(0.05)
return dig(depth + 1) # no base case: this never stops
try:
dig(1)
except RecursionError:
print("RecursionError after", deepest, "calls")
plot("how deep the stack is", 0)
print("the stack is empty again")
The chart climbs in a straight line and stops dead. Python keeps a limit on how many frames deep a program may go, about a thousand by default, and raises RecursionError when it is passed. The limit is there to catch exactly this mistake: without it the program would carry on until the memory ran out, which on a small robot means a crash with nothing useful printed. Deeper in, the same thing in a language without that check is called a stack overflow.
Two things to notice. The error is the same whether the mistake is a missing base case or a recursive call that is not smaller. And a thousand frames sounds like a lot until you try to recurse once per centimetre of a route, or once per pixel of a picture.
Recursion or a loop?
Anything you can write with recursion you can write with a loop, and the other way round, because a loop plus your own list used as a stack is exactly what recursion does for you. Which to use is a matter of which one says the thing more plainly.
- A loop is usually clearer, and always cheaper, for a straight run through a list or a count.
- Recursion is usually clearer when the problem is made of smaller copies of itself: a tree of folders, a sorted half of a list, an expression inside brackets, or a maze where each junction is a smaller maze.
Backtracking is the case where recursion earns its keep, and that is the rest of this page.
Backtracking: a maze
Here is the recipe for solving a maze by recursion. Stand in a cell. If it is off the grid, or a wall, or somewhere you have already been, this way is no good, so say no. Otherwise put the cell on the path and ask the same question of each neighbour in turn. If any of them says yes, you are done. If all of them say no, this cell is a dead end: take it off the path and say no yourself.
That last step is the backtracking, and it is where the call stack does the work for you. Coming back from a call that said no means the program is back in the cell it came from, with that cell's own variables, its own list of directions left to try, and its own place in the loop. Nobody had to write down the way back. The stack is the way back.
The maze in this demo is drawn on the mat by the program itself: grey squares for the walls, a green line for the path so far, and a red square on each cell found to be a dead end. It is 5 cells across and 4 up, each cell 20 cm, with the robot starting in the middle of the bottom row and the goal in the top left corner.
The program
from bugbot import *
connect()
MAZE = ["..#..", # the top row, y = 80 cm
".#..#",
"...#.",
"#...."] # the bottom row, y = 20 cm
ROWS, COLS = 4, 5
START = (3, 2) # where the robot is standing
GOAL = (0, 0) # the top left corner
WAYS = [(-1, 0), (0, 1), (1, 0), (0, -1)] # up, right, down, left
def middle(cell):
# the middle of a cell, in cm on the mat
row, col = cell
return (10 + 20 * col, 80 - 20 * row)
path = [] # the cells from the start to where it is now
seen = set() # every cell already tried
dead = [] # the cells that led nowhere
def show():
draw("path", [middle(c) for c in path], "green", "line", 3)
draw("dead ends", [middle(c) for c in dead], "red", "squares", 8)
plot("how deep the stack is", len(path))
def explore(row, col):
if row < 0 or row >= ROWS or col < 0 or col >= COLS:
return False # off the grid
if MAZE[row][col] == "#":
return False # a wall
if (row, col) in seen:
return False # been here already
seen.add((row, col))
path.append((row, col))
show()
wait(0.1)
if (row, col) == GOAL:
return True # the base case that wins
for down, across in WAYS:
if explore(row + down, col + across):
return True # a neighbour found the goal
path.pop() # backtrack
dead.append((row, col))
print("dead end at", (row, col), "at depth", len(path) + 1)
show()
wait(0.1)
return False
draw("walls", [middle((r, c)) for r in range(ROWS) for c in range(COLS)
if MAZE[r][c] == "#"], "#555555", "squares", 20)
if explore(*START):
print("path:", path)
print("cells looked at:", len(seen), "and", len(dead), "were dead ends")
# drive it: this robot can go sideways, so it never turns
here = middle(START)
trail = [here]
for cell in path[1:]:
x, y = middle(cell)
px, py = position()
dx, dy = x - here[0] - px, y - here[1] - py
if dx > 1:
right(80, distance=dx)
elif dx < -1:
left(80, distance=-dx)
if dy > 1:
forward(80, distance=dy)
elif dy < -1:
backward(80, distance=-dy)
trail.append((x, y))
draw("robot", trail, "blue", "line", 2)
plot("how deep the stack is", 0)
print("time:", round(clock()), "s")
Watch the green line grow up the middle of the mat and then off to the right, where it runs out of maze. Four cells in a row turn red as the search backs out of that branch, the deepest of them six cells down the stack. Then it tries left instead, loses one more cell to a dead end below, and walks out to the goal. The chart rises and falls with the green line, because the depth of the stack is the length of the path so far.
The order in WAYS is the only thing deciding which way it goes first, and it changes everything. Put left before right, [(-1, 0), (0, -1), (1, 0), (0, 1)], and the search goes the other way round the maze. Try it: the path it finds is different, and so are the dead ends.
What recursive backtracking does not give you is the shortest route. It gives you the first route it happens to find. The maze solving guide compares it with flood fill, which does find the shortest, and the breadth-first search guide explains why a queue finds short routes where a stack finds deep ones.
The same picture as a chart of the stack, cell by cell, shows the backtracking on its own:
Recursive backtracking is the same shape whatever the puzzle: choose, recurse, and undo the choice if the recursion fails. Sudoku solvers, the eight queens problem, timetabling and the solver behind a crossword app are all this, with a different test for "no good".
Where this is taught
- Stack frames and the call stack builds the stack by hand, pushing and popping frames as the robot's own subroutines run.
- Recursion is the full lesson: base case, recursive case, and what the stack holds while it runs.
- Recursion versus iteration writes the same job both ways and compares them.
- Project: out of the dead end sets a maze of its own, to solve recursively and then drive.
- Linear and binary search and Merge sort are the two classic algorithms that are naturally recursive.
- Depth-first traversal does the same walk on a graph rather than a grid.
Questions
What is recursion in programming?
A function that calls itself, on a smaller version of the same problem, until the problem is small enough to answer outright. Every recursive function needs a base case, which returns without calling again, and a recursive case, which calls itself on something smaller. The calls that are still waiting are held on the call stack, and they finish in the opposite order from the one they started in.
What is a base case, and why does it matter?
The base case is the smallest version of the problem, the one answered with no further call: an empty list, a count that has reached zero, a cell that is the goal. Without one, or with a recursive call that does not actually shrink the problem, the calls never stop. Python raises RecursionError after about a thousand of them, which is the second demo on this page.
How does the call stack work in recursion?
Each call gets a stack frame of its own, holding its arguments, its local variables and the place to return to. The frames pile up as the calls go deeper, so ten calls deep means ten frames, each with its own copy of the variables. When a call returns, its frame is thrown away and the one below carries on from where it stopped. This is why the copies never get muddled, and why deep recursion costs memory.
What is a stack overflow?
Running out of room on the call stack, usually by recursing too deep. Python checks the depth itself and raises RecursionError instead of letting the program crash, and you can see the limit with sys.getrecursionlimit(). In C or C++ there is no such check, and the program falls over. Either way the cause is almost always a missing or unreachable base case.
What is backtracking?
Trying a choice, exploring what follows from it, and undoing the choice if it leads nowhere, then trying the next one. In the maze demo the choice is which neighbouring cell to step into, and undoing it is the path.pop(). Recursion suits backtracking because returning from a call automatically puts you back in the state you were in before you made the choice, with the right variables and the right place in the loop.
Why use recursion for a maze instead of a loop?
Because the undoing comes free. A loop would need its own list of cells to come back through, its own record of which directions each cell had already tried, and code to manage both. Recursion keeps all of that on the call stack without you writing any of it. Written as a loop with an explicit stack, it is the same algorithm and about twice the code, and that is exactly what depth-first search with a stack is.
Does recursive backtracking find the shortest path?
No. It finds the first path it reaches, and which one that is depends on the order it tries the directions. On this page the search looks at 11 cells and comes back with a path of 6; changing the order of WAYS finds a different path. For the shortest route, use breadth-first search, flood fill, or Dijkstra's algorithm.
Is recursion slower than a loop?
Usually a little, because each call costs a frame to set up and tear down, and in Python that is not free. It also costs memory in proportion to the depth, where a loop costs none. Some languages turn a recursive call in the last line of a function into a jump, which is called tail call optimisation, but Python deliberately does not. Write whichever is clearer, and if the depth might reach thousands, write the loop.
How deep can recursion go in Python?
About a thousand frames by default. sys.getrecursionlimit() reports the limit and sys.setrecursionlimit() changes it, but raising it is nearly always the wrong fix, because it turns a clear RecursionError into a real crash. If a program does need to go that deep, rewrite it as a loop with a list for the stack.
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- A2.1 Stack frames and the call stack Recursion and computational thinking, A level
- A2.2 Recursion Recursion and computational thinking, A level
- A2.3 Recursion versus iteration Recursion and computational thinking, A level
- A2.10 Project: out of the dead end Recursion and computational thinking, A level
- A4.3 Depth-first traversal Trees and graphs, A level
- A5.3 Linear and binary search Algorithms and complexity, A level
- A5.5 Merge sort Algorithms and complexity, A level