DailyRNG
Login
Basic

The base case

The base case is the branch that returns without calling itself. It is the smallest input whose answer you already know, and it is what makes the recursion end.

What you will see

0

About 3 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Write base cases that end cleanly.

1

Sum an empty list.

def total(a): if not a: return 0 return a[0] + total(a[1:]) print(total([]))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
0
2

First of a one-item list.

def first(a): if len(a) == 1: return a[0] return first(a[1:]) print(first([9]))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
9
3

Fib of 6.

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

Before you run it, say out loud what it will print. Then open the answer.

What it prints
8
4

Call with zero.

def h(n): if n <= 0: return 0 return h(n - 1) print(h(0))

Before you run it, say out loud what it will print. Then open the answer.

What it prints
0

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

The base case returns a known answer without recursing. It must be reachable and must match how the recursive call shrinks the input.
1 smallest input
↓
2 return known answer
↓
3 no further call
↓
4 chain ends
Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

def total(a): sets nothing on screen
if not a: sets nothing on screen
return 0 sets nothing on screen
return a[0] + total(a[1:]) sets nothing on screen
print(total([])) 0
Why this works
Know the smallest answer

Pick the input so small that you can state the answer with no recursion. That is your base case, and it must be reachable.

Match the shrink

The base test has to line up with how the recursive call reduces the input. Step by two and test for zero is a mismatch.

Examples

Empty is the base

def total(a):
    if not a:
        return 0
    return a[0] + total(a[1:])
print(total([2, 3]))

An empty list sums to zero. That base case ends the chain of calls.

One is the base

def first(a):
    if len(a) == 1:
        return a[0]
    return first(a[1:])
print(first([9, 7, 5]))

A one-item list has an obvious first item. The base case can be size one, not only zero.

Base case must be reached

def f(n):
    if n <= 0:
        return 0
    return f(n - 2)
print(f(5))

Stepping by two from an odd number still reaches the base because the test is less than or equal to zero.

Wrong base loops

def f(n):
    if n == 0:
        return 0
    return f(n - 2)
print(f(5))

Stepping by two from five never hits exactly zero. The base test must match how the input shrinks.

Two base cases

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

Zero and one are both base cases here. A base case can cover several small inputs.

Base returns a value

def g(n):
    if n == 0:
        return 100
    return g(n - 1)
print(g(2))

The base case carries the answer for the smallest input. Everything above it is built on that value.

Base before work

def s(a):
    if not a:
        return 0
    return a[0] + s(a[1:])
print(s([]))

Test the base case before touching the data. An empty list must not be indexed.

Base is the whole stop

def h(n):
    if n <= 0:
        return 0
    return h(n - 1)
print(h(0))

The base case is the only branch that does not recurse. Remove it and the calls never end.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← What recursion is
Previous Lesson
What recursion is
Next Lesson
Counting down and up
Counting down and up →