Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Base case `n == 0` returns 0; else return `n + sum(n-1)`. Closed form n(n+1)/2 avoids recursion entirely.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you translate a recurrence and recognise recursion's stack cost.
Where candidates slip
Missing base case, or ignoring the stack-depth risk.
How to stand out
Mention the O(1) closed form and iterative alternatives.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Linear recursion
1Hint 1Explore hintHide hint
Express the sum to n in terms of the sum to n−1.
2Hint 2Explore hintHide hint
What's the base case?
3Hint 3Explore hintHide hint
Is recursion the best tool here, given large n?
A · Core idea
sum(n) = n + sum(n−1), bottoming out at sum(0) = 0 — the base-plus-shrink recursion applied to addition.
Why it mirrors the math. The definition reads exactly like the recurrence: the sum up to n is n plus the sum up to n−1. Each call peels off one term until it reaches the empty sum, 0.
Why recursion is the *wrong* tool at scale. Each call adds a stack frame, so this is O(n) stack depth; for n = 10⁵ that risks a stack overflow. The iterative loop is O(1) space, and the closed form n(n+1)/2 is O(1) time — both beat the recursion. Saying so shows judgement.
Tail-call note. Some languages optimise tail recursion to O(1) stack; Java and CPython do not, so the depth concern is real there.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3sum(3)
3 + sum(2)
waits6C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) stack spaceOpen the invariant and proofExplore the proofHide the proof
Mentioning the O(1) closed form shows you know recursion isn't always the right tool.
ComplexityO(n) time, O(n) stack space — n nested calls, each O(1) work, with an O(n)-deep stack.
E · Edge cases and pitfalls5n = 0 — Base case → 0.Explore edge casesHide edge cases
Edge cases handled
n = 0Base case → 0.n = 11 + sum(0) = 1.n = 100000Deep recursion risks stack overflow — prefer loop/formula.
Pitfalls
- No base case → stack overflow.
- Deep recursion blowing the stack for large n.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long sumTo(int n) { if (n == 0) return 0; return n + sumTo(n - 1); }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
- No base case → stack overflow.
- Deep recursion blowing the stack for large n.
Revise
Carry the pattern into the interview
Pattern to remember
Base case + shrink
Code pattern to memorize
sum(n) = n==0 ? 0 : n + sum(n-1)Rules to remember
- 1sum(0)=0.
- 2sum(n)=n+sum(n-1).
- 3Closed form n(n+1)/2.
Use this pattern when
- Illustrating linear recursion
Choose another pattern when
- Large n — use the loop or formula
Interview takeaway
Recursion mirrors the math, but a closed form may beat it.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA core fresher pattern: Base case + shrink. Master it on small inputs and it transfers to harder problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups