A recursive definition describes a structure through smaller instances of the same kind, together with cases that need no further expansion. An immutable linked list, for example, is either empty or a value followed by a tail linked list. The empty list stops the recursion; a nonempty list holds one value and another list. section 1.2
Listing 1.1 Example immutable linked list
sealed record LinkedList<T>(T? Value, LinkedList<T>? Tail)
{
public static LinkedList<T> Empty = new (default, null);#1
public LinkedList<T> Push(T value) => new (value, this);
public bool IsEmpty => this == Empty; #2
public override string ToString()
{
var s = "";
for (var list = this; !list.IsEmpty; list = list.Tail!)
s += list.Value + " "; #3
return s;
}
}
The C# record makes the definition concrete: Push creates a new list whose tail is the existing list. Its empty-list representation is convenient but permits invalid states, such as a nonempty list with an invalid tail. section 1.2
Recursion need not preserve the element type at each level. A deque can be empty, contain one item, or contain a left mini, a middle deque of minis, and a right mini. Keeping small chunks at the edges makes many pushes and pops cheap: they replace an edge mini and reuse the rest. When an edge fills, a chunk moves into the middle, where chunks are grouped again. section 3.3.2
That middle deque gives the definition a surprising type-level consequence. Each descent nests another generic type rather than merely repeating the containing type. The nesting is finite for any deque: its tree has O(log₃ n) levels for n items. C# and Java handle these generic types differently from languages that expand template instantiations into more code, such as C++. section 3.6
A square defined by smaller squares
A 0-quad is one live or dead cell. For n > 0, an n-quad consists of four (n−1)-quads: northeast, northwest, southeast, and southwest. This definition yields a square with side length 2ⁿ and places every leaf n edges from the root. section 4.3
A recursive definition also affects operations built on the structure. Compiler-generated value equality for a C# record list follows its recursively defined tail; comparing long lists can therefore overflow the call stack. Recursive formulas have alternatives, too: combinations satisfy C(n,k) = C(n−1,k−1) + C(n−1,k), but a direct formula avoids using that recurrence as a computation method. section 1.2.1 section 6.3.2
