Python中求和递归教程

Question

我需要编写一个程序，为函数执行上下递归，但我完全不知道如何启动。我看过python文档，发现它更令人困惑，而不是有用。如果有人能为我指明关于教程和/或python中求和惯例的文档的正确方向，我将不胜感激。感谢

Answer 1

编写递归函数可能很难理解，但有一些很好的参考资料可以更好地解决此类问题。我强烈建议你买一本《小阴谋家》。在类似语言的方案中工作可能比在python中直接处理更容易。

在python中，递归求和可以写成：

def rsum( seq ):
    if not seq:
        return 0
    else:
        return seq[0] + rsum(seq[1:])

从第一性原理出发，值得注意的是，这个函数遵循一个非常常见的模式，它是一个折叠的例子。在python中，您可以将foldl和foldr写成：

def foldl( f, z, xs ):
    if not xs:
        return z
    else:
        return foldl(f, f(z, xs[0]), xs[1:])
def foldr( f, z, xs ):
    if not xs:
        return z
    else:
        return f(xs[0], foldr(f, z, xs[1:]))

使用更高阶的构建块，这意味着您可以真正将rsum写成：

def rsum(seq):
    return foldl( lambda a,b: a+b, 0, seq )

或者：

def rsum(seq):
    return foldr( lambda a,b: a+b, 0, seq )

Answer 2

以下是使用算法和数据结构解决问题的官方幻灯片：

http://www.pythonworks.org/pythonds/Slides.zip?attredirects=0&d=1

您可以查看第3章，它是关于递归算法的。