Recursion solves a problem by solving a smaller version of it. The two questions are: what is the terminating case, and how does each call get closer to it? The smaller answer must also be assembled into the answer to the original problem. Recursive data structures, such as quadtrees and tree-shaped deques, make this pattern natural—but they do not make it automatically efficient. section 4.4.2 section 3.10
Color a graph by choosing its last node first
With c available colors, find a node whose degree is less than c. Remove it, recursively color the remaining graph, then give the removed node a color its neighbors did not use. The empty graph is the base case. In C#, the central call is graph.RemoveNode(last).ColorGraph(colors); the result is extended with coloring.Add(last, lastColor). If no eligible node exists, this algorithm returns failure: it has not established that the graph cannot be colored by another method. section 8.4
Listing 8.4 The simple recursive coloring algorithm
static class SimpleGraphColoring
{
public static ImmutableDictionary<N, C>? ColorGraph<N, C>(
this ImGraph<N> graph,
ImmutableHashSet<C> colors)
where N : notnull where C : notnull
{
if (graph.IsEmpty)
return ImmutableDictionary<N, C>.Empty;
N? last = graph.Nodes
.Where(n => graph.Edges(n).Count < colors.Count)
.FirstOrDefault(); #1
if (last is null)
return null;
var coloring = graph.RemoveNode(last).ColorGraph(colors);
if (coloring is null)
return null;
var usedColors = graph.Edges(last).Select(n => coloring[n]); #2
var lastColor = colors.Except(usedColors).First(); #3
return coloring.Add(last, lastColor);
}
}
The listing keeps the empty-graph base case, node removal, recursive call, and final color assignment together. section 8.4
The direction of work can be surprising. Graph coloring removes a node on the way down and assigns its color on the way back up. Quadtree-based Life instead breaks a grid into overlapping smaller regions, advances those regions, and assembles their centers. Its level-two quad is the base case; an empty quad has a cheaper terminating path because its center remains empty after one tick. The first recursive step makes nine smaller step calls for a non-base, nonempty quad, raising an immediate performance question. section 8.4 section 4.4.2
Figure 4.10 Given a 3-quad, we can extract nine 2-quads from it and step each of them forward one tick to get nine 1-quads one tick in the future.
The figure identifies the nine overlapping smaller quads used to advance a level-three quad. section 4.4.2
The same pattern handles problems with quite different meanings of “smaller”:
- Change-ringing permutations: Changes(0) yields the empty permutation. Changes(n - 1) supplies smaller permutations into which n - 1 is inserted; GetChange(n, p) instead uses a quotient and remainder to retrieve one numbered permutation recursively. section 6.2.4
- Binary-term anti-unification: equal terms need no further work; matching symbols preserve their names while their left and right children are processed recursively. A differing pair receives a hole, reused if that pair has already appeared. section 10.5
- Deque concatenation: handle trivial deques directly; otherwise, form suitable middle pieces and recursively concatenate the smaller middles. section 3.10 section 3.7
A recursive description does not require a recursive implementation. Retrieving a numbered lexicographic permutation can be expressed as a smaller-permutation problem, then written as a loop. Conversely, avoiding work now can hide a cost later: the change-ringing implementation uses lazy insertion, so its apparent constant-time construction does not describe the cost of enumerating the result; enumeration can traverse nested calls. section 6.2.1 section 6.2.4
Check call-stack depth as well as time and memory. Materializing a Hughes list assembled from n pushes and appends can consume O(n) stack space; even a few thousand elements may overflow the fixed-size .NET call stack. Loops work for the immutable stack and queue implementations, but the Hughes list’s deferred structure is hidden inside closures, making that substitution unavailable there. For deeply nested processing, an explicit stack is another alternative. section 2.7.6 section 9.0
