递归_python递归结构

递归是解决问题的一种方法，它将问题不断地分成更小的子问题，直到子问题可以用普通的方法解决。通常情况下，递归会使用一个不停调用自己的函数来进行。

引例

现存在一个数字列表（numlist），计算数字列表各数字之和。

第一种方法，通过循环实现：

def listsum(numlist):
    nSum = 0
    for i in numlist:
        nSum = nSum + i

	return nSum

第二种方法，通过递归实现： 递归的逻辑不是循环，而是将问题分解成更小、更容易解决的子问题。

def listsum(numlist):
    if len(numlist) == 1:
        return numlist[0]
    else:
        return numlist[0] + listsum(numlist[1:])

• 其中，数字列表 numList 的各元素总和等于列表中的第一个元素（ numList[0] ）加上其余元素之和，而其余元素则是 numList[1:] 列表的各元素。可以说，numList[1:] 是将第一个元素剔除后得到的新列表。
• 代码中第 2 行检查列表是否只包含一个元素。这个检查非常重要，同时也是该函数的退出语句。对于长度为 1 的列表，其元素之和就是列表中的数。这同时也是算法停止递归的条件，停止条件通常是小到足以直接解决的问题。
• 代码中第 5 行 listsum 函数通过调用自己来进行下一步操作，所以将 listsum 函数称为递归函数，每一次递归都改变了问题的状态并向停止条件靠近。

总结递归：一系列递归调用其实就是一系列的简化操作。每一次递归调用都是在解决一个更小的问题，如此进行下去，直到问题本身不能再简化为止。所以当问题无法再简化时，我们开始拼接所有子问题的答案，以此解决最初的问题。