Writing Recursive Functions — Write recursive functions with correct base cases - Python

SECTION 1

Historical Context & Motivation

The idea of defining something in terms of itself might sound circular, but recursion is one of the most powerful concepts in computer science. Long before electronic computers existed, mathematicians realized that many natural processes — from the branching of trees to the spirals of seashells — follow patterns where each piece mirrors the whole. Translating that observation into a programming technique took decades of theoretical work, but today recursion sits at the heart of algorithms you use every time you search the web or sort a playlist.

1889 • Peano Axioms

Giuseppe Peano defined the natural numbers recursively: start with 0, and every number is the successor of the one before it. This gave recursion a rigorous mathematical foundation.

1936 • Church & Turing

Alonzo Church's lambda calculus and Alan Turing's theoretical machine both showed that recursion is fundamental to computation itself — any computable function can be expressed recursively.

1958 • LISP Is Born

John McCarthy created LISP, the first programming language built around recursion. LISP proved that recursive functions could be practical, not just theoretical.

1991 • Python Released

Guido van Rossum released Python, which supports recursion with clean, readable syntax. Python became a popular language for teaching recursive thinking to new programmers.

So why do we need recursion when we already have loops? The key insight is that some problems are naturally self-similar — they contain smaller copies of themselves. Calculating a factorial, navigating a file system, or solving a maze are all tasks where each step looks like a miniature version of the original problem. Recursion lets you write code that mirrors this structure directly, making solutions shorter, clearer, and often easier to reason about.

SECTION 2

Core Principles of Recursion

Every correct recursive function rests on two pillars. First, it needs a base case — a condition under which the function stops calling itself and returns a known value. Second, it needs a recursive case — a step that breaks the problem into a smaller version and calls the function again. If either piece is missing or wrong, the function either never finishes or produces incorrect results.

Base Case

The stopping condition. When the input is small or simple enough, the function returns a result directly without making another recursive call. Without this, the function runs forever.

Recursive Case

The self-referential step. The function calls itself with a smaller or simpler input, trusting that the recursive call will eventually reach the base case and return a correct answer.

Progress Toward Base Case

Each recursive call must bring the input closer to the base case. For example, if the base case is n == 0, each call should reduce n. This guarantees the recursion terminates.

The Call Stack

Python keeps track of each recursive call on a structure called the call stack. Each call waits for the one below it to finish. When the base case is hit, results cascade back up the stack.

✦

KEY TAKEAWAY

Think of recursion like looking into a set of Russian nesting dolls. You open each doll to find a smaller one inside (the recursive case). Eventually you reach the tiniest doll that doesn't open (the base case). Then you put them all back together from smallest to largest — that's how the answers flow back up the call stack.

SECTION 3

Visualizing the Recursive Call Stack

The diagram below traces how Python computes factorial(4) step by step. Notice how each call waits for the next one to finish. Once the base case returns 1, the results multiply back up through each waiting frame, ultimately producing 24.

The left column shows each recursive call descending toward the base case factorial(0) (highlighted in cyan). The right column shows the return values cascading back up, multiplying at each level until the final answer of 24 is produced.

This pattern applies to every recursive function. The calls descend with each recursive step, making the problem smaller. When they hit the base case, results begin ascending back through the stack. If you forget the base case, the purple arrows keep going down forever — Python will eventually crash with a RecursionError.

SECTION 4

How Recursive Functions Work in Python

Let's break down the anatomy of a recursive function in Python. The factorial function is the classic starting point: n! means multiplying all positive integers from 1 to n. We can express this recursively because n! = n × (n−1)!, and we know that 0! = 1.

RECURSIVE DEFINITION OF FACTORIAL

n! = n × (n − 1)! where 0! = 1

n is a non-negative integer. The base case is n == 0, which returns 1. The recursive case multiplies n by the factorial of (n − 1).

Python Implementation

Here is how you translate the mathematical definition into Python code:

💡

Factorial in Python

def factorial(n):
    if n == 0:          # Base case
        return 1
    else:               # Recursive case
        return n * factorial(n - 1)

Line 2 checks if we've reached the base case. If n is 0, return 1 immediately. Otherwise, line 5 calls the function again with a smaller input.

The Three Rules of Recursion

RULE 1 — BASE CASE EXISTS

f(0) = known value

There must be at least one input for which the function returns a result without calling itself.

RULE 2 — RECURSIVE CASE MAKES PROGRESS

f(n) calls f(n − 1) or f(n / 2), etc.

Each recursive call must use an input that is closer to the base case than the current input.

RULE 3 — TRUST THE RECURSION

Assume f(n − 1) returns the correct answer

When writing the recursive case, assume the recursive call works correctly. Focus only on how to combine that result with the current input.

SECTION 5

Common Recursive Patterns & Base Case Strategies

Choosing the right base case is the most critical decision when writing a recursive function. A missing base case causes infinite recursion, while an incorrect base case produces wrong answers. The diagram below shows four common patterns and their base cases.

Four common recursive patterns. The Countdown pattern decreases a number. Divide & Conquer halves a range. Shrinking Collection removes one element. Multi-Branch makes two recursive calls and may need multiple base cases.

⚠

Common Mistake: Missing or Wrong Base Case

If you write def factorial(n): return n * factorial(n - 1) without a base case, Python will call factorial(4), then factorial(3), ... factorial(0), factorial(−1), factorial(−2) ... and never stop. Python's default recursion limit is 1000 calls, after which it raises a RecursionError. Always write the base case first, then the recursive case.

SECTION 6

Worked Example: Recursive Sum of Digits

Let's write a function that takes a non-negative integer and returns the sum of its digits. For example, sum_digits(1234) should return 10 (because 1 + 2 + 3 + 4 = 10). We'll build it step by step, applying the three rules of recursion.

Writing sum_digits(n) Recursively

1
Step 1 — Identify the Base Case

What is the simplest input? A single-digit number (0 through 9). When n < 10, the sum of its digits is just n itself. So our base case is: if n < 10: return n.

Base case: n < 10 → return n
2
Step 2 — Define the Recursive Case

For a number with multiple digits, we can extract the last digit using n % 10 (the remainder when dividing by 10). The remaining digits are n // 10 (integer division by 10). So sum_digits(1234) equals 4 + sum_digits(123).

Recursive case: return (n % 10) + sum_digits(n // 10)
3
Step 3 — Verify Progress Toward Base Case

Each call uses n // 10, which always produces a smaller number. For example, 1234 → 123 → 12 → 1. Since 1 is less than 10, we hit the base case. Progress is guaranteed.

✓ n // 10 always moves toward the base case
4
Step 4 — Write the Complete Function

def sum_digits(n): if n < 10: return n return (n % 10) + sum_digits(n // 10) That's it — four lines of clean, readable code.

Complete function written and verified
5
Step 5 — Trace the Execution

Let's trace sum_digits(1234): sum_digits(1234) = 4 + sum_digits(123) sum_digits(123) = 3 + sum_digits(12) sum_digits(12) = 2 + sum_digits(1) sum_digits(1) = 1 ← base case! Now the returns cascade: 1 → 2 + 1 = 3 → 3 + 3 = 6 → 4 + 6 = 10.

sum_digits(1234) = 10 ✓

SECTION 7

Recursion vs. Iteration: Strengths & Limitations

Any recursive function can be rewritten as an iterative one using loops, and vice versa. So when should you choose recursion over iteration? The table below compares the two approaches across several important dimensions.

Dimension	Recursion	Iteration (Loops)
Code Readability	Often mirrors the mathematical definition; very readable for naturally recursive problems like trees and graphs	Can be more verbose but familiar to most beginners; straightforward for simple loops
Memory Usage	Each call adds a frame to the call stack; deep recursion can cause stack overflow	Uses constant extra memory for a loop variable; no stack buildup
Speed	Function call overhead makes recursion slightly slower; naive Fibonacci is exponentially slow	Generally faster due to no function call overhead
Problem Fit	Ideal for tree traversal, divide-and-conquer algorithms, backtracking, and problems with self-similar structure	Ideal for simple counting, array scanning, and tasks with a fixed number of repetitions
Python Limit	Default recursion limit is 1000 calls deep; can be adjusted but risks crashing the program	No inherent limit on loop iterations

Comparison of recursive and iterative approaches

✦

WHEN TO USE RECURSION

Choose recursion when the problem itself is recursive — when each piece looks like a smaller copy of the whole. Think of it like giving directions: 'Walk to the corner, then follow the same directions from there.' If the problem is more like 'Walk 100 steps forward,' a simple loop is the better tool.

SECTION 8

Connection to Advanced Recursion Techniques

Once you're comfortable writing basic recursive functions with correct base cases, there's a whole world of advanced techniques that build on the same principles. Understanding base cases is the foundation for everything that follows.

This Lesson	Advanced Technique	What's New
Single base case	Multiple base cases	Some problems need 2+ stopping conditions (e.g., Fibonacci needs n == 0 and n == 1)
One recursive call	Tree recursion	Functions that call themselves twice or more, creating a branching tree of calls
Simple return value	Memoization	Storing previously computed results to avoid redundant recursive calls; essential for Fibonacci
Stack builds up	Tail recursion	Restructuring the recursive call so it's the very last operation, enabling optimization in some languages (not Python)
Direct self-call	Mutual recursion	Two functions calling each other — function A calls B, which calls A, and so on

How this lesson connects to advanced recursion topics

All of these advanced techniques still rely on the core ideas from this lesson. You'll always need a well-defined base case, a recursive step that makes progress, and the trust that the recursion handles the smaller problem. Master these fundamentals, and the advanced material will feel like a natural next step.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

A student writes the following function:

def countdown(n):
    print(n)
    countdown(n - 1)

What will happen when countdown(5) is called? What is missing, and how would you fix it?

Show answer

The function has no base case, so it will print 5, 4, 3, 2, 1, 0, −1, −2, … and keep going until Python hits its recursion limit (default 1000) and raises a RecursionError. To fix it, add a base case at the beginning: if n < 0: return. This stops the recursion when n drops below 0, so it prints 5, 4, 3, 2, 1, 0 and then stops.

Question 2: BASIC CALCULATION

Write a recursive function power(base, exp) that computes base^exp (where exp is a non-negative integer). Identify the base case and trace power(3, 4).

Show answer

The base case is when exp == 0, in which case any number raised to the 0th power is 1. The recursive case returns base × power(base, exp − 1). The function is:

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

Tracing power(3, 4): 3 × power(3,3) → 3 × 3 × power(3,2) → 3 × 3 × 3 × power(3,1) → 3 × 3 × 3 × 3 × power(3,0) → 3 × 3 × 3 × 3 × 1 = 81.

Question 3: INTERMEDIATE

Write a recursive function reverse_string(s) that returns the reverse of a string. For example, reverse_string('hello') should return 'olleh'. Identify the base case and explain why your recursive step makes progress.

Show answer

The base case is when the string has 0 or 1 characters — a string that short is already its own reverse, so return s. The recursive case takes the first character and moves it to the end: return reverse_string(s[1:]) + s[0]. Progress is guaranteed because s[1:] is always one character shorter than s. Full function:

def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]

Question 4: APPLIED

You're writing a program to count files in a folder structure. Each folder can contain files and subfolders. The data is represented as a nested dictionary:

folder = {
  'files': ['a.txt', 'b.txt'],
  'subfolders': [
    {'files': ['c.txt'], 'subfolders': []},
    {'files': [], 'subfolders': [
      {'files': ['d.txt', 'e.txt'], 'subfolders': []}
    ]}
  ]
}

Write a recursive function count_files(folder) that returns the total number of files across all folders and subfolders.

Show answer

The base case is implicit: when a folder has no subfolders, the loop over subfolders simply doesn't execute. The function counts the files in the current folder, then recursively counts files in each subfolder:

def count_files(folder):
    count = len(folder['files'])
    for sub in folder['subfolders']:
        count += count_files(sub)
    return count

For the example above: root has 2 files, first subfolder has 1, second has 0 but its child has 2. Total: 2 + 1 + 0 + 2 = 5. This is a real-world example of the shrinking collection pattern — each recursive call processes a smaller portion of the tree.

Question 5: CRITICAL THINKING

Consider this recursive function:

def mystery(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + mystery(n // 2)
    else:
        return 1 + mystery(3 * n + 1)

(a) Trace mystery(6) and find the return value. (b) Does this function always terminate? Can you prove it, or is there a reason you can't? (c) What happens if you change the base case to n == 0 instead of n == 1?

Show answer

(a) Tracing mystery(6): 6→3→10→5→16→8→4→2→1. That's 8 recursive calls, so mystery(6) returns 8. (b) This is actually the famous Collatz conjecture! Mathematicians believe every positive integer eventually reaches 1 under these rules, but nobody has been able to prove it. So we can't formally guarantee termination for all inputs — this is one of the most famous unsolved problems in mathematics. (c) If the base case changes to n == 0, the function will never stop because the Collatz sequence for positive integers never reaches 0. This demonstrates how a seemingly small change to a base case can break a recursive function entirely.

SUMMARY

Lesson Summary

Summary

A recursive function is one that calls itself to solve smaller versions of the same problem. Every correct recursive function needs two essential components: a base case that stops the recursion and returns a known value, and a recursive case that breaks the problem down and calls the function again with a smaller input. The recursive case must always make progress toward the base case to guarantee the function eventually terminates.

We explored four common patterns: the countdown pattern (factorial, power), divide and conquer (binary search), shrinking collection (list sum, string reversal), and multi-branch recursion (Fibonacci). Python tracks each call on the call stack, with a default limit of 1000 frames. Recursion shines for problems with self-similar structure, while iteration is better for simple, flat repetition. Mastering base cases is the foundation for advanced techniques like memoization and tree recursion.