Stack space is the memory consumed by activation records for active function calls. Recursive algorithms consume it as their call depth grows; replacing recursive calls with an explicit work stack can shift storage away from the call stack without necessarily reducing total auxiliary space. section 6.3.1 section 9.3.3
Analyze stack space by asking how deeply execution can nest and what alternative data structure stores pending work:
- Recursive combination generation may reach O(n) call depth, even though each generated combination performs only O(k) deque operations. section 6.3.1
- A nonrecursive pretty-printer keeps pending documents in Stack<Doc>, using constant call-stack space while its work-stack space grows with ConcatDoc structure. section 9.3.3
- Recursive anti-unification uses at most O(n) stack space when traversing terms whose deepest leaf occurs at depth bounded by n. section 10.5
Replacing recursion with a work stack
Fits() begins with a Stack<Doc>, repeatedly pops a document, and pushes its children. This keeps call-stack use constant, while the document stack can grow to the number of ConcatDocs. 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;
}
}
}
// […]
Inspect the C# implementation that makes pending recursive work explicit and exposes the separate call-stack and work-stack costs. section 9.3.3
