Is there a reason I'm getting IndexError: list index out of range on this recursive function?

Question

I struggle a lot with recursion and my brain doesn't seem to be able to process this question apparently. Can anyone explain why this doesn't work?

Question prompt: Write a recursive program that computes the product of all numbers in a given list.

def product(L):
    if L[0]==0:
        return 0
    else:
        if len(L) > 0:
            return L[0] * product(L[1:])

I thought first checking the length would always make sure to cover the empty list case.

Answer 1

There are two issues.

1. L[0]==0 checks if the first element in the list contains the value of 0. It is not a check on the length of the list. In particular, if all of the elements in the list are nonzero, the recursive function will eventually call itself with an empty list and try to access L[0], causing an IndexError.

2. The empty product has a value of 1. Your base case should return 1, not 0 -- doing the latter would cause the function to always output 0.

Here is a recursive solution that fixes both of these issues:

def product(L):
    if len(L) == 0:
        return 1
    else:
        return L[0] * product(L[1:])

Answer 2

Edit

The other answer gives you code that will work, and succinctly points out where the problem is. This answer is intended more to show you how to figure out the solution for yourself.

/Edit

It's often a good idea to pick a very small input and try to step through it yourself, on paper. In this case let's try

product([1,2,3])

L[0] is 1, so we skip to the else, then len(L) is 3 so we return 1 * product([2,3]), and then we have

product([2,3])

which we move into again. L[0] is 2, so we skip to the else, and then len(L) is 2 so we return 2 * product([3]). All good so far.

product([3])

L[0] is 3, so skip to else, and len(L) is 1, so return 3 * product([]), and then

product([])

L[0] is... ah, there is no L[0] - L is empty. That's where the IndexError is coming from. Now you know where the error is, you can fix it - move the check for the length of the list to before that (and add a base case) and you get

def product(L):
    if len(L) > 0:
        if L[0] == 0:
            return 0
        else:
            return L[0] * product(L[1:])
    else:
        return 1

which will work.