How does reduce function work?

As far as I understand, the reduce function takes a list l and a function f. Then, it calls the function f on first two elements of the list and then repeatedly calls the function f with the next list element and the previous result.

So, I define the following functions:

The following function computes the factorial.

def fact(n):
    if n == 0 or n == 1:
        return 1
    return fact(n-1) * n


def reduce_func(x,y):
    return fact(x) * fact(y)

lst = [1, 3, 1]
print reduce(reduce_func, lst)

Now, shouldn't this give me ((1! * 3!) * 1!) = 6? But, instead it gives 720. Why 720? It seems to take the factorial of 6 too. But, I need to understand why.

Can someone explains why this happens and a work-around?

I basically want to compute the product of factorials of all the entries in the list. The backup plan is to run a loop and compute it. But, I would prefer using reduce.

Solution 1:

The other answers are great. I'll simply add an illustrated example that I find pretty good to understand reduce():

>>> reduce(lambda x,y: x+y, [47,11,42,13])
113

will be computed as follows:

(Source) (mirror)

Solution 2:

The easiest way to understand reduce() is to look at its pure Python equivalent code:

def myreduce(func, iterable, start=None):
    it = iter(iterable)
    if start is None:
        try:
            start = next(it)
        except StopIteration:
            raise TypeError('reduce() of empty sequence with no initial value')
    accum_value = start
    for x in iterable:
        accum_value = func(accum_value, x)
    return accum_value

You can see that it only makes sense for your reduce_func() to apply the factorial to the rightmost argument:

def fact(n):
    if n == 0 or n == 1:
        return 1
    return fact(n-1) * n

def reduce_func(x,y):
    return x * fact(y)

lst = [1, 3, 1]
print reduce(reduce_func, lst)

With that small revision, the code produces 6 as you expected :-)

Solution 3:

Your function calls fact() on both arguments. You are calculating ((1! * 3!)! * 1!). The workaround is to only call it on only the second argument, and pass reduce() an initial value of 1.