Recursion Explained: Base Case, Recursive Case, Unwinding

Recursion is a function that solves a problem by calling itself on a smaller copy of the same problem. It is the idea behind tree traversals, depth-first search, merge sort, backtracking and most dynamic programming, and it is the topic where people most often say "I get it when I read it, but I can't write it." The fix is not more examples. It is two rules, one recipe, and a clear picture of what the runtime does with each call.

The problem it solves

Some problems are defined in terms of themselves:

• A folder's size is its files plus the sizes of the folders inside it.
• A tree's height is one more than the taller of its two subtrees.
• The sum of a list is its first item plus the sum of the rest.

Writing those as loops means managing your own bookkeeping of "where was I?". Writing them recursively lets the language do that bookkeeping: each call gets its own copy of its variables, and when it finishes, execution resumes exactly where the caller left off.

The intuition

A recursive function needs two parts, and missing either one breaks it:

• A base case that answers directly, without calling itself. It is the only thing that ever stops the chain.
• A recursive case that calls itself on a strictly smaller input, so every chain of calls is guaranteed to reach the base case.

When writing one, ask three questions in order. What is the smallest input, and what is its answer? That is the base case. How do I make the input smaller? Drop one item, move one index, halve a number. If the smaller call already returned the right answer, how do I finish? That last step is the "leap of faith": you do not trace the smaller call in your head, you trust it, exactly as you trust len() without reading its source.

Then there is the runtime's side. Every call gets a frame, and a caller's frame stays open, waiting, until the call it made returns. The frames form a stack: the last call made is the first to finish. So anything that happens before the recursive call happens on the way down, in call order, and anything after it happens on the way back up, in reverse.

Watch it run

The animation runs the lesson's countdown(3), with the frames alive on one side and the printed output on the other. A recursive function needs two parts: a base case that answers directly, and a step that makes the problem smaller. countdown(3): 3 is not 0, so it prints 3 and calls itself with n - 1, and the problem just got smaller. countdown(2) is a brand new call with its own n, while the caller is still open, waiting underneath. countdown(1) is still not the base case, so it shrinks the problem one more time. Then n == 0: the base case prints "liftoff" and answers without calling anything, the only thing that stops the descent. countdown(0) returns and its frame disappears, and the chain unwinds in the reverse order it was built: each call returns to the one below it until nothing is left, four calls and four returns. Then the experiment: delete the n == 0 branch and nothing ever answers. The calls keep shrinking past zero, printing 0 and -1 and onwards, until Python gives up. Base case plus a strictly smaller sub-problem; miss either one and the function never finishes.

The code

The lesson's countdown, and its mirror image with the print moved after the call. Same calls, opposite order, because the second one prints on the way back up:

def countdown(n):
    if n == 0:                  # base case: answer directly
        print("liftoff")
        return
    print(n)                    # before the call: on the way down
    countdown(n - 1)            # recursive case: a smaller problem

def countup(n):
    if n == 0:
        return
    countup(n - 1)
    print(n)                    # after the call: on the way back up

countdown(3)                    # prints 3, 2, 1, liftoff on four lines
countup(3)                      # prints 1, 2, 3 on three lines

The three-question recipe on three problems. Each recursive call moves an index or halves a number instead of slicing, because a slice copies the list and would quietly make the sum O(n²):

def total(nums, i=0):
    if i == len(nums):                        # 1. smallest input: nothing left, sum 0
        return 0
    return nums[i] + total(nums, i + 1)       # 2. smaller: one index on; 3. finish: add

def is_palindrome(s, lo=0, hi=None):
    hi = len(s) - 1 if hi is None else hi
    if lo >= hi:                              # zero or one character left
        return True
    return s[lo] == s[hi] and is_palindrome(s, lo + 1, hi - 1)

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)                   # halve the exponent: depth ~ log2(n)
    return half * half * (x if n % 2 else 1)

print(total([4, 8, 15, 16, 23, 42]))                   # 108
print(is_palindrome("racecar"), is_palindrome("recursion"))   # True False
print(power(3, 13), 3 ** 13)                           # 1594323 1594323

def no_base_case(n):
    return no_base_case(n - 1)                # nothing ever answers

import sys
try:
    no_base_case(3)
except RecursionError:
    print("RecursionError, limit", sys.getrecursionlimit())   # RecursionError, limit 1000

Checked on 2,000 seeded random inputs against a brute force: Python's built-ins and plain loops. The same check measures the depth each function reaches, which is where the linear and logarithmic versions part ways:

import random

def deepest(fn, *args):
    """Run fn and return the deepest recursion level it reached."""
    depth = [0, 0]
    def tracer(frame, event, arg):
        if event == "call" and frame.f_code is fn.__code__:
            depth[0] += 1
            depth[1] = max(depth[1], depth[0])
        elif event == "return" and frame.f_code is fn.__code__:
            depth[0] -= 1
    sys.settrace(tracer)
    try:
        fn(*args)
    finally:
        sys.settrace(None)
    return depth[1]

rng = random.Random(31)
ok = True
for _ in range(2_000):
    nums = [rng.randint(-50, 50) for _ in range(rng.randint(0, 40))]
    word = "".join(rng.choice("ab") for _ in range(rng.randint(0, 9)))
    x, n = rng.randint(-5, 5), rng.randint(0, 60)
    loop_power = 1
    for _ in range(n):
        loop_power *= x                            # brute force: n multiplications
    ok &= total(nums) == sum(nums)
    ok &= is_palindrome(word) == (word == word[::-1])
    ok &= power(x, n) == loop_power
    ok &= deepest(total, nums) == len(nums) + 1    # one frame per item, plus the base case
    ok &= deepest(power, x, n) == (n.bit_length() + 1)
print(ok)                                          # True

The complexity

• Time is the number of calls times the work per call. countdown(n) and total make n + 1 calls with constant work each: O(n). power makes about log₂ n calls: O(log n).
• Space is the deepest chain of frames alive at once, not the total number of calls. total holds n + 1 frames at its deepest, so it uses O(n) stack even though a loop would use O(1).
• Branching changes everything. A function that calls itself twice per level, like naive Fibonacci, makes an exponential number of calls; the Big-O cheat sheet has the recursion rows, and dynamic programming is the fix.

Where it goes wrong

• A base case that can be skipped. if n == 0 with an n that steps by 2 from an odd number jumps straight past zero. Write the base case as n <= 0 when the step is larger than one.
• A step that does not shrink. Calling f(n) from f(n), or on a list that is not shorter, recurses until the limit.
• Forgetting to return. total(nums, i + 1) without return in front of it computes the answer and throws it away.
• Deep input in Python. As of September 2026, CPython's default recursion limit is 1000, and it does not eliminate tail calls, so a recursive walk down a 10,000-node linked list fails. Tail recursion explains why, and an explicit stack is the portable fix.

When it shows up in interviews

Everywhere trees and graphs appear: tree traversals, depth-first search, backtracking, and reversing a linked list recursively. Expect "what's the space complexity?" with the call stack as the answer, and "can you do it iteratively?" as the follow-up.

How to say it in an interview

"I'll solve it recursively. The base case is the empty input, which returns zero directly. The recursive case handles the first element and calls itself on the rest, one index further, so every call is strictly smaller and the chain must reach the base case. I'll trust the smaller call to be correct and just combine its answer with the current element. Time is O(n) for n calls with constant work each, and space is O(n) for the call stack, which in Python also means a long input can hit the recursion limit, so for very deep inputs I'd convert it to a loop."