认识递归

1、什么是递归函数：

                           在自身函数里调用自己，就是递归函数，python系统默认最大递归次数为998次，超过了这个次数会报如下错误（RecursionError: maximum recursion depth exceeded while calling a Python object），写递归时一定要写结束条件！！

 

1.1、递归的返回值：

               不要只看到return就认为已经返回了，要看返回操作是在递归到几层的时候发生的，然后返回给了谁
               如果不是返回给外层函数，调用者就接收不到
               需要再分析，看如何把结果返回回来

 

2、如何修改默认递归得次数：

                                        不建议修改，如果递归次数太多就不适合用递归来解决

import sys
sys.setrecursionlimit(10000)

3、递归得优缺点：

                             优点：会让代码变简单

                             缺点：占内存

一个递归计算年龄的例子及递归得运行过程

需求：

         求欧阳多大了

已知：欧阳比张三大两岁，

          张三比李四大两岁，

          李四比二麻子大两岁

          二麻子今年40了

递归得代码：求欧阳今年多大了：

def age(n):
    if n == 4:
        return 40
    elif n > 0 and n < 4:
        return age(n+1)+2
print(age(1))    #最终计算结果：46

上面得递归代码运行得过程：

第一次递归，执行函数时将1当实参传进来了
def age(1):
    if 1 == 4:
        return 40
    elif 1 > 0 and 1 < 4:
        return age(1+1)+2    #age（2+2    #44+2==46最终结果为：46
    
def age(2):
    if 2 == 4:
        return 40
    elif 2 > 0 and 2 < 4:
        return age(2+1)+2   #age(3)+2    #42+2==44
    
def age(3):
    if 3 == 4:
        return 40
    elif 3 > 0 and 3 < 4:
        return age(3+1)+2   #age(4)+2  #40+2==42
    
def age(4):
    if 4 == 4:       #n==4时
        return 40     #返回40
    elif 3 > 0 and 3 < 4:       #不符合这里得条件，一下代码不执行
        return age(3+1)+2

画图说明执行过程：

一个递归计算斐波那契数列的例子及递归的过程 

斐波那契数列说明（第一位和第二位都是1，以后的每个数字是前两个数字相加的合）：1，1，2，3，5，8，13，21，34，55，89

1、使用双调用的形式计算斐波那契数列
def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n-1) +fib(n-2)
print(fib(5))

1.1、递归方式

第一次递归的过程
def fib(5):
    if n == 1 or n == 2:              #向下递归              #向上预算结果
        return 1
    return fib(n-1) +fib(n-2)   #fib(5-1) + fib(5-2)    #3+2=5
print(fib(5))   #结果为5

第二次递归得过程
def fib(4):
    if n == 1 or n == 2:
        return 1
    return fib(n-1) +fib(n-2)   #fib(4-1) + fib(4-2)     #2+1=3
print(fib(4))    #结果为：3
def fib(3):
    if n == 1 or n == 2:
        return 1
    return fib(n-1) +fib(n-2)   #fib(3-1) + fib(3-2)    #1+1=2
print(fib(3))    #结果为：2

第三次递归的过程
def fib(3):
    if n == 1 or n == 2:
        return 1
    return fib(n-1) +fib(n-2)   #fib(3-1) + fib(3-2)     
print(fib(3))    
def fib(2):
    if n == 1 or n == 2:
        return 1       #返回1
    return fib(n-1) +fib(n-2)
print(fib(2))
def fib(1):
    if n == 1 or n == 2:
        return 1       #返回1
    return fib(n-1) +fib(n-2)
print(fib(1))

说明：双递归的方式计算斐波那契数列效率很慢，因为递归里设计到两次函数调用，每个函数每次调用都要重新计算一下，具体看下图详解

2、使用但调用的形式计算斐波那契数列

#一次调用计算斐波那契数列
def fib(n):
    if n == 2:
        return 1,1
    else:
        a,b = fib(n-1)
        print(a,b)
        return b,a+b
print(fib(4))          #结果为前一个数字和计算结果（不完美）

#修改后（只显示计算出的斐波那契数列 完美的）
def fib(n,l = [0]):
    l[0] +=1
    if n == 1 or n == 2:
        l[0] -= 1
        return 1,1
    else:
        a,b = fib(n-1)
        l[0] -= 1
        if l[0] == 0:
            return a+b
        return b,a+b
print(fib(4))

2.1、递归过程说明：

def fib(n):
    if n == 2:
        return 1,1
    else:
        a,b = fib(n-1)
        print(a,b)
        return b,a+b
print(fib(4))            #最终结果为（2，3）

#第一次递归
def fib(4):
    if 4 == 2:        #0、条件不成立
        return 1,1
    else:
        a,b = fib(4-1)     #1、4-1=3    #8、a=1,b=2
        return b,a+b     #9、返回值2，3
print(fib(4)) 

#第二次递归
def fib(4):
    if 4 == 2:        #2、条件不成立
        return 1,1
    else:
        a,b = fib(4-1)     #3、3-1=2    #6、a=1,b=1
        return b,a+b       #7、返回值1，2
print(fib(4)) 

#第三次递归
def fib(4):
    if 4 == 2:        #4、条件成立
        return 1,1    #5、返回1，1
    else:
        a,b = fib(4-1) 
        return b,a+b
print(fib(4))

算法

什么叫算法：计算的方法：人脑复杂，计算机简单
查找：找数据
排序：找最短路径

现在学习的算法都是过去式
了解基础的算法才能创造出更好的算法
不是所有的事情都能套用现成的方法解决的
有些时候用到学过的算法知识来解决新的问题

二分查找算法

二分查找算法，必须处理有序的列表

使用递归实现二分查找算法：
l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

def find(l,aim,start = 0,end = None):
    end = len(l) if end is None else end
    mid_index = (end - start) // 2 + start
    if start <= end:
        if l[mid_index] < aim:
            return find(l,aim,start = mid_index+1,end=end)
        elif l[mid_index] > aim:
            return find(l,aim,start=start,end=mid_index-1)
        else:
            return print(\'找到了，index为：%s\'%mid_index,)
    else:
        return \'找不到这个值...\'
ret = find(l,44)
print(ret)

递归实现的过程

#第一次递归
def find(l,aim,start = 0,end = None):
    end = len(l) if end is None else end        #end = len(l) -->25
    mid_index = (end - start) // 2 + start       #计算中间值 25 // 2 == 12 + 0 == 12
    if l[mid_index] < aim:         #12和目标作比较，12 < 44
        find(l,aim,start = mid_index+1,end=end)     #find (l,44,start=13,end=24)
    elif l[mid_index] > aim:
        find(l,aim,start=start,end=mid_index-1)
    else:
        print(\'找到了\',mid_index,aim)
find(l,44)

#第二次递归
def find(l,aim,start = 0,end = None):          #find(l,44,start = 13,end = 24)
    end = len(l) if end is None else end        #end 不等于空，所以end = 24
    mid_index = (end - start) // 2 + start       #计算中间值 (24 - 13) // 2 == 5 + 13 == 18
    if l[mid_index] < aim:         #18和目标作比较，l[18] == 67,67和44比较
        find(l,aim,start = mid_index+1,end=end)
    elif l[mid_index] > aim:         #67 > 44
        find(l,aim,start=start,end=mid_index-1)   #find (l,44,start=13,end=18 - 1)
    else:
        print(\'找到了\',mid_index,aim)

#第三次递归
def find(l,aim,start = 0,end = None):          #find(l,44,start = 13,end = 17)
    end = len(l) if end is None else end        #end 不等于空，所以end = 17
    mid_index = (end - start) // 2 + start       #计算中间值 (17 - 13) // 2 == 2 + 13 == 15
    if l[mid_index] < aim:         #15和目标作比较，l[15] == 55,55和44比较
        find(l,aim,start = mid_index+1,end=end)
    elif l[mid_index] > aim:         #55 > 44
        find(l,aim,start=start,end=mid_index-1)   #find (l,44,start=13,end=15 - 1)
    else:
        print(\'找到了\',mid_index,aim)

#第四次递归
def find(l,aim,start = 0,end = None):          #find(l,44,start = 13,end = 14)
    end = len(l) if end is None else end        #end 不等于空，所以end = 14
    mid_index = (end - start) // 2 + start       #计算中间值 (14 - 13) // 2 == 0 + 13 == 13
    if l[mid_index] < aim:         #13和目标作比较，l[13] == 42,42和44比较，42 <44
        find(l,aim,start = mid_index+1,end=end)   #find (l,44,start=14,end=14)
    elif l[mid_index] > aim:
        find(l,aim,start=start,end=mid_index-1)
    else:
        print(\'找到了\',mid_index,aim)

#第五次递归
def find(l,aim,start = 0,end = None):          #find(l,44,start = 14,end = 14)
    end = len(l) if end is None else end        #end 不等于空，所以end = 14
    mid_index = (end - start) // 2 + start       #计算中间值 (14 - 14) // 2 == 0 + 13 == 13
    if l[mid_index] < aim:         #13和目标作比较，l[13] == 42,42和44比较，42 <44
        find(l,aim,start = mid_index+1,end=end)   #find (l,44,start=15,end=14)          #start大于end时预示着找不到了
    elif l[mid_index] > aim:
        find(l,aim,start=start,end=mid_index-1)
    else:
        print(\'找到了\',mid_index,aim)

 

版权声明：本文为hei-ma原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/hei-ma/articles/9533077.html