A base case terminates recursion by solving an instance without another recursive expansion. In recursive data structures and algorithms, it supplies the smallest result from which larger results can be composed. section 4.4.1 section 8.4
The stopping condition depends on what information is sufficient to make progress:
- HashLife stops at a level-2 quadtree: a 2-quad contains enough information to compute its center 1-quad one tick ahead, whereas level-1 and level-0 quadtrees do not. section 4.4.1
- Recursive graph coloring stops at the empty graph, whose nodes already satisfy the coloring constraint; the algorithm then assigns colors while unwinding. section 8.4
HashLife's quadtree base case
StepBaseCase asserts that its input has level 2, reads the sixteen cells of the 2-quad, counts neighbors for the center cells, and returns their future 1-quad. Larger quadtrees recursively produce smaller future quadtrees until this operation applies. section 4.4.1 section 4.4.5
Listing 4.8 The base case for the HashLife algorithm
private static IQuad Rule(IQuad q, int count) => #1
count switch { 2 => q, 3 => Alive, _ => Dead };
private static IQuad StepBaseCase(IQuad q) #2
{
Debug.Assert(q.Level == 2);
int a = (q.NW.NW == Dead) ? 0 : 1;
int b = (q.NW.NE == Dead) ? 0 : 1;
int c = (q.NE.NW == Dead) ? 0 : 1;
int d = (q.NE.NE == Dead) ? 0 : 1;
int e = (q.NW.SW == Dead) ? 0 : 1;
int f = (q.NW.SE == Dead) ? 0 : 1;
int g = (q.NE.SW == Dead) ? 0 : 1;
int h = (q.NE.SE == Dead) ? 0 : 1;
int i = (q.SW.NW == Dead) ? 0 : 1;
int j = (q.SW.NE == Dead) ? 0 : 1;
int k = (q.SE.NW == Dead) ? 0 : 1;
int l = (q.SE.NE == Dead) ? 0 : 1;
int m = (q.SW.SW == Dead) ? 0 : 1;
int n = (q.SW.SE == Dead) ? 0 : 1;
int o = (q.SE.SW == Dead) ? 0 : 1;
int p = (q.SE.SE == Dead) ? 0 : 1;
int nf = a + b + c + e + g + i + j + k;
int ng = b + c + d + f + h + j + k + l;
int nj = f + g + h + j + l + n + o + p;
int nk = e + f + g + i + k + m + n + o;
return Make(
Rule(q.NW.SE, nf), Rule(q.NE.SW, ng),
Rule(q.SE.NW, nj), Rule(q.SW.NE, n22));
}
The listing makes the base case concrete through its level assertion, cell extraction, neighbor counts, and Life rule. section 4.4.1
