CODEWITHSUNDEEP
pythonrecursionreduce
OLGJ
OLGJ

Reputation: 432

Recursive reduce function in Python

I'm given a sequence tuple(range(1,5)) and I am supposed to write a recursive function with reduce to calculate the product 1*2*3*4*5 = 24.

I don't know how to do this recursively. I've tried looking here https://www.burgaud.com/foldl-foldr-python/ and understand reduce is left-fold. My non-recursive implementation is simply:

def red(func, seq):
    return reduce(func, seq)

red(lambda x, y: x*y, tuple(range(1,5)))

As reduce is left fold, how can I achieve this?

Upvotes: 1

Views: 383

Answers (2)

Asclepius
Asclepius

Reputation: 63282

The prior answer by Tobi will not work with an iterable input which is a standard expectation for reduce. This answer however will. It is adapted from a non-recursive implementation.

def reducer(func, iterable):
    # Ref: https://stackoverflow.com/a/77298563
    iterable = iter(iterable)  # Required for supporting `list` or `tuple` or `range` input.

    try:
        result = next(iterable)
    except StopIteration:
        raise TypeError('reduce() of empty iterable')

    try:
        return func(result, reducer(func, iterable))
    except TypeError:
        return result

Better yet, to avoid calling iter(iterable) repeatedly, an inner function can be used:

def reducer(func, iterable):
    # Ref: https://stackoverflow.com/a/77298563
    iterable = iter(iterable)  # Required for supporting `list` or `tuple` or `range` input.

    def inner(start, iterator):
        try:
            next_ = next(iterator)
        except StopIteration:
            return start
        new_start = func(start, next_)
        return inner(new_start, iterator)

    try:
        first = next(iterable)
    except StopIteration:
        raise TypeError('reduce() of empty iterable')
    return inner(first, iterable)

Usage examples:

> reducer(lambda i,j: i+j, range(1))
0

> reducer(lambda i,j: i+j, range(100))
4950

> reducer(lambda x, y: x*y, range(1,5))  # Example in question.
24

Upvotes: 0

Tobi208
Tobi208

Reputation: 1376

To make a function recursive, you need to add a case for termination (only one element left) and the recursive call in which you make the problem smaller (go one step ahead in the sequence)

def reduce(func, seq):
    if len(seq) == 1:
        return seq[0]
    return func(seq[0], reduce(func, seq[1:]))


print(reduce(lambda x, y: x * y, tuple(range(1, 5))))

Output:

24

If you're using python 3.10+, you should look into pattern matching for a more functional style in python.

Upvotes: 2

Related Questions