Python递归函数 分解

一、递归两大要素：起、止条件和递归方程

1、递归方程，即递归调用的方法

递归通俗的说就是在函数内部自己调用自己，如何调用就是递归方程，数学上的递归方程可以很复杂，但编程世界中的递归方程一般很简单。

以如下的sum(x)(x between 0...n)求和函数递归实现方式为例，递归调用方式就是返回n+sum(n-1)，这样sum(n)的计算方式就类似如下：

sum(n)=n+sum(n-1) #递归方程，以下为其展开
sum(n)=n+(n-1)+sum(n-2)
...
sum(n)=n+(n-1)+(n-2)+...+sum(1)
到这里递归循环就应该结束了，很自然的我们得到了递归循环的结束条件：n=0，此时的返回就不是0+sum(-1)了，直接返回0结束循环即可。

2、起止条件，即从哪里开始和结束
从哪里开始和结束要分情况，在上例中有明确的起止条件[0,n],正向进入递归时至n截止，反向进入递归时至0截止，选哪种逻辑都可以。
其他场景例如遍历二叉树这种，我们知道起始都是根节点(因为前序、后序、中序的遍历依据就是根节点)，结束时一定是最底层的叶子结点，那么只要开始处理下根节点，之后递归循环子节点至无子节点为止，终止条件就是到没有子节点的node。
一般的，我们把终止条件在函数中设置为终止退出的return语句，起始条件设为输入参数或者函数内的递归起始点。

二、递归函数示例：

#!/usr/bin/env python
def sum(list):
    sum = 0
    # Add every number in the list.
    for i in range(0, len(list)):
        sum = sum + list[i]    
    # Return the sum.
    return sum
print(sum([5,7,3,8,10]))


#!/usr/bin/env python
def sum(list):
   if len(list) == 1:
        return list[0]
   else:
        return list[0] + sum(list[1:])
print(sum([5,7,3,8,10]))
一般的，递归函数的代码更加简洁，且可以处理不能预定义递归层数的场景。

三、递归的易做图条件：
递归函数使用栈来存储函数调用，过多的递归会导致栈溢出，例如sum([一个超长的序列])，因此平时推荐使用简单循环即可，但是遇到需要进行多层循环或者根本不清楚循环层数的场景，递归就很有用了，只要确定了终止条件和递归方程就可以实现遍历。
在Python中递归超过1000此就会报出：“RuntimeError: maximum recursion depth exceeded”报错，因此递归也不是无限循环的，这个值也可以修改，你需要大致估算下你的递归次数，然后通过以下方式修改：

#!/usr/bin/env python
import sys
sys.setrecursionlimit(5000)
#阶乘实现示例：
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
print factorial(3000)
 四、递归函数的使用场景：

一些场景下循环层次数未知，使用递归会非常简便，例如遍历xml文件节点的代码：

#coding=utf-8
from xml.dom.minidom import parse
import sys
reload(sys)
sys.setdefaultencoding("utf-8")
root=parse('<xml文件名>').documentElement
#开始遍历节点
def iter_xmlNodes(node):
    if node == None:
        return
    if node.nodeType == node.ELEMENT_NODE: #只有ELEMENT_NODE类型的node才有遍历的必要
        print ("ELEMENT Node:%s" %(node))
        for child in node.childNodes:
            iter_xmlNodes(child)
    else:
        print ("Node:%s, NodeType:%d" %(node,node.nodeType))
#对于前两个if，第一个if表示终止条件，第二个if表示对输入节点的处理，对其子节点执行递归。
iter_xmlNodes(root)

# 再加一个场景，比如我们想要把类似如下格式的map转化为单层深度的格式：
m = {'a': 1, 'b': {'c': 2, 'd': 3, 'e': {'f': 4}}}
==> to
{'a': 1, 'b.c': 2, 'b.d': 3, 'b.e.f': 4}
# 起始条件就是上述m,终止条件即当m为单层时截至，递归方程即无限遍历前2层的压缩函数，代码如下：
from pprint import pprint
 
 
def isSimpleMap(m):
    """
    判断map是否是单层map(即非嵌套的map)
    :param m:
    :return:
    """
    for k, v in m.items():
        if isinstance(v, dict):
            return False
    return True
 
 
def shrinkMap(m):
    """
    压缩2层深度的嵌套map
    :param m:
    :return:
    """
    result_map = dict()
    for k, v in m.items():
        if isinstance(v, dict):
            for vk, vv in v.items():
                new_k = "%s.%s" % (k, vk)
                result_map[new_k] = vv
        else:
            result_map[k] = v
    return result_map
 
 
def squashMap(m):
    """
    通过递归压缩多层深度的嵌套map
    :param m:
    :return:
    """
    if isSimpleMap(m):
        return m
    else:
        return squashMap(shrinkMap(m))
 
if __name__ == '__main__':
    map_origin = {
        'a': 1,
        'b': {
            'c': 2,
            'd': 3,
            'e': {
                'f': 4
            }
        }
    }
    squashedMap = squashMap(map_origin)
    pprint(squashedMap)