liveBook · Manning

Recursion

As explained in Algorithms Every Programmer Should Know

Recursion is a technique in which a function directly or indirectly invokes itself to solve progressively smaller or simpler instances of a problem.

Imagine looking for groups in a network where everyone is connected to everyone else. Trying every possible group quickly becomes impractical: 50 vertices have more than a quadrillion subsets. Recursion offers a way to explore one possible group, extend it with a compatible vertex, and then return to try another path. The Bron–Kerbosch algorithm uses this recursive backtracking to find maximal cliques. section 11.1

Each call carries three sets:

  • R is the clique built so far; every vertex in it connects to every other vertex in it. section 11.1
  • P contains vertices still eligible to join R. section 11.1
  • X records vertices already explored, preventing the same maximal clique from being reported again. section 11.1

Start with R and X empty and every vertex in P. Choose a vertex from P, add it to R, and make a recursive call. In that call, intersect P and X with the chosen vertex’s neighbors: only vertices compatible with the growing clique carry forward. When both P and X are empty, report R as a maximal clique. After a call returns, move its chosen vertex from P to X and try the next branch. An empty P alone is not enough: a vertex in X may show that R belongs to a clique already found. section 11.1

Follow one branch

On a small network, successive calls add vertices 1, 2, and 4 to R. Neighbor intersections narrow P until P and X are both empty, yielding maximal clique {1, 2, 4}. The calls then unwind so the search can explore other branches; one later branch finds {2, 3, 5}. section 11.1

Figure 11.3 Recursive trace of Branch 1 on the full network. The algorithm progressively locks nodes 1, 2, and 4 into R, pruning prospective candidates in P via neighbor intersections until both P and X are empty, confirming maximal clique {1, 2, 4}.

Trace how each recursive call grows R while neighbor intersections shrink the remaining candidates. section 11.1

Why does returning to an earlier branch work? Function calls use a last-in, first-out stack: a call finishes before control returns to the call that made it. Calls that keep stacking without finishing can cause stack overflow. Recursion is therefore more than repeating a function call; the search needs conditions that let branches finish. section 1.4.3 section 11.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces recursive state, branching, stopping, and backtracking through a graph, then provides pseudocode and Python implementations.
Examples
Traces a small network to maximal cliques {1, 2, 4} and {2, 3, 5}, including a branch rejected through X.
What it assumes
Introduces call-stack behavior with a stack analogy and defines the three graph-state sets before tracing recursive search.
What you can do after
Build it from scratch: implement recursive Bron–Kerbosch clique enumeration in Python, with an optional pivot variation.
How it connects
Connects recursion to backtracking, maximal cliques, set intersection, pivoting, and the call stack.

Also explained in

Compare how 25 books explain recursion →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.