Python递归挑战

Question

我目前正在介绍Python和计算理论课,最近有一个关于中期的难题,我根本无法解决.它涉及为添加数字的程序编写代码.我相信这个问题应该使用递归.我不记得问题究竟是如何措辞的,但这是基本的想法.

实现multiadder(n)函数,它接受一个非负整数n并将n任意值加在一起.要添加的每个值必须作为单独的调用写入.例如:

>>> multi_three = multiadder(3)
>>> multi_three(1)(2)(3)
6

>>> multiadder(5)(1)(2)(3)(4)(5)
15

必须通过填写空白来编写代码.

def multiadder(n):
    assert n > 0
    if _________________________ :
        return _________________________
    else:
        return _________________________

我们在课堂上讨论的主题是高阶函数,递归,lambdas和控制语句.我们不允许使用列表和集等数据结构,也不允许导入任何内容.

有人请帮忙.这是我无法测试的唯一问题!

Answer 1

试试这个:

def multiadder(n):
  assert n > 0
  if n == 1:
    return lambda t: t
  else:
    return lambda a: lambda b: multiadder(n-1)(a+b)

if __name__ == '__main__':
  print(multiadder(5)(1)(2)(3)(4)(5))

因为n == 1,结果必须是返回输入的函数.

对于n > 1,n-1通过添加输入来包装结果.

这也适用于连接字符串和其他累积操作:

>>> multiadder(3)('p')('q')('r')
pqr

Answer 2

你可以这样做,但它几乎是不可读的.我希望这些解释很有帮助:

def multiadder(n):
    assert n > 0
    if n == 0:
        return 0
    else:
        return (lambda f: lambda i, n, sm: f(f, i, n, sm))(
                    lambda rec, i, n, sm: sm+i if n == 0 else lambda j: rec(rec, j, n-1, sm+i)
                )(0, n, 0)

看它在repl.it上运行.

这个怎么运作

返回值包含三个主要部分:

(lambda f: lambda i, n, sm: f(f, i, n, sm))

总之,这个函数分配一个名称的函数,因此它可以递归调用.更详细:它需要一个函数f,它必须自己接受4个参数,其中第一个应该是一个自引用.这里返回的函数接受另外三个参数,并返回递归调用f.

第二部分是真正的核心:

(lambda rec, i, n, sm: sm+i if n == 0 else lambda j: rec(rec, j, n-1, sm+i))

这作为参数传递给上面的第一个函数,使递归成为可能.此函数采用上面提到的4个参数,并应用特定的逻辑:

• i 是必须添加的数字
• n 是在此之后仍然预期的值的数量
• sm是到目前为止的累计金额(不包括i)

根据是否需要更多值,此函数返回最终结果(sm+i)或具有一个参数的函数,该函数将执行与此处描述的相同(递归),具有减少的n和适应的总和.

最后,初始值传递给上面的:

(0, n, 0)

意思是,我们从数字0(虚拟),n期望值和当前总和0开始.

注意

由于上面代码中的递归不涉及调用multiladder,并且断言实际上排除了if条件为真,我们可以不这样做if...else:

def multiadder(n):
    assert n > 0
    return (lambda f: lambda i, n, sm: f(f, i, n, sm))(
                lambda rec, i, n, sm: sm+i if n == 0 else lambda j: rec(rec, j, n-1, sm+i)
            )(0, n, 0)