DSA Recursion on Arrays

Recursion on arrays solves a list problem by splitting the list into head and rest. The head is the first value, and the rest is every value after it.

Adding a list by head and rest

The base case is an empty list, whose total is zero. Each other call adds the head to the total of the rest.

def total(values):
    if not values:
        return 0
    return values[0] + total(values[1:])

print(total([4, 7, 2]))
print(total([]))

Finding the largest value

The largest value is either the head or the largest value of the rest. A list of one value is the base case here.

def largest(values):
    if len(values) == 1:
        return values[0]
    rest_best = largest(values[1:])
    if values[0] >= rest_best:
        return values[0]
    return rest_best

print(largest([4, 9, 2, 7]))

Checking membership

Membership asks whether a target value appears in the list. The search answers False only after the rest runs out completely.

def contains(values, target):
    if not values:
        return False
    if values[0] == target:
        return True
    return contains(values[1:], target)

print(contains([4, 9, 2], 9))
print(contains([4, 9, 2], 5))

Example

def total(values, counter):
    counter[0] += 1
    if not values:
        return 0
    return values[0] + total(values[1:], counter)

def largest(values):
    if len(values) == 1:
        return values[0]
    rest_best = largest(values[1:])
    if values[0] >= rest_best:
        return values[0]
    return rest_best

def contains(values, target):
    if not values:
        return False
    if values[0] == target:
        return True
    return contains(values[1:], target)

data = [12, 5, 19, 8, 19, 3]
counter = [0]
print("list:", data)
print("total:", total(data, counter), "calls:", counter[0])
print("largest:", largest(data))
print("contains 8:", contains(data, 8))
print("contains 7:", contains(data, 7))

Key points

Splitting a list into head and rest gives each call a smaller list.
An empty list is a natural base case for list recursion.
Membership can stop early, because a match settles the answer at once.

In this example, three recursive tools run on one list of six values. The total tool makes seven calls, one per value plus the empty base case. The largest tool compares each head against the best value of the rest. The membership tool finds 8 in the list and reports that 7 is absent.

Note

Slicing with values[1:] builds a new list on every call, so this style copies data as it goes.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def total(values, counter):
    counter[0] += 1
    if not values:
        return 0
    return values[0] + total(values[1:], counter)

def largest(values):
    if len(values) == 1:
        return values[0]
    rest_best = largest(values[1:])
    if values[0] >= rest_best:
        return values[0]
    return rest_best

def contains(values, target):
    if not values:
        return False
    if values[0] == target:
        return True
    return contains(values[1:], target)

data = [12, 5, 19, 8, 19, 3]
counter = [0]
print("list:", data)
print("total:", total(data, counter), "calls:", counter[0])
print("largest:", largest(data))
print("contains 8:", contains(data, 8))
print("contains 7:", contains(data, 7))

Exercise

The recursive total tool runs on the list [2, 3, 4]. What does it return?

24 9 0 4