Recursion Fundamentals: Base Case, Recursive Case, and the Call Stack

Recursion is a function calling itself with a smaller version of the same problem. The first time you see it, it feels like a trick — how can a function be defined in terms of itself without spinning forever? The answer is that every recursive function must contain two things: a base case that does not recurse, and a recursive case that moves toward the base case. Once those two pieces are in place, the function unwinds naturally.

The two parts

Every recursive function has the same skeleton:

def f(n):
    if base_case_condition(n):
        return base_answer
    return combine(n, f(smaller(n)))

If you forget the base case, the function recurses forever and Python raises RecursionError. If the recursive case does not make the problem smaller, same outcome. Getting these two right is the whole job.

Factorial — the canonical first example

n! = n × (n-1) × (n-2) × ... × 1. Notice the recursive structure: n! = n × (n-1)!. That gives us the recursive case for free. The base case is 0! = 1 (and 1! = 1).

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120

Read it back: “factorial of n is one if n is one or less; otherwise it’s n times factorial of n - 1.” The definition matches the math.

The call stack

Each function call gets its own frame on the call stack — a stack of pending invocations, each waiting for its inner call to return. When factorial(5) is running, the stack looks like this:

┌──────────────────────────┐
│ factorial(1) → returns 1 │  ◀── top (active)
├──────────────────────────┤
│ factorial(2) waits on 1  │
├──────────────────────────┤
│ factorial(3) waits on 2  │
├──────────────────────────┤
│ factorial(4) waits on 3  │
├──────────────────────────┤
│ factorial(5) waits on 4  │  ◀── bottom (original call)
└──────────────────────────┘

When factorial(1) returns 1, its frame is popped. factorial(2) now has its answer (2 * 1 = 2) and returns. Then factorial(3) (3 * 2 = 6), then factorial(4) (4 * 6 = 24), then factorial(5) (5 * 24 = 120). The stack unwinds in reverse order.

The takeaway: recursion uses memory proportional to how deep the calls go. Ten thousand nested calls means ten thousand stack frames.

Sum of a list

def list_sum(items):
    if not items:
        return 0
    return items[0] + list_sum(items[1:])

print(list_sum([1, 2, 3, 4]))    # 10

The base case is the empty list (sum is 0). The recursive case peels off the first element and recurses on the rest. Each call’s problem is strictly smaller than the previous one, so we will reach the base case.

This particular implementation is wasteful — items[1:] builds a new list every call. Use an index instead for efficient recursion:

def list_sum(items, i=0):
    if i == len(items):
        return 0
    return items[i] + list_sum(items, i + 1)

Same idea, no copying.

Fibonacci and the recursion tree

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, ... — each number is the sum of the two before it.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(6))    # 8

This is a beautiful definition and an awful implementation. Each call spawns two more, and the same subproblems are computed over and over. Drawing the recursion tree makes the waste obvious:

fib(4)
/      

fib(3)      fib(2)
/   \       /    

fib(2) fib(1) fib(1) fib(0)
/   

fib(1) fib(0)

fib(2) is computed twice. fib(1) is computed three times. For fib(30) the tree has over a million nodes. We will fix this with memoization in the Dynamic Programming Introduction post — recursion plus a cache turns this from exponential into linear.

Recursion vs iteration

Anything you can write recursively, you can write with a loop. So why use recursion?

• It mirrors the structure of the problem. Tree traversals, divided-and-conquer algorithms (merge sort, quicksort), and parsers are far cleaner recursively.
• It eliminates manual stack bookkeeping. When iteration would force you to manage your own stack of “work to do later,” recursion uses Python’s stack for free.

When iteration is the better choice:

• The problem is a simple linear walk (sum, count, transform).
• The recursion depth could exceed Python’s stack limit (default about 1000).
• Performance matters and the function call overhead is significant.

Compare:

# recursive
def count_down(n):
    if n == 0:
        print("done")
        return
    print(n)
    count_down(n - 1)

# iterative
def count_down(n):
    for i in range(n, 0, -1):
        print(i)
    print("done")

Both work. The loop is shorter, faster, and won’t blow the stack at n = 10_000.

Stack overflow — what to watch for

Python’s default recursion limit is around 1000. Hit it and you get RecursionError: maximum recursion depth exceeded.

def deep(n):
    if n == 0:
        return 0
    return 1 + deep(n - 1)

deep(2000)    # RecursionError

Three ways out:

1. Rewrite iteratively.
2. Raise the limit with sys.setrecursionlimit — only if you understand the consequences (you can crash the interpreter).
3. Use tail-call style and let an explicit stack take over — see below.

A note on tail recursion

A function is tail recursive when the recursive call is the very last action — nothing waits on its return value:

def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, acc * n)    # tail call

In some languages (Scheme, Scala), the compiler turns tail calls into loops, removing the stack growth. Python does not do this. A tail-recursive Python function still uses one stack frame per call. The pattern is still useful — it makes the function easier to convert to a loop — but it does not save memory on its own.

Worked example — a simple tree walk

Where recursion really earns its place is on tree-shaped data. Here is a directory-style nested structure:

tree = {
    "name": "root",
    "children": [
        {"name": "a", "children": [
            {"name": "a1", "children": []},
            {"name": "a2", "children": []},
        ]},
        {"name": "b", "children": [
            {"name": "b1", "children": []},
        ]},
    ],
}

def count_nodes(node):
    return 1 + sum(count_nodes(child) for child in node["children"])

print(count_nodes(tree))    # 6

One line of recursion replaces a non-trivial iterative walk with an explicit queue or stack. This is the shape of problem recursion was made for.

Practice problems

Solve each before reading the solution.

1. Sum of digits

Write digit_sum(n) that returns the sum of digits of a non-negative integer.

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(digit_sum(1234))    # 10

2. Greatest common divisor

Use Euclid’s algorithm: gcd(a, b) = gcd(b, a % b), base case b == 0.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(48, 18))    # 6

3. Count occurrences in a list

def count(items, target, i=0):
    if i == len(items):
        return 0
    return (1 if items[i] == target else 0) + count(items, target, i + 1)

print(count([1, 2, 3, 2, 2, 1], 2))    # 3

4. Palindrome check

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome("racecar"))    # True
print(is_palindrome("hello"))      # False

5. Flatten a nested list

def flatten(items):
    result = []
    for x in items:
        if isinstance(x, list):
            result.extend(flatten(x))
        else:
            result.append(x)
    return result

print(flatten([1, [2, [3, 4], 5], 6]))    # [1, 2, 3, 4, 5, 6]

6. Print all subsets of a list

def subsets(items, i=0, current=None):
    if current is None:
        current = []
    if i == len(items):
        print(current)
        return
    subsets(items, i + 1, current)                  # exclude
    subsets(items, i + 1, current + [items[i]])     # include

subsets([1, 2, 3])
# []
# [3]
# [2]
# [2, 3]
# [1]
# [1, 3]
# [1, 2]
# [1, 2, 3]

Recap

You now know:

• Every recursive function needs a base case and a recursive case
• The call stack stores one frame per pending call
• A recursion tree is the best way to see repeated subproblems
• Recursion shines on tree-shaped problems; loops win on flat linear ones
• Python doesn’t optimise tail calls — deep recursion can crash the interpreter

Next steps

The fibonacci tree we drew above had repeated subproblems. The next post introduces dynamic programming — recursion’s smarter cousin, which solves each subproblem once and remembers the answer.

→ Next: Dynamic Programming: Memoization and Tabulation

Questions or feedback? Email codeloomdevv@gmail.com.