Course 3.2Lesson 4 of 5

Recursion on text and lists

Recursion on text and lists uses the first item and the rest. The smaller problem is the text or the list without its first item, or without both ends. The base case is an empty text or list, or one with a single item. A palindrome test compares the first and last letters and then asks the same question about the middle. A recursive sum, length, search or count of a list takes the first item and adds the answer for the rest. Slicing makes a new copy at every call, so for long data a loop is better. Use recursion on lists when the idea is clearer, or when the structure itself has lists inside lists.

about 30 min1 simulation2 practice questions

Lesson 4 of 5Show all lessons

Try the code and the simulations beside the lesson.

What you will be able to do

After this lesson you can

break a text or a list into the first item and the rest,
write the base case for an empty or one-item sequence,
write recursive functions that reverse, count, add and search, and
say when a loop is a better choice.

The first item, and the rest

A text and a list share a useful property: you can always cut them into the first item and the rest. The rest is a smaller text or list of the same kind. That is a recursive structure, and recursion fits it.

The two slices to remember:

text[0] is the first item, and text[1:] is the rest.
text[0] is the first, text[-1] is the last, and text[1:-1] is the middle, without both ends.

The base case is almost always the empty sequence ("" or []), or a sequence with one item.

Text

Predict first, then run it. Look at each function.

reverse(text): the base case is a text of at most one letter, which is its own reverse. Otherwise, reverse the rest, and put the first letter at the end: reverse(text[1:]) + text[0]. For "abc", that is reverse("bc") + "a", which is "cb" + "a".
is_palindrome(text): a palindrome reads the same both ways, like level. The base case: a text of at most one letter is a palindrome. The step: if the first and the last letters differ, it is not. If they are the same, look at the middle: text[1:-1]. This smaller problem lost two letters.
count_letter(text, letter): the base case is an empty text, with 0. If the first letter matches, it is 1 plus the count in the rest. If not, it is just the count in the rest. The two branches both call the function on text[1:].

Lists

The same idea works for a list. The first item is items[0], and the rest is items[1:].

Function	Base case: `[]`	The step
`total`	0	`items[0] + total(items[1:])`
`length`	0	`1 + length(items[1:])`
`contains`	`False`	`True` if the first matches, else `contains(items[1:], target)`
`count_even`	0	1 or 0 for the first item, plus `count_even(items[1:])`

The shape is always: do something with the first item, and combine it with the answer for the rest. The thing you do and the way you combine are the only parts that change.

Notice contains. It stops as soon as it finds the target, and does not look at the rest, like a linear search with break.

For a short text it does not matter. For a long list, a version that passes a position instead of a slice saves all this copying.

The price of slicing

Each call makes a new copy of the rest of the list with items[1:]. For a list of 10 000 items, that is a lot of copying, and the recursion is also too deep (Python allows about a thousand calls). So, for a long list, a loop is the better tool. These recursive list functions are good for learning the idea, and for short lists. In practice, you would write sum(items), len(items) and target in items.

Recursion on lists becomes really valuable when the list holds lists inside lists, to any depth. A loop cannot easily handle that, and recursion can. You will meet it in the project.

Common mistakes

A base case that misses. For lists, len(items) == 1 fails for an empty list. Use the empty list as the base case.
Forgetting that text[1:] makes a copy. Not a problem for short texts.
The wrong end of the text: reverse(text[1:]) + text[0] and not text[0] + reverse(text[1:]), which would not reverse anything.
Comparing items == [] is fine, and not items is the same. Both mean "empty".
Using recursion on a very long list. A RecursionError.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

Warm-up. Open the problem Reverse a string and the problem A palindrome by recursion.
Build. Open the lab Reverse and palindrome. You write both functions, and the checker tries many texts, including an empty one.
Stretch. Write all_positive(items), which says whether every item of a list is more than 0, by recursion.

Remember these

Cut a text or list into the first item and the rest. The rest is the smaller problem.
The base case is an empty (or one-item) sequence.
The shape: do something with the first item, and combine it with the answer for the rest.
For long data, a loop is better than recursion with slices.