美文网首页
Python递归

Python递归

作者: 断尾壁虎V | 来源:发表于2017-12-01 19:13 被阅读0次

在python中,如阶乘运算,函数的自身循环调用等叫做递归。
递归主要有递推和回溯两个阶段。
递归的效率低,需要在进入下一次递归时,保留当前的状态,解决方法是尾递归,即在函数的最后一步(而非最后一行)调用自己。但是python没有尾递归,且对递归层级做了限制
1.必须有一个明确的结束条件
2.每次进入更深一层递归时,问题规模相比山此递归应有所减少
3.递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以递归调用的次数过多,会导致栈溢出)

在默认情况下,系统会对递归做层级的限制,默认是1000:

>>> import sys
>>> sys.getrecursionlimit()
1000

当然,我们也可以修改这个值:

>>> sys.setrecursionlimit(500)
>>> sys.getrecursionlimit()
500

当然不推荐修改。

递归的使用

循环和递归具有相似的功能,但是在有些场景下,我们无法指定循环的条件时,使用递归就能很好的是实现.
如,打印出列表中的所有数字:

a=[1,[2,[3,[4,[5,[6,[7,[8,[9,10,11],12]]]]]]]]

def list_num(list_n):
    for i in list_n:
        if type(i) is list:
            list_num(i)
        else:
            print(i)
list_num(a)

二分法

在使用递归对有序数列进行查找时,使用二分法可以极大的提高算法效率。二分法的的原理是每次都截取一半,在这一半中查找需要的值。这里使用递归:

a=[0, 1, 2, 3, 6, 7, 8, 9, 33, 44, 54, 66, 67, 878]

def findnum(num,l):
    print(l)
    if len(l)==1:
        if l[0] == num:
            print('find this num')
        else:
            print('not exist')
        return

    half_index=len(l)//2
    if num == l[half_index]:
        print('find this num')
        return
    elif num > l[half_index]:
        l=l[half_index:]
    elif num < l[half_index]:
        l=l[:half_index]
    findnum(num, l)   # 使用递归调用自身

findnum(34,a)

相关文章

网友评论

      本文标题:Python递归

      本文链接:https://www.haomeiwen.com/subject/kjuwbxtx.html