Lesson 11 - Introduction to Recursion

Learning Objective

Write a recursive function with a clear base case and recursive case, and understand why every recursive function needs both.

Introduction

Every function you’ve written so far has called other functions.

A recursive function is different because it calls itself.

At first this may seem unusual, but recursion is a natural way to solve problems that can be broken into smaller versions of the same problem.

For example:


factorial(5)

can be thought of as:


5 × factorial(4)

and:


factorial(4)

can be thought of as:


4 × factorial(3)

This continues until a simple case is reached.

Every recursive function must contain:

A base case that stops recursion
A recursive case that moves toward the base case

Without both, recursion never ends.

What Is Recursion?

A function is recursive when it calls itself.

Example:


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

This function is recursive, but it has a problem:


countdown(3)

never stops.

It keeps calling itself forever.

To make recursion safe, we need a base case.

Base Case and Recursive Case

A proper recursive function contains two parts:

Stops recursion.


if n <= 0:
    return

Base Case

Calls the function again with a smaller problem.


countdown(n - 1)

Recursive Case

Together they guarantee that recursion eventually ends.

Factorial Example

Factorial is a classic recursive problem.

Mathematically:


5! = 5 × 4 × 3 × 2 × 1

Recursive definition:


factorial(n) = n × factorial(n - 1)

Base case:


factorial(1) = 1

Implementation:


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

Code


# recursion_basics.py
 
def factorial(n):
    if n <= 1:                      # base case
        return 1
 
    return n * factorial(n - 1)     # recursive case
 
print(factorial(5))
 
def countdown(n):
    if n <= 0:
        print("Liftoff!")
        return
 
    print(n)
    countdown(n - 1)
 
countdown(3)
 
def sum_list(numbers):
    if not numbers:                 # base case: empty list
        return 0
 
    return numbers[0] + sum_list(numbers[1:])
 
print(sum_list([4, 8, 15, 16, 23]))

Expected Output

Click to see expected output


120

3
2
1
Liftoff!

66

Recursive Countdown

The countdown function works by reducing the value of n with every call.


countdown(3)

Execution:


countdown(3)
    countdown(2)
        countdown(1)
            countdown(0)

At:


n <= 0

the base case is reached and recursion stops.

Recursive List Processing

Recursion can process lists by handling:

The first item
The rest of the list

Example:


def sum_list(numbers):
    if not numbers:
        return 0
 
    return numbers[0] + sum_list(numbers[1:])

For:


[4, 8, 15]

Python evaluates:


4 + sum_list([8, 15])
8 + sum_list([15])
15 + sum_list([])

Then:


4 + 8 + 15 + 0

Result:

Visualizing Factorial


factorial(5)

Expands into:


5 × factorial(4)
5 × 4 × factorial(3)
5 × 4 × 3 × factorial(2)
5 × 4 × 3 × 2 × factorial(1)

Base case:


factorial(1) = 1

Then Python works backward:


2 × 1 = 2
3 × 2 = 6
4 × 6 = 24
5 × 24 = 120

Final result:

🔧 Under the Hood

What actually stops a recursive function from running forever?

Every function call is placed on Python’s call stack.

For example:


factorial(5)

creates:


factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)

Each call waits for the next call to finish.

Once the base case returns:


return 1

the stack begins to unwind.

The results flow back upward until the original call completes.

What If There Is No Base Case?

Consider:


def broken(n):
    return broken(n - 1)

There is no stopping condition.

Python continues creating stack frames until it reaches its recursion limit.

At that point it raises:


RecursionError

You can inspect the limit with:


import sys
 
print(sys.getrecursionlimit())

The default is usually around:

This protects programs from consuming unlimited memory due to runaway recursion.

Student Challenge

Challenge 1

Write a recursive function called digit_sum(n) that adds together all individual digits in a positive integer n (for example, digit_sum(12345) returns 15 because 1 + 2 + 3 + 4 + 5 = 15).

Define a base case: if n < 10, it is already a single digit, so return n.
Define a recursive case: extract the last digit using n % 10 and add it to digit_sum(n // 10), which handles the remaining digits.

Hint

These two operations are the key:


n % 10

Gets the last digit.


n // 10

Removes the last digit.

Each recursive call works with a smaller number than before.

Click to see solution


# digit_sum.py
 
def digit_sum(n):
    if n < 10:                      # base case: single digit
        return n
 
    return n % 10 + digit_sum(n // 10)
 
print(digit_sum(12345))

Challenge 2

Write a recursive function called drive_waypoints(bot, waypoints) that navigates your BonicBot through a list of route tuples (distance, angle) recursively instead of using a for loop.

Define a base case: if waypoints is empty (if not waypoints:), return to stop recursion.
In the recursive case: unpack the first waypoint distance, angle = waypoints[0], execute the drive and rotate actions on bot, and then recursively call drive_waypoints(bot, waypoints[1:]) with the remaining waypoints.
Test your function with a route list (such as [(0.4, 90), (0.3, 90), (0.4, 90), (0.3, 90)]).

Full SDK method details are available in the Python SDK reference.

Hint

This expression:


waypoints[1:]

creates a new list containing everything except the first waypoint.

Each recursive call receives a shorter list.

Eventually the list becomes empty:

[]

which triggers the base case.

Click to see solution


# challenge_recursive_patrol.py
 
from bonicbot_bridge import BonicBot
 
def drive_waypoints(bot, waypoints):
    if not waypoints:    # base case
        return
 
    distance, angle = waypoints[0]
 
    print(
        f"Driving {distance} m, "
        f"then turning {angle}°"
    )
 
    bot.drive_distance(distance, speed=0.2)
    bot.rotate_angle(angle, speed=45.0)
 
    drive_waypoints(
        bot,
        waypoints[1:]
    )    # recursive case
 
with BonicBot(host='192.168.0.188') as bot:
    route = [
        (0.4, 90),
        (0.3, 90),
        (0.4, 90),
        (0.3, 90),
    ]
 
    drive_waypoints(bot, route)
 
    bot.stop()

Recursion vs Loops

Recursion	Loops
Solves problems by calling itself	Solves problems by repetition
Requires a base case	Requires a stopping condition
Uses the call stack	Uses loop control structures
Can be elegant for tree-like problems	Often more efficient
Limited by recursion depth	No recursion depth limit

Neither approach is always better.

The best choice depends on the problem.

Reflection Question

If route had 500 waypoints instead of 4, why might the for loop version from Lesson 6 be the safer practical choice over this recursive version, given what you now know about Python’s recursion depth limit?

By the end of this lesson, you should be able to identify recursive problems, write recursive functions with base and recursive cases, understand how the call stack works, and recognize when an iterative loop may be a more practical solution than recursion.