A stack is a last-in, first-out collection: push work onto one end, then pop the most recently added item. That makes it useful when an algorithm must finish newly discovered subproblems before returning to older ones. An explicit work stack can replace recursive calls when deeply nested input might exhaust a thread’s fixed call stack. section 9.3.3
Consider checking whether a pretty-printing document fits in the space left on a line. Start a Stack<Doc> with the document. Pop one doc at a time: add text length to the used width, or push a child that still needs checking. A concatenation requires its left child before its right; because the stack is last-in, first-out, push the right child first. Return false once used exceeds the available width, and true when no work remains. section 9.3.3
Listing 9.3 A nonrecursive Fits method
abstract record class Doc
{
// […]
private bool Fits(int width)
{
var docs = new Stack<Doc>(); #1
docs.Push(this); #2
int used = 0; #3
while (true)
{
if (used > width) #4
return false;
if (docs.Count == 0) #5
return true;
Doc doc = docs.Pop();
switch (doc)
{
case TextDoc td:
used += td.text.Length;
break;
case GroupDoc gd:
docs.Push(gd.doc);
break;
case IndentDoc id:
docs.Push(id.doc); #6
break;
case OptBreakDoc bd:
used += bd.text.Length; #7
break;
case ConcatDoc cd:
docs.Push(cd.right); #8
docs.Push(cd.left);
break;
}
}
}
// […]
The Fits listing makes the replacement for recursion visible: a loop repeatedly pops a Doc, accounts for its width, and pushes unfinished child work. section 9.3.3
The same idea handles state that a recursive call might otherwise carry implicitly. Pretty uses a stack of (bool, int, Doc) tuples. Each item records whether optional breaks print as text, the indentation to use after a line break, and the doc to print. Group decisions can then change the state attached to subsequent work without relying on nested calls. section 9.3.4
Listing 9.4 A nonrecursive Pretty method
using System.Text;
abstract record class Doc
{
// […]
public string Pretty(int width)
{
var sb = new StringBuilder();
int used = 0; #1
var docs = new Stack<(bool, int, Doc)>(); #2
docs.Push((true, 0, new GroupDoc(this))); #3
while (docs.Count > 0) #4
{
(bool fits, int indent, Doc doc) = docs.Pop(); #5
switch (doc)
{
case TextDoc td:
sb.Append(td.text); #6
used += td.text.Length;
break;
case GroupDoc gd: #7
docs.Push((gd.doc.Fits(width - used), indent, gd.doc));
break;
case IndentDoc id: #8
docs.Push((fits, indent + IndentSpaces, id.doc));
break;
case OptBreakDoc bd:
if (fits) #9
{
sb.Append(bd.text);
used += bd.text.Length;
}
else #10
{
sb.AppendLine();
sb.Append(' ', indent);
used = indent;
}
break;
case ConcatDoc cd: #11
docs.Push((fits, indent, cd.right));
docs.Push((fits, indent, cd.left));
break;
}
}
return sb.ToString();
} }
The Pretty listing shows why the stack holds tuples rather than docs alone: each pending task carries its line-break decision and indentation. section 9.3.4
The trade-off is not that the work disappears; it moves from recursive calls to an explicit, growable data structure. That matters for document graphs that can be much deeper than their parse trees. The stack keeps traversal order and pending state under the algorithm’s control while avoiding deep call-stack use. section 9.3.3 section 9.5
