Python递归函数

2018-11-22 08:45:42来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

参考:
https://pythonspot.com/recursion/
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文件名>')
#开始遍历节点
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)

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:数据解析

下一篇:python3多线程—卖票