Python递归函数

参考：

https://www.python-course.eu/recursive_functions.php

一、递归函数两大要素 -- 终止条件和递归方程

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

递归通俗的说就是在函数内部自己调用自己，如何调用就是递归方程。

以以下的sum(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、终止条件，即从哪里开始和结束
从哪里开始和结束要分情况，在上例中有明确的结束条件n=0，n>0则进入递归循环，其隐形的条件就是n不能小于0，因此其开始条件写个n>0即可。

而其他场景例如遍历B树这种，开始一定是根节点，结束时一定是叶子结点，那么只要开始处理下根节点的打印，之后递归循环子节点即可，因此初始返回值就是根节点相关，之后递归调用以便遍历子节点和后代节点们，终止条件就是找不到子节点。

二、递归函数示例：

#!/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)

巴特西

Python递归函数

最新文章

热门文章