Die Labs / Foundations
FoundationsWorking~4h
Turn Recursion Into Iteration Without Losing Correctness
You start with a genuinely recursive function (e.g. a tree/graph traversal or a recursive-descent parser) that provably stack-overflows on deep input, then rewrite it to use an explicit heap-allocated stack instead of the call stack — preserving exact output equivalence on every input the original could still handle, while now succeeding on inputs that used to crash.
Was er beweist
Der Satz, den du im Vorstellungsgespräch verteidigen kannst.
Lebenslauf-Zeile
Rewrote a recursive tree-traversal algorithm to use an explicit stack after profiling a production stack-overflow on deeply nested input, eliminating the crash while proving output-identical behavior against the original across 500+ generated test cases.
- understands call-stack mechanics, not just recursion syntax
- can manage explicit state (stack frames as data) correctly
- validates correctness with differential testing, not just 'it ran'
Die Aufgabenstellung
Was du Schritt für Schritt baust.
- 01A real recursive function operating on a non-trivial structure (e.g. DFS/traversal over a tree, or a recursive-descent expression parser) — not a toy factorial/fibonacci
- 02A reproducible crash: a generated pathologically deep/skewed input (e.g. a 50,000-node degenerate tree) that provably triggers a RecursionError / stack overflow / RangeError on the original implementation, captured as evidence
- 03An iterative rewrite using an explicit stack data structure that manually manages the state each recursive call frame used to hold (current node, visited children index, partial results) — no use of the language's call stack for the traversal itself
- 04Differential test harness that runs both implementations on hundreds of randomly generated inputs (shallow and moderately deep, where the recursive version still works) and asserts byte-for-byte identical output
- 05The same pathological deep input from step 2 is fed to the iterative version and completes successfully, with peak memory/heap usage measured and reported
- 06A short complexity note: confirm the iterative version's time complexity matches the recursive original (no accidental O(n) becoming O(n^2) from list operations on the explicit stack)
Der Beweis
Fertig, wenn diese Tests bestehen.
Original recursive implementation reproducibly crashes (RecursionError/stack overflow) on the generated deep input, captured as a logged stack trace
automated test
Property-based differential test shows identical output between recursive and iterative versions across 500+ generated cases
automated test
Iterative version completes successfully on the same deep input that crashed the recursive version, with measured peak memory reported
checked output
Complexity note confirms no asymptotic regression introduced by the explicit-stack rewrite
reviewed
Stack
Python or JavaScript/TypeScripta property-based testing library (Hypothesis or fast-check)a deep/degenerate input generator (e.g. a skewed linked-list-shaped tree)
Sage Method
frame → decide → prove
Du behältst
Recursive + iterative implementations, differential property-based test suite, crash-reproduction log, and a before/after performance note