Recursion on Lists and Strings

20 min · Intermediate

Lists and strings are the easiest data to recurse on: take off the first item and solve the rest. This lesson covers that pattern, why slicing costs time, how to use an index instead, and how recursion handles nested lists.

The first item and the rest

Head and tail are the first item of a sequence and everything after it. Many recursive functions on lists and strings handle the head and call themselves on the tail.

To total a list of order amounts, add the first amount to the total of the rest. An empty list totals zero.

Python

1def list_sum(items):2    if not items:3        return 04    return items[0] + list_sum(items[1:])5
6
7print(list_sum([40, 15, 25]))

Example 1 · Largest order

Python

1def largest(items):2    if len(items) == 1:3        return items[0]4    rest = largest(items[1:])5    return items[0] if items[0] > rest else rest6
7
8print(largest([40, 95, 15, 60]))

Output

What this code does

A list with one item is the base case, so an empty list is not allowed here.
Compare the head with the largest of the tail.

Example 2 · What slicing costs

Python

1def copies(items):2    if not items:3        return 04    return len(items) - 1 + copies(items[1:])5
6
7print(copies(list(range(100))))

Output

What this code does

Each call copies the tail, which has one item fewer than its own list.
For 100 items that is 4950 copies, and it grows with n squared.

items[0] is the head and items[1:] is the tail. Each call gets a shorter list, so the empty list is always reached.

Pass an index instead of slicing

Index parameter is an extra argument that marks how much of the sequence is left to process. It replaces slicing, so the same list is shared by every call and nothing is copied.

Slicing copies the tail on every call, which is slow for long lists. Pass a position instead and the list is never copied.

Python

1def list_sum(items, start=0):2    if start == len(items):3        return 04    return items[start] + list_sum(items, start + 1)5
6
7print(list_sum([40, 15, 25]))

Example 3 · Count a value

Python

1def count(items, target, start=0):2    if start == len(items):3        return 04    here = 1 if items[start] == target else 05    return here + count(items, target, start + 1)6
7
8print(count([3, 1, 3, 3, 2], 3))9print(count([], 3))

Output

3
0

What this code does

here is 1 or 0 for the current position.
An empty list gives 0 straight from the base case.

The slicing version copies about n²/2 items in total, which is O(n²). The index version does O(n) work and uses O(n) stack space.

Strings: reverse and palindrome

Palindrome is a sequence that reads the same forwards and backwards, such as the text level. A recursive check compares the two ends and then the part between them.

A palindrome reads the same both ways. Compare the two ends, then check what lies between them.

Python

1def is_palindrome(text, low, high):2    if low >= high:3        return True4    if text[low] != text[high]:5        return False6    return is_palindrome(text, low + 1, high - 1)7
8
9word = "level"10print(is_palindrome(word, 0, len(word) - 1))

Example 4 · Reverse a string

Python

1def reverse(text):2    if len(text) <= 1:3        return text4    return reverse(text[1:]) + text[0]5
6
7print(reverse("order"))8print(reverse(""))

Output

redro

What this code does

The reversed tail comes first and the head goes last.
In real code text[::-1] is shorter and faster. This is the practice form.

Example 5 · A failed palindrome

Python

1def is_palindrome(text, low, high):2    if low >= high:3        return True4    if text[low] != text[high]:5        return False6    return is_palindrome(text, low + 1, high - 1)7
8
9for word in ("racecar", "python", ""):10    print(repr(word), is_palindrome(word, 0, len(word) - 1))

Output

'racecar' True
'python' False
'' True

What this code does

The empty string has high = -1, so low >= high holds at once.
python fails on the first comparison, p against n.

The base case is a middle with zero or one letters. A mismatch ends the search early, so the result is False at once.

Nested lists

Nested list is a list that has other lists as items. Its depth can vary, so recursion fits it well: a list is handled by handling each item, and an inner list is handled the same way.

Data from files can hold lists inside lists. The depth is unknown, so each item is either a value or another list to open.

Python

1def flatten(data):2    flat = []3    for item in data:4        if isinstance(item, list):5            flat.extend(flatten(item))6        else:7            flat.append(item)8    return flat9
10
11print(flatten([1, [2, [3, 4]], 5]))

Example 6 · Sum a nested list

Python

1def nested_sum(data):2    total = 03    for item in data:4        if isinstance(item, list):5            total += nested_sum(item)6        else:7            total += item8    return total9
10
11print(nested_sum([1, [2, [3, [4]]], 5]))

Output

What this code does

Numbers are added directly. Inner lists are summed by the same function.
The depth here is 4, so the stack is 5 calls at most.

The base case is any item that is not a list. The recursive case flattens a smaller list. Each level of nesting adds one call to the stack.

Next step

Check your understanding

10 quick questions

1def count(items, target, start=0):2 if start == len(items):3 return 04 here = 1 if items[start] == target else 05 return here + count(items, target, start + 1)6 7 8print(count([3, 1, 3, 3, 2], 3))9print(count([], 3))

1def is_palindrome(text, low, high):2 if low >= high:3 return True4 if text[low] != text[high]:5 return False6 return is_palindrome(text, low + 1, high - 1)7 8 9word = "level"10print(is_palindrome(word, 0, len(word) - 1))

1def is_palindrome(text, low, high):2 if low >= high:3 return True4 if text[low] != text[high]:5 return False6 return is_palindrome(text, low + 1, high - 1)7 8 9for word in ("racecar", "python", ""):10 print(repr(word), is_palindrome(word, 0, len(word) - 1))

Nested lists

Nested list is a list that has other lists as items. Its depth can vary, so recursion fits it well: a list is handled by handling each item, and an inner list is handled the same way.

Data from files can hold lists inside lists. The depth is unknown, so each item is either a value or another list to open.

1def flatten(data):2 flat = []3 for item in data:4 if isinstance(item, list):5 flat.extend(flatten(item))6 else:7 flat.append(item)8 return flat9 10 11print(flatten([1, [2, [3, 4]], 5]))

1def nested_sum(data):2 total = 03 for item in data:4 if isinstance(item, list):5 total += nested_sum(item)6 else:7 total += item8 return total9 10 11print(nested_sum([1, [2, [3, [4]]], 5]))