带有reduce的函数式递归函数

Question

我得到了一个序列

tuple(range(1,5))

，我应该用reduce编写一个递归函数来计算乘积1*2*3*4*5 = 24。

我不知道如何递归地执行此操作，我尝试在这里查看https://www.burgaud.com/foldl-foldr-python/并了解reduce是左折叠。我的非递归实现很简单：

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

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

由于reduce是左折叠，我该如何实现这一点？

Answer 1

要使函数递归，您需要添加终止情况（只剩下一个元素）和递归调用，使问题变得更小（按顺序前进一步）

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))))

输出：

24

如果您使用的是 python 3.10+，您应该研究模式匹配，以在 python 中获得更实用的风格。

Answer 2

Tobi 之前的 答案不适用于可迭代输入，这是

reduce

的标准期望。然而这个答案会。它改编自非递归实现。

def reducer(func, iterable):
    # Ref: https://stackoverflow.com/a/77298563
    iterable = iter(iterable)

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

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

更好的是，为了避免重复调用

iter(iterable)

，可以使用内部函数：

def reducer(func, iterable):
    # Ref: https://stackoverflow.com/a/77298563
    iterable = iter(iterable)

    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)

使用示例：

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

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