List Recursion

Recursion over lists is very similar to recursion over strings. Since lists in Python can be indexed and sliced like strings, the same principles that we learned in the last lesson also apply to lists.

A mystery recursion function

Here's an example of a recursive function that operates on a list:

def mystery(lst):
    if len(lst) == 0:
        return 0
    else:
        return lst[0] + mystery(lst[1:])

Storing the recursive return value

Consider the following recursive function, which counts the even numbers in a list:

def count_even_numbers(lst):
    if len(lst) == 0:
        return 0
    else:
        if lst[0] % 2 == 0:
            return 1 + count_even_numbers(lst[1:])
        else:
            return count_even_numbers(lst[1:])

For example, count_even_numbers([1, 2, 3, 4, 5]) would evaluate to 2, since there are two even numbers in that list.

This function checks whether the number at the first position of the list l[0] is even, and if it is, returns 1 plus the count of even numbers in the rest of the list (excluding the first character).

If the first number is not even, the function just returns the count of numbers in the rest of the list.

Here's an alternative way of implementing this function:

def count_even_numbers(lst):
    if len(lst) == 0:
        return 0
    else:
        count_in_rest = count_even_numbers(lst[1:])
        if lst[0] % 2 == 0:
            return 1 + count_in_rest
        else:
            return count_in_rest

In this version of the function, we made the recursive call first, stored its return value in a variable, and then used that variable when deciding what to return. This approach can be useful to simplify the code of your recursive functions and to clarify the logic.

Recursive binary search

At this point, we have mentioned binary search in multiple lessons, and even implemented it iteratively. Now, we are ready to implement a recursive version of binary search.

As before, binary search is suited for searching for a value in O(logn) time when the collection is sorted. Watch the following video to see how it is implemented.

Here's the version of binary search from the video:

def binary_search(lst, val, low, high):
    if low > high:
        return None
    else:
        mid = (low + high) // 2

        if lst[mid] == val:
            return mid
        elif val < lst[mid]:
            return binary_search(lst, val, low, mid - 1)
        else:
            return binary_search(lst, val, mid + 1, high)

Reminder: // in Python performs integer division, which will truncate any fractional part of the result. For example, 7 // 2 is 3.