Python 中的求和递归教程

Question

我需要写一个程序，里面有一个函数要先向上递归，然后再向下递归，但我完全不知道该怎么开始。我看过Python的文档，结果觉得比帮助还要困惑。如果有人能给我指个方向，推荐一些关于Python中求和的教程或文档，我会非常感激。谢谢！

Answer 1

这里是关于算法和数据结构问题解决的官方幻灯片：

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

你可以查看第三章，里面讲的是递归算法。

Answer 2

写递归函数可能会让人感到困惑，但有一些很好的参考资料可以帮助你更好地解决这类问题。我强烈推荐你去看看《小程序员》这本书。用像Scheme这样的语言来学习，可能比直接用Python要简单一些。

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

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

从基本原理出发，值得注意的是，这个函数遵循了一个非常常见的模式，它是一个折叠（fold）的例子。在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 )