Recursion 101 — Base & Recursive Cases

By the end of this lesson you can:

• Identify the two parts of every recursive function — base case and recursive case.
• Write a small recursive function that counts down or sums.
• Trace a recursive call stack — what frame is active when.
• Avoid infinite recursion (and recognise RecursionError).

def countdown(n):
    if n <= 0:
        return                # ← base case: stop
    print(n)
    countdown(n - 1)          # ← recursive case: smaller problem

countdown(5)
# 5
# 4
# 3
# 2
# 1

Two branches. if n <= 0 stops. Otherwise print and call yourself with a smaller number. The recursion is guaranteed to end because n shrinks every step and the base case catches zero.

The skeleton

def recursive_func(args):
    if base_case_condition:
        return base_value          # the answer for the smallest input

    # recursive case
    smaller_args = make_smaller(args)
    smaller_answer = recursive_func(smaller_args)
    return combine(smaller_answer, args)

Four ingredients: condition for base, return value at base, way to shrink the args, way to combine the recursive answer with the current step.

Sum 1..n — combine pattern

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

print(sum_to(5))      # 5 + 4 + 3 + 2 + 1 + 0 = 15

Trace the calls:

sum_to(5) returns 5 + sum_to(4)
   sum_to(4) returns 4 + sum_to(3)
      sum_to(3) returns 3 + sum_to(2)
         sum_to(2) returns 2 + sum_to(1)
            sum_to(1) returns 1 + sum_to(0)
               sum_to(0) returns 0           ← base case
            unwinds to 1
         unwinds to 3
      unwinds to 6
   unwinds to 10
final: 15

Each call waits for the next to finish, then combines. The deepest call hits the base case; the answer bubbles back up.

Length of a list — list recursion

def length(lst):
    if lst == []:
        return 0
    return 1 + length(lst[1:])

print(length(["a", "b", "c", "d"]))    # 4

Base case: empty list. Recursive: drop the first item, add 1 to whatever the rest's length is. lst[1:] is the "everything but the head" slice.

Three rules for safe recursion

1. Always write the base case first. Forgetting it = infinite recursion = RecursionError: maximum recursion depth exceeded after about a thousand calls.
2. Make sure each recursive call moves toward the base case. Passing the same args = forever-loop. Use smaller numbers, shorter lists, simpler structures.
3. Trust the recursion. Don't try to imagine every level in your head — that's impossible past 3 deep. Trust that the recursive call returns the right answer for the smaller problem, and focus on combining it with the current step.

Infinite recursion · the crash

def forever(n):
    return forever(n - 1)        # ❌ no base case!

# forever(5)
# RecursionError: maximum recursion depth exceeded

Python protects you with a default depth limit (~1000). Hitting it means you forgot the base case or the recursive case isn't actually shrinking.

Reverse a string · build pattern

def reverse(s):
    if s == "":
        return ""
    return reverse(s[1:]) + s[0]

print(reverse("hello"))       # 'olleh'

Base: empty string reverses to empty. Recursive: reverse everything except the first char, then put the first char at the end.

The four shapes you'll see again and again

Numeric recursion         f(n) calls f(n-1) until n hits 0
List recursion            f(lst) calls f(lst[1:]) until lst is []
Divide & conquer          f(big) calls f(left half) + f(right half)
Tree recursion            f(node) calls f(child1) and f(child2) — fractals!

Today we focus on numeric and list. Tomorrow brings factorial, fibonacci, powers. The art lessons (33-35) introduce tree recursion via turtle.

Save as recurse_basics.py:

# recurse_basics.py — five tiny recursive functions

def countdown(n):
    """Print n, n-1, ..., 1."""
    if n <= 0:
        return
    print(n)
    countdown(n - 1)


def sum_to(n):
    """Sum 1..n."""
    if n == 0:
        return 0
    return n + sum_to(n - 1)


def length(lst):
    """Length of a list. Recursive — no len()."""
    if lst == []:
        return 0
    return 1 + length(lst[1:])


def max_in(lst):
    """Largest in a non-empty list. Recursive — no max()."""
    if len(lst) == 1:
        return lst[0]
    rest_max = max_in(lst[1:])
    return lst[0] if lst[0] > rest_max else rest_max


def reverse_str(s):
    """Reverse a string."""
    if s == "":
        return ""
    return reverse_str(s[1:]) + s[0]


# Demonstration
print("--- countdown ---")
countdown(5)

print("\n--- sum_to(10) ---")
print(sum_to(10))            # 55

print("\n--- length ---")
print(length(["a", "b", "c", "d", "e"]))     # 5

print("\n--- max_in ---")
print(max_in([3, 1, 4, 1, 5, 9, 2, 6]))      # 9

print("\n--- reverse_str ---")
print(reverse_str("Aisyah"))                  # 'hayisA'

Read the diff

Five functions, all 4-5 lines each. Every one has a clear base case at the top and a recursive case below it. Trust-the-recursion in action: max_in says "the max of the list is either the first item OR the max of the rest". The function doesn't solve the whole problem — it solves one step and lets the recursion handle the rest.

Every recursive function has two parts: a base case that returns directly, and a recursive case that calls itself with a smaller problem. Always write the base case first. Make sure each recursive call moves toward it. Trust that the recursive call returns the right answer for the smaller problem — your job is just to handle the current step. Forgetting the base case raises RecursionError after ~1000 nested calls.