Recursive function for counting elements

Question

def length(lst):
    if not lst:
        return 0
    else:
        return 1 + length(lst[1:])

I don't understand how this line of code: return 1 + length(lst[1:]), counts the number of elements. Could you explain me how does it work step by step.

The first check is simple: `if not lst` captures an empty list and returns 0. If the list is non-empty, we know there has to be at least one element, thus `1`. Then we recursively apply this function on a slicing of that list, cutting off the first element. If there are no more elements in the list, the slicing will return an empty list, which is captured by the first check, ending the recursion. Quite elegant! — mara004, Apr 15 '22 at 11:48

score 2 · Answer 1 · answered Apr 15 '22 at 11:47

Are you familiar with slice notation? lst[1:] will create a slice of the list from [1] to the end, therefore excluding the [0] element. So basically it will count 1 for the current element, then recursively call with the rest of the list, removing the front each recursive call. When it is finally called with an empty list it just returns 0 which is the base case.

You could imagine this sequence of calls looking something like

length([1,2,3,4])
1 + length([2,3,4])
1 + 1 + length([3,4])
1 + 1 + 1 + length([4])
1 + 1 + 1 + 1 + length([])
1 + 1 + 1 + 1 + 0

Recursive function for counting elements

1 Answers1