Recursion Fundamentals — why it breaks your brain (and how to fix it) | Learn

StrongYes tip

Recursion isn't hard because it's complex. It's hard because it asks you to believe a function works before you've finished writing it. That leap of faith is the real skill.

Here's something nobody told me the first time I saw recursion:

The confusion you're feeling is not a sign that you're bad at this. It's a sign that your brain is doing exactly what it should — rejecting an unproven claim.

When you write a recursive function, you're saying "assume this function already works for a smaller input, and use that to solve the current one." Your brain hears that and goes: but I haven't proven it works yet. I'm literally still writing it.

That's the whole problem. Not base cases. Not stack overflows. Not "thinking in trees." The core issue is that recursion requires you to trust the function you haven't finished.

Julia Evans identifies this exact pattern in how we teach programming concepts — we introduce something that depends on understanding six things at once, and then wonder why people are confused. Recursion is the poster child. You're told "the function calls itself" as if that explains anything, when the real mental shift is about believing the call returns the right answer before you've traced through every step.

The Leap of Faith

Let's make this concrete. Here's a function that sums a list:

PYTHON

def sum_list(nums):
    if not nums:          # base case
        return 0
    return nums[0] + sum_list(nums[1:])  # recursive case

When you read sum_list(nums[1:]), your instinct is to trace it. "Okay, so it calls itself with [2, 3, 4], then that calls itself with [3, 4], then..." — and you're mentally holding four stack frames, losing track, and feeling like you're drowning.

That tracing instinct is the trap.

The fix is counterintuitive: stop tracing. Instead, assume sum_list(nums[1:]) returns the correct sum of the rest of the list. You haven't proven it yet. Trust it anyway.

If sum_list(nums[1:]) correctly returns the sum of everything after nums[0], then nums[0] + sum_list(nums[1:]) correctly returns the sum of the whole list.

That's it. That's the whole argument. The handles the empty list, and the recursive case handles everything else by trusting the recursive call.

Diagram

Rendering diagram...

Why Your Brain Resists

This isn't just a programming thing. It's a thinking thing.

Lilian Weng's research on reasoning systems shows that deliberate, step-by-step reasoning — what Kahneman calls System 2 thinking — is fundamentally harder than intuitive pattern-matching. Your brain wants to trace the recursion because tracing feels like understanding. But tracing a recursive function is System 1 trying to brute-force a System 2 problem.

The leap of faith IS the System 2 skill. You're not skipping the proof — you're using without realizing it:

Base case works. (You can check this — it's one line.)
If the recursive call works for smaller input, the current call works. (This is the leap.)
Therefore it works for all inputs. (That's induction.)

You don't need to trace fib(5) through eight stack frames to trust it. You need to verify two things: the base case is right, and if fib(n-1) and fib(n-2) return correct values, then fib(n-1) + fib(n-2) is correct too.

The Call Stack, Demystified

Okay — but sometimes you DO need to see the stack unfold, especially for interviews. The trick is knowing when to trace vs. when to trust.

Here's fib(5) unfolding. Watch the tree structure:

Diagram

Rendering diagram...

Notice something? fib(3) is computed twice. fib(2) is computed three times. This tree has 15 nodes for a problem of size 5. For fib(50), this tree has billions of nodes. That's not a recursion problem — that's a problem. The recursion itself is fine. The redundant work is what kills you.

How to talk through recursion in an interview

Name the subproblem

"I need fib(n). If I already had fib(n-1) and fib(n-2), the answer is just their sum."

1 / 4

That four-step script works for any recursive problem in an interview. Name the subproblem, state the base case, trust the call, analyze the cost.

The Two Mental Modes

Here's the framework I wish someone had given me:

Trust Mode

Trace Mode

When to use

Writing the function, verifying correctness

Debugging, analyzing time complexity

What you do

Assume the recursive call works. Check base case + recursive step.

Draw the call tree. Count nodes. Find repeated work.

Mental cost

Low — two things to verify

High — exponential in problem size

Interview use

Explain your approach, prove correctness

Analyze Big-O, identify optimization opportunities

Most people get stuck because they're in Trace Mode when they should be in Trust Mode. You don't trace Array.sort() every time you call it. You trust the contract: give it an array, get a sorted array back. Recursion is the same — you're just writing the contract yourself.

Aleksey Kladov (matklad) makes a related point about recursive functions: most real-world recursive algorithms are primitive recursive — they always terminate, always shrink the input, always make progress toward the base case. The scary "what if it runs forever?" scenario is mostly theoretical. If your input gets smaller every call and your base case is correct, it terminates.

Where People Actually Get Stuck in Interviews

It's not the simple cases. Nobody fails on "sum a list recursively." The real traps are:

Trap 1: The helper function that does two jobs

PYTHON

# BAD — what does this return? A count? A boolean? A modified list?
def helper(node, target, count):
    ...

If you can't describe what your recursive helper returns in one sentence, you have two functions mashed together. Split them.

Trap 2: Modifying state across recursive calls

PYTHON

# DANGEROUS — results is shared mutable state
def backtrack(nums, path, results):
    results.append(path[:])  # must copy!
    for i in range(len(nums)):
        path.append(nums[i])
        backtrack(nums[i+1:], path, results)
        path.pop()           # must undo!

requires you to undo every choice you make. Forget the path.pop() and your results are corrupted. The fix: think of each recursive call as a self-contained world. Whatever you change, change back.

Trap 3: Not seeing the recursion in non-obvious places

on a graph? Recursion. Parsing nested JSON? Recursion. Merge sort's divide step? Recursion. with top-down ? Recursion with a .

Once you see the pattern — "solve for smaller, combine for bigger" — you'll spot recursion hiding everywhere.

The Fix, In Practice

Here's the thing that finally made recursion click for me. It wasn't a textbook. It wasn't tracing through call stacks on a whiteboard. It was this realization:

Every recursive function is a contract with yourself.

The contract says: "If you give me a smaller version of this problem, I promise to return the right answer." The base case is where the contract is trivially true. The recursive case is where you use the contract to build up from there.

Interview question

Write a function that returns the depth of a binary tree.

Weak

“I'll check if the node is null, return 0. Then I'll go left, track the depth, go right, track the depth... actually, let me trace through an example tree first. So if the root is 1, left is 2, right is 3...”

Starts tracing immediately. Will get lost in a 4-level tree.

Strong

“The depth of a tree is 1 plus the max depth of its subtrees. Base case: null node has depth 0. So it's: if not node, return 0. Otherwise, return 1 + max(depth(left), depth(right)). I'm trusting that depth(left) and depth(right) return correct values for the subtrees.”

Names the contract, states the base case, trusts the call. Three sentences, done.

Unlock the full guide

Complete walkthrough, diagrams, and practice problems — all included with StrongYes Pro.

Unlock with Pro

This is how Coco coaches at StrongYes — permission to be confused first, then a clear path through. Try a session →

Practice Recursion.

Explain your thinking like you're in the interview.

Practice with Fin or Coco

Sources:

Evans, J. "Patterns in confusing explanations" (2021) — on why technical concepts feel harder than they are
Kladov, A. "Primitive Recursive Functions For A Working Programmer" (2024) — on why real recursion is safer than theory suggests
Weng, L. "Why We Think" (2025) — on System 1 vs System 2 reasoning and deliberate thought