递归

雨点打透心脏的1/2处 2022-02-19 05:39 327阅读 0赞

# 递归Recursion #

*  递归要求
    
    1.  递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用
    2.  递归调用的深度不宜过深
        
         *  python对递归调用的深度做了限制，以保护解释器
         *  超过递归深度显示，抛出RecursionError:maxinum recursion depth exceeded超出最大深度
         *  sys.getrecursionLimit() 可以查看当前解析器栈的最大深度
 *  简单递归示例：

1.  求n的阶乘

#第一种实现
    def factorial(n):
        return n if n==1 else n*factorial(n-1)
    
    #第二种实现
    def factorial2(n,face=1):
        if n==1:
            return face
        else:
            return factorial2(n-1,n*face)
    print(factorial(5),factorial2(5))

1.  将一个数逆序放入列表中，例如1234 ==》 \[4,3,2,1\]

#思路一，取模递归调用
    def numtolist(num,arr = []):
        if num<10:
            arr.append(num)
        else:
            arr.append(num%10)
            numtolist(num//10)
        return arr
    
    #思路二 利用列表的加法，保存返回值
    def numtolist2(num):
        if num<10:
            return [num]
        else:
            return [num%10] + numtolist2(num//10)
    
    #思路三： 使用str类型递归实现
    def numtolist3(num,arr = []):
        if isinstance(num,int):
            num = str(num)
        if len(num)==1:
            arr.append(int(num))
            return
        else:
            arr.append(int(num[-1]))
            numtolist3(num[:-1])
        return arr
    #思路四，参数限定为一个
    def numtolist4(num):
        if isinstance(num,int):
            num = str(num)
        if len(num)==1:
            return [int(num)]
        else:
            return [int(num[-1])] + numtolist4(num[:-1])
        
    #思路五，使用闭包
    def numtolist5(num):
        arr = []
        def numto(num):
            if num<10:
                arr.append(num)
            else:
                arr.append(num%10)
                numto(num//10)
        numto(num)
        return arr
    
    #思路六 使用devmod
    def numtolist6(num):
        if num<10:
            return [num]
        else:
            tmp = divmod(num,10)
            return [tmp[1]] + numtolist6(tmp[0])
            
    print(numtolist(123),numtolist2(123),numtolist3(123),numtolist4(123),numtolist5(123),numtolist6(123),sep="\n")

1.  解决猴子吃桃问题
    
     *  猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想吃时，只剩下一个桃子了。求第一天共摘多少个桃子

#思路一
    def ectpeach(day,num):
        print("第{}天有{}个桃子".format(day,num))
        return num if day==1 else ectpeach(day-1,(num+1)*2)
    #思路二
    def ectpeach2(day):
        return 1 if day==1 else (ectpeach2(day-1)+1)*2
    print(ectpeach(10,1),ectpeach2(10))

*  递归总结
    
     *  递归是一种很自然的表达，复合逻辑思维
     *  递归相对运行效率低，每一次调用函数都要开辟栈帧
     *  递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就会溢出
     *  如果是有线次数的递归，可以使用递归调用，或者使用循环代替，循环代码稍微复杂些，但是只要不是死循环，可以多次迭代直至算出结果
     *  即使递归代码很简洁，但是能不用则不用递归