The 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.
它证明了什么
你可以在面试中捍卫的一句话。
简历亮点
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'
简介
你逐步构建的内容。
- 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)
证明
当这些通过时，即完成。
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
技术栈
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
你将保留
Recursive + iterative implementations, differential property-based test suite, crash-reproduction log, and a before/after performance note