Core · AlgorithmsLesson 6 of 8Free to read

Recursion and merge sort · Data Structures and Algorithms

How can a function solve a problem by calling itself?

Why you need it

Some problems contain smaller copies of themselves: a folder holds folders, a tree holds trees, sorting a list can mean sorting two halves. Recursion writes these naturally, and it's the basis of merge sort, tree traversal and most divide-and-conquer algorithms.

The intuition

Every recursive function has two parts:

Base case: a problem so small you answer it directly (an empty list, n = 0).
Recursive case: make the problem smaller, call yourself, combine the answers.

Trust that the smaller call works, the same way you trust len(). Each call waits on a stack (the call stack) until its smaller calls return.

Merge sort: split the list in half, sort each half recursively, then merge two sorted lists by repeatedly taking the smaller front item. O(n log n): log n levels of splitting, n work to merge each level.

Definition

Base case

The input a recursive function answers without calling itself. Without one, the calls never stop (RecursionError).

Divide and conquer

Split a problem into independent smaller parts, solve each (often recursively), and combine the results.

Examples

Sum a nested list

Try it yourself

A list may contain numbers or more lists, any depth deep. Recursion handles the nesting.

def total(items):
    s = 0
    for x in items:
        if isinstance(x, list):
            s += total(x)
        else:
            s += x
    return s

print(total([1, [2, 3], [4, [5, 6]]]))

Step by step

L4A list inside: let a smaller call add it up.
L7A plain number is the base case.
L101 + (2 + 3) + (4 + (5 + 6)).21

Merge sort

Try it yourself

Split, sort the halves, merge.

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    return out + a[i:] + b[j:]

def merge_sort(xs):
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    return merge(merge_sort(xs[:mid]), merge_sort(xs[mid:]))

print(merge([1, 4, 9], [2, 3, 10]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

Step by step

L4Take the smaller front item.
L10One side ran out; the rest of the other is already sorted.
L13Base case: 0 or 1 items are sorted.
L19Seven items, three levels of splitting.[3, 9, 10, 27, 38, 43, 82]

Common mistakes

No base case

A call that always calls itself never stops: RecursionError. Write the base case first.

Not getting smaller

f(n) calling f(n) (instead of f(n - 1)) never reaches the base case.

Quick quiz

1. What does this print?

def countdown(n):
    if n == 0:
        print("go")
        return
    print(n)
    countdown(n - 1)

countdown(3)

A
```
3
2
1
go
```
B
```
go
1
2
3
```
C
```
3
2
1
0
```

Show the answer

Answer: A

Each call prints its n and hands n − 1 on; 0 is the base case.

2. Why is merge sort O(n log n)?

Alog n levels of halving, n work to merge each level
BIt compares every pair once
CIt sorts in place

Show the answer

Answer: A

Halving gives log n levels; merging all lists on one level touches each item once.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictFollow the calls
Type exactly what this program prints.
ModifyAdd the base case
flatten(items) should turn a nested list into one flat list, but it calls itself on numbers too and crashes. Fix it so numbers are added directly.
WriteMerge two sorted lists
Write merge(a, b) that merges two sorted lists into one sorted list in O(len(a) + len(b)). Don't call sorted() or .sort().

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Recursion	递归	A function solving a problem by calling itself on a smaller version.
Base case	基本情况	The smallest input, answered without recursion.
Merge sort	归并排序	Sort halves recursively, then merge them: O(n log n).