Debugging a Recursive Search: Print, Fix, and Return Types

Why does a recursive search that only recurses on L[1:] find 1 in [2, 5, 8, 1] but miss it in [2, 1, 5, 8] — and how do print statements expose the skipped element?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

What the print statement shows

Here is the tempting first version of the membership test, with one extra line at the very top of the body so that every call announces the list it is currently examining:

## incorrect
def in_list(L, e):
    print(L)
    if len(L) == 1:
        return L[0] == e
    else:
        return in_list(L[1:], e)

Someone runs in_list([7, 3, 9, 4], 9). Assign to trace a list of lists: the value each call prints, in the order the calls happen.

# Exercise 1: every list the console shows, in order.
trace = []  # your code here

# Exercise 1: every list the console shows, in order.
trace = []  # your code here

Python runs in your browser

⌘/Ctrl + Enter runs

is a list

records at least one printed line

every entry is itself a list

has one line per call, and the calls stop where the base case bites

matches the lists the calls really receive, in order

←Previous Recursion on Lists: Peel One Element, Trust the Rest Next Nested Lists: Flatten, Search, and Why Loops Fall Short →