Module 1 · Recursion Fundamentals · Lesson 2 of 24

The leap of faith (the skill that makes recursion click)

2 min readTechInterviewNotes Editorial TeamUpdated 16 Sept 2026Save

What actually happens: the call stack

When C# calls a method, it pushes a stack frame (the method's parameters and locals) onto the call stack. The frame stays there, paused, until the call inside it returns. Here is SumTo(4), frame by frame:

GOING DOWN (winding the stack)	COMING BACK UP (unwinding)
`SumTo(4)`	`SumTo(0)` returns `0`
`needs SumTo(3), pauses`	`SumTo(1)` resumes: `1 + 0 = 1`
`SumTo(3)`	`SumTo(2)` resumes: `2 + 1 = 3`
`needs SumTo(2), pauses`	`SumTo(3)` resumes: `3 + 3 = 6`
`SumTo(2)`	`SumTo(4)` resumes: `4 + 6 = 10`
`needs SumTo(1), pauses`	`Final answer: 10`
`SumTo(1)`
`needs SumTo(0), pauses`
`SumTo(0) --> BASE CASE, returns 0 immediately`

Notice two things that trip people up:

Nothing is "computed" on the way down. The way down only sets up smaller and smaller questions. All the real work (n + ...) happens on the way back up, in reverse order.
Each call has its own private n. SumTo(4)'s n is 4; SumTo(3)'s n is 3. They are separate stack frames.

Recursion is not a loop reusing one variable — it's many paused copies of the function, each with its own state.

2.3 The leap of faith (the skill that makes recursion click)

The mental block most developers have: they try to trace every call in their head, get lost at depth 3, and conclude recursion is confusing.

Experienced people don't trace. They use the recursive leap of faith:

Assume the recursive call already works.
When writing SumTo(n), simply trust that SumTo(n - 1) returns the correct sum for n−1 — the same way you trust Math.Sqrt() without reading its source.
Your only jobs are:

handle the base case correctly, and
correctly combine one step with the trusted result.

If those two things are right, induction guarantees the whole thing is right.

This is exactly mathematical induction wearing a hoodie: prove the base case, prove that step k follows from step k−1, and the whole ladder holds.

2.4 Core recursion patterns in C#

These five small functions cover the patterns 90% of interview recursion is built from. Type each one.