Recursion

Lesson purpose

Some problems are easiest to solve by breaking them into smaller copies of the same problem. This lesson introduces recursion: functions that call themselves. Students learn the recursive mindset, the parts of a recursive function (base case, modified parameters, recursive call, returned result), the difference between linear and branching recursion, when recursion beats a loop (and when it does not), how recursive calls use memory on the call stack, and what tail recursion is.

For students who know C# and JavaScript: recursion works the same way in all three languages. The differences are practical: Python has a fairly low default recursion limit (about 1,000 calls) and, like C# and most JavaScript engines, does not optimize tail calls.

Learning objectives

By the end of the lesson, students should be able to:

• Describe the recursive mindset: solving a problem by reducing it to smaller, identical problems.
• Explain how a function can call itself, and define recursive function, base case, and infinite recursion.
• Decide when recursion is an appropriate tool compared with a loop.
• Apply a four-step checklist to design a recursive function.
• Trace a recursive number-guessing game.
• Convert a simple loop into linear recursion and explain divide-and-conquer.
• Recognize branching recursion, such as counting files in nested folders or computing Fibonacci numbers.
• Explain how recursive calls use memory blocks on a stack.
• Describe tail recursion and its rules.

1. Key components of recursion

The recursive mindset

Suppose a friend is thinking of a number between 1 and 100. You guess 27 and hear “higher.” Now the answer is between 28 and 100. Each response eliminates possibilities, so you can reach the answer much faster than by guessing randomly.

That is the recursive mindset: solve a big problem by applying the same steps to smaller and smaller versions of it. With 1 to 10 and an answer of 6:

Guess	Friend says	New range	Function equivalent
5	“Higher”	6 to 10	guess_number(1, 10)
8	“Lower”	6 to 7	guess_number(6, 10)
6	“Yes!”	Done	guess_number(6, 7)

Recursion basics

A quick review of functions:

• Functions are named blocks of code that perform a specific task.
• Parameters pass information in; return values pass information back.
• Functions are called to run their code.
• Functions can call other functions, and a function can call any function in scope, including itself.

A recursive function calls itself at least once. At each call it uses modified parameters to shrink the problem (in the guessing game, the lower and upper limits of the range). If the parameters are never modified, the function never stops; this is infinite recursion.

In Python, infinite recursion does not run forever the way an infinite loop does. Each call uses memory, so Python stops the program with RecursionError: maximum recursion depth exceeded after roughly 1,000 nested calls.

The base case

A base case is a condition where the function should stop recursing:

• It can signal an early exit: you guessed the number, so there is no need to update the range.
• It can represent a problem small enough to solve directly: if you run out of numbers to guess, the friend made a mistake and you can say so.
• A recursive function can have more than one base case.

A recursive function with no return value

Print the numbers 1 to 10:

def display_numbers(n):
    if n > 10:
        return
    else:
        print(n)
        display_numbers(n + 1)

display_numbers(1)

If n is greater than 10, the function returns without doing anything (base case). Otherwise it prints n and calls itself with n + 1 (modified parameter).

A recursive function that returns a value

Returned values pass back through the chain of calls like a game of telephone: each call hands its result to the call that made it, until the answer reaches the first call. Unlike the game, the computer never garbles the message.

def add_numbers(n):
    if n < 1:
        return 0
    else:
        total = n + add_numbers(n - 1)
        return total

print(add_numbers(10))   # 55

add_numbers(0) returns 0 (base case). add_numbers(1) returns 1 + add_numbers(0), which is 1.

Linear vs. branching recursion

• Linear recursion: each call calls itself at most once (or stops at a base case). It forms a single chain, is the easiest to program, and is the most similar to a for-loop. The guessing game is linear.
• Branching recursion: each call can call itself more than once, forming a tree of calls that each end at a base case.

Linear                      Branching
call                        call
 └─ call                    ├─ call
     └─ call                │   └─ base case
         └─ base case       └─ call
                                ├─ base case
                                └─ call
                                    └─ base case

When to use recursion

Ask:

• Can this problem be broken down into smaller problems?
• Are the smaller problems identical to the larger problem?
• Is there a way to divide the problem into smaller subproblems that are easy to solve?

Loops and linear recursion can do the same jobs, but they are different tools, like a hammer and a saw: you could cut wood with a hammer, but the saw is easier. Use a loop to repeat the same task without changing the conditions; use recursion when you need to reduce the problem to solve it.

Think of recursion as delegating: How can you hand smaller pieces of the problem to others? How do you put the results back together? What is the smallest task, the one you cannot delegate any further?

2. Using recursion to solve complex problems

A checklist for recursive functions

1. Check for the base case. “When should I stop?”
2. Modify the parameters. “How does the problem change with each recursive call?”
3. Invoke the function recursively.
4. Return the result to the calling function, if appropriate: pass it back unchanged or calculate a new value from it.

The guessing game

def guess_number(low, high):
    # Base case
    if low > high:
        return -1

    middle = (low + high) // 2
    hint = input("Is your number " + str(middle) + "? ")

    # Base case
    if hint == "correct":
        return middle
    # Higher
    elif hint == "higher":
        return guess_number(middle + 1, high)
    # Lower
    else:
        return guess_number(low, middle - 1)

print("Enter higher, lower, or correct.")
print("Think of a number between 1 and 10.")
number = guess_number(1, 10)
if number != -1:
    print("Your number is " + str(number) + "!")
else:
    print("You cheated :(")

Sample run (thinking of 6): Is your number 5? higher, Is your number 8? lower, Is your number 6? correct, Your number is 6!

Checklist applied:

• Base cases: low > high (the friend gave inconsistent answers, return -1) and "correct" (return middle).
• Modified parameters: middle + 1 becomes the new low, or middle - 1 becomes the new high.
• Recursive calls: guess_number(...) inside the elif and else.
• Returned value: the correct number (or -1), passed back unchanged through every call.

Loop vs. recursion side by side

Anything done with a loop can be done with recursion:

# Iterative
current_number = 1                 # first value
while current_number <= 10:        # condition (base case is the opposite)
    print(current_number)
    current_number += 1            # modification

# Recursive
def display_numbers(current_number):
    if current_number > 10:        # base case
        return
    else:
        print(current_number)
        display_numbers(current_number + 1)   # modification

display_numbers(1)                 # first value

The loop’s starting value becomes the first argument, its update becomes the modified parameter, and its stopping point becomes the base case.

Divide and conquer

Some recursion modifies parameters incrementally (adding 1 in display_numbers). Another design, divide and conquer, splits the problem each time. The guessing game cuts the range of possible answers in half with every guess until it conquers the problem.

Linear recursion: summing 1 to 10

Iteratively:

count = 0
for number in range(1, 11, 1):
    count += number
print(count)

With linear recursion:

def add_numbers(current_number):
    if current_number > 10:
        return 0
    else:
        next_number = current_number + 1
        count = add_numbers(next_number)
        return current_number + count

print(add_numbers(1))   # 55

Checklist: base case current_number > 10 returns 0; the parameter is modified to current_number + 1; the function calls itself; it returns current_number + count.

Branching recursion: counting files in nested folders

Goal: count every .txt file in a folder and all of its subfolders. Useful tools (from Lesson 11):

• os.listdir(folder) returns a list of the names in a folder.
• os.path.isdir(path) returns True if the path is a folder.
• os.path.join("folder", "subfolder", "example.txt") builds the path folder\subfolder\example.txt on Windows.
• "example.txt".endswith(".txt") returns True.

Correction: the book writes os.path.join(["folder", "filename"]) with square brackets. os.path.join() takes the parts as separate arguments, os.path.join("folder", "filename"); passing a list raises TypeError.

A single loop only counts the top folder. Adding a nested loop handles one level of subfolders, but a subfolder can contain another subfolder, and so on; you would need an unlimited number of nested loops. Each new folder is the same problem in a smaller form, which makes it perfect for recursion:

import os

def count_txt_files(folder):
    count = 0
    files = os.listdir(folder)
    for filename in files:
        file_path = os.path.join(folder, filename)

        # Base case
        if filename.endswith(".txt"):
            count += 1

        # Branching recursive calls
        elif os.path.isdir(file_path):
            subcount = count_txt_files(file_path)
            count += subcount

    return count

starting_folder = input("Enter a folder name: ")
final_count = count_txt_files(starting_folder)
print(final_count)

The function may call itself once for every subfolder, so this is branching recursion. It combines a for-loop with recursion to handle a nesting depth that no fixed set of loops could.

Branching recursion: Fibonacci

The Fibonacci sequence is defined recursively:

• The first number is 1 and the second number is 1.
• Every later number is the sum of the two before it: the nth number is the (n - 1)th plus the (n - 2)th.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

def fibonacci(n):
    # Base case
    if n == 1 or n == 2:
        return 1
    else:
        n1 = fibonacci(n - 1)
        n2 = fibonacci(n - 2)
        return n1 + n2

print(fibonacci(10))   # 55

Each call makes two recursive calls, so the number of calls grows very quickly.

Beyond the book: naive recursive Fibonacci recomputes the same values over and over; fibonacci(35) makes about 30 million calls. A loop, or recursion that remembers previous answers (memoization), is dramatically faster.

3. Managing memory during recursion

Memory blocks and the stack

Each time a function is called, the computer reserves a block of memory that holds the current state: the function’s variable names and their values.

def sum_numbers(current_number):
    if current_number == 0:
        return 0
    else:
        sum_total = sum_numbers(current_number - 1)
        return current_number + sum_total

print(sum_numbers(10))   # 55

Calling sum_numbers(10) needs 11 memory blocks: one each for current_number values 10, 9, 8, … 1, and 0.

Computers store these blocks on a stack, a data structure like a stack of pancakes: you can only add to the top and only remove from the top.

• Each recursive call pushes a new memory block on top of the stack.
• Each time a call finishes and returns, its block is removed from the top, and the call beneath it resumes where it left off.

sum_numbers(3) calls...                returns...
                      [n == 0]         [n == 0] → return 0
            [n == 1]  [n == 1]         [n == 1] → return 1 + 0
  [n == 2]  [n == 2]  [n == 2]         [n == 2] → return 2 + 1
  [n == 3]  [n == 3]  [n == 3]         [n == 3] → return 3 + 3 = 6

The longer the chain of calls, the more memory is needed; a computer can run out of memory if recursion goes on too long. This matters mainly for very large datasets.

Python connection: Python caps the stack at about 1,000 frames by default (sys.getrecursionlimit()), so sum_numbers(5000) raises RecursionError even though 5,000 iterations of a loop are trivial. C# programmers will recognize this as the equivalent of a StackOverflowException.

Tail recursion

Recursion uses memory because the computer must remember each unfinished call. Tail recursion is designed so that nothing needs to be remembered after the recursive call. Its rules:

1. The recursive call is the last line of code in the function.
2. The recursive call is in the return statement.
3. The return statement returns a single value: the value from the recursive call.

The trick is to pass the running total forward as a parameter instead of adding to it after the call returns:

# Regular recursion: the addition happens AFTER the recursive call returns
def sum_numbers(current_number):
    if current_number == 0:
        return 0
    else:
        sum_total = sum_numbers(current_number - 1)
        return current_number + sum_total

sum_numbers(10)

# Tail recursion: the recursive call is the entire return value
def sum_numbers(sum_total, current_number):
    if current_number == 0:
        return sum_total
    else:
        sum_total = sum_total + current_number
        return sum_numbers(sum_total, current_number - 1)

sum_numbers(0, 10)

Both versions sum 10 down to 1 and return 55.

Correction: the book says tail recursion “does not need additional memory.” That is only true in languages whose compiler performs tail-call optimization (such as Scheme). Python does not, and neither do C# or most JavaScript engines: the tail-recursive version above still creates one stack frame per call and still raises RecursionError past about 1,000 calls. Tail recursion is still a useful design pattern, and it converts easily into a loop, which is the Python way to avoid the memory cost.

Classroom application

1. Guess my number. Play the guessing game aloud with 1 to 100 and count the guesses; connect halving the range to divide and conquer.
2. Checklist practice. For display_numbers, add_numbers, and guess_number, have students label the base case, the modified parameter, the recursive call, and the returned value.
3. Loop to recursion. Convert loops that count down from 10, sum a list, and compute a factorial into recursive functions.
4. Trace the stack. Draw the stack of memory blocks for sum_numbers(4) as calls are made, then as they return.
5. Break it on purpose. Remove the base case or the parameter change and observe the RecursionError; then read the traceback together.
6. Nested folders. Build a practice folder with subfolders and .txt files, then run count_txt_files and compare it with a one-level loop.
7. Fibonacci timing. Time fibonacci(25), fibonacci(30), and fibonacci(32) to see how branching recursion grows.

Common misconceptions

• “A recursive function needs no stopping condition.” Every recursive function needs at least one base case that is guaranteed to be reached.
• “Infinite recursion runs forever like an infinite loop.” In Python it stops with a RecursionError when the stack limit is reached.
• “Calling the function again with the same argument is fine.” The parameters must change so the problem shrinks toward a base case.
• “The recursive call’s return value is used automatically.” You must return it (or use it); forgetting return in return guess_number(...) makes the caller get None.
• “Recursion is always better (or always worse) than a loop.” Use loops for straightforward repetition and recursion for problems that naturally break into smaller identical problems, like nested folders.
• “Linear and branching recursion are the same.” Linear calls itself at most once per call; branching may call itself several times.
• “Tail recursion saves memory in Python.” Python does not optimize tail calls; each call still uses a stack frame.
• “Each call shares the same local variables.” Every call gets its own memory block with its own copies of the parameters and local variables.

Lesson summary

• Recursion is a strategy for solving large problems by breaking them into smaller, identical problems; the same steps are applied to each smaller version with different restrictions.
• A recursive function calls itself at least once and uses modified parameters to reduce the size of the problem; without modification, it creates infinite recursion.
• A base case stops the recursion, either as an early exit (guessing the right number) or as a problem small enough to solve directly.
• A recursive function should check for the base case first, modify the parameters, invoke itself recursively, and do something with any returned value.
• Linear recursion calls itself at most once per call; branching recursion calls itself more than once.
• Loops and linear recursion are similar, but loops suit repeating the same task without changing conditions, while recursion suits reducing a problem to solve it.
• Each recursive call needs a block of memory on the stack, which is removed when the call returns.
• Tail recursion places the recursive call last, in the return statement, and passes results forward as parameters; languages that optimize tail calls can then avoid extra memory, but Python does not.