21.递归

递归

递归的概念：函数包含了对自身的调用，那么就是递归，函数运行会占用内存。
使用的场景：如果你发现你将要做的事情就是你现在做的，那么用递归
递归类似循环；在编写或阅读递归时，首先我们关注的是递归的终止条件

递归循环终止条件

##########33
def zhangan(index=0):
    if index < 100:    
        print('当前运行的此时',index)
        return zhangan(index+1)
    else:
        print('递归结束')
        return     1    
rt = zhangan()
print('返回值：',rt)

当前运行的此时 95
当前运行的此时 96
当前运行的此时 97
当前运行的此时 98
当前运行的此时 99
递归结束
返回值： 1

递归求和

在接触递归之前，我们先来做这么一个问题：如果说，要对一个数字列表求和（或者其他序列）求和，除了我们可以使用内置的sum函数，还有什么办法？
如果你还有更优秀的办法，可以在关于页面找到我的联系方式，有偿提交给我

while循环：
1 L = [1,2,3,4,5]
2 mysum = 0 #保存和的变量
3 while L: #将列表最为循环条件
4     mysum += L[0] #每次将列表第一个位置的值加到和中
5     L = L[1：] #去掉列表第一个元素

for循环：

1 L = [1,2,3,4,5]
2 mysum = 0
3 for var in L:
4     mysum += var

递归求和：

1 a = [1,2,3,4,5]
2 def zhangan(seq):
3     if not seq:  #空列表时递归终止返回值0
4         return 0
5     else:
6         return seq[0]+zhangan(seq[1:])
7          #在返回值中，我们返回了一个函数的调用，并且传递的参数为去掉当前列表第一个元素的新列表        
8 print(zhangan(a))

 1 a = [1,2,3,4,5]
 2 def get_sum(seq):
 3     if seq:  
 4         return seq[0] + get_sum(seq[1:])
 5     else:  #空列表时递归终止
 6         return 0
 7     #return seq[0] + get_sum(seq[1:]) if seq else 0 
 8 rt = get_sum(a)
 9 print(rt)
10 1#get_sum([1,2,3,4,5]): return 1 + get_sum([2,3,4,5])
11 2#get_sum([2,3,4,5])  : return 2 + get_sum([3,4,5])
12 3#get_sum([3,4,5])    : return 3 + get_sum([4,5])
13 4#get_sum([4,5])      : return 4 + get_sum([5])
14 5#get_sum([5])        : return 5 + get_sum([])
15 6#get([])             : return 0

递归处理非线性循环

递归还可以处理一些非线性循环，而普通的循环是无法处理的
比如这样一个列表对其求和：

L = [1,[2,[3,4],5],6,[7,8]]
由于这个列表不是一个线性迭代，包含着复杂的元素嵌套
普通的循环语句处理起来将会非常难以控制

 1 L = [1,[2,[3,4],5],6,[7,8]]
 2 sum = 0
 3 def mysum(L):
 4     global sum
 5     for var in L:
 6         if not isinstance(var,list):   
 7         #如果其中元素不为列表类型，则为一个确定的值
 8             sum += var
 9         else:
10             mysum(var)
11     return

第一种用global运算：

 1 mylist = [1,2,[3],5,[6,[7,8,9]],1,2] #-> 44
 2 #试一下用循环求和，
 3 #如果列表变化，那么代码可以兼容，可以直接复用，不能改变
 4 mysum = 0
 5 #for while 一层层的向下遍历
 6 
 7 def get_sum(iter):#接收一个等待求和的多层序列
 8     #iter 中 无非两种数据类型: list int
 9     global mysum
10     for var in iter:
11         if type(var) == int: #当前取出来的数据是int
12         #if type(var) == type([])
13             mysum += var
14         else:
15             get_sum(var) #遇到的又是一个列表，那么我们继续遍历
16     #for循环结束的时候，递归结束
17 get_sum(mylist)
18 print(mysum)
19 # get_sum([1,2,[3],5,[6,[7,8,9]],1,2])
20     #mysum += 1,2,5,1,2
21         # get_sum([3]) -> mysum += 3
22         # get_sum([6,[7,8,9]])
23             #mysum += 6
24             # get_sum([7,8,9])
25                 #mysum += 7,8,9

第二种用return返回值求和：

 1 a = [1,2,[1,2,3],5,[6,[6,7,8,9]],32,2] 
 2 def zhangan(a1):
 3     sum = 0     #每一次递归sum都为0
 4     for var in a1:
 5         if type(var) == int: 
 6             sum += var
 7         else:
 8             dsum = zhangan(var) #每一次list递归的结果
 9             sum = sum + dsum    #递归的结果值和不走递归的结果值加起来
10     return sum    #函数运行结果要返回    
11 rt=zhangan(a)
12 print(rt)

花钱递归

思考：假如你有10000块，每天花一半，毛钱直接舍弃，那么这钱可以花几天？

递归解决：

 1 money = 10000
 2 def zhangan(money,day=1):
 3     if money > 0:
 4         print('今天是第：%d天' % day)
 5         money1 = money // 2  #每次花一半
 6         print('还剩余：%d' % money1)
 7         day +=1     #花完天数+1
 8         return zhangan(money1,day)
 9     else:
10         return day
11 print(zhangan(money))

1 moeny = 10000
2 def func(moeny,day=0):
3     if moeny > 0:
4         func(moeny // 2,day+1)
5     else:
6         print(day)
7         return 0
8 func(moeny)

小猴子吃桃子递归：

 1 #小猴子吃桃子
 2 #100个桃子，每天吃一半加一个，什么时候不能按照这样的条件吃了。得花多少天
 3 
 4 peach_num = 100
 5 def eat_peach(peach_num,day = 1):
 6     print('今天是%d天' % day)
 7     print('现在还有%d个桃子' % (peach_num))
 8     eat_num = peach_num // 2 + 1
 9     peach_num = peach_num - eat_num
10     if peach_num > 0:
11         print('吃完了还剩下%d个桃子' % (peach_num))
12         day += 1
13         print('--------------')
14         return eat_peach(peach_num, day)
15     else:
16         return day
17 day = eat_peach(peach_num)
18 print(day)
19 
20 1#eat_peach(100,day = 1):
21 '''
22     eat_num = 51 要吃的
23     peach_num = 49 剩下的 >0
24     day = 1 当前的天数
25     return eat_peach(49, 2) 6
26 '''
27 2#eat_peach(49, 2)
28 '''
29     eat_num = 25 要吃的
30     peach_num = 24 剩下的 >0
31     day = 2 当前的天数
32     return eat_peach(24, 3)  6 
33 '''
34 3#eat_peach(24, 3)
35 '''
36     eat_num = 13 要吃的
37     peach_num = 11 剩下的 >0
38     day = 3 当前的天数
39     return eat_peach(11, 4)  6  
40 '''
41 4#eat_peach(11, 4)
42 '''
43     eat_num = 6 要吃的
44     peach_num = 5 剩下的 >0
45     day = 4 当前的天数
46     return eat_peach(5, 5) 6    
47 '''
48 5#eat_peach(5, 5)
49 '''
50     eat_num = 3 要吃的
51     peach_num = 2 剩下的 >0
52     day = 5 当前的天数
53     return eat_peach(2, 6)   6  
54 '''
55 6#eat_peach(2, 6)
56 '''
57     到了这一天，没法过了！
58     eat_num = 2 要吃的
59     peach_num = 0 剩下的 = 0
60     day = 6 当前的天数
61     return 6    
62 '''

 1 #小猴子吃桃子
 2 #100个桃子，每天吃一半加一个，什么时候不能按照这样的条件吃了。得花多少天
 3 taozi = 100
 4 def func(taozi,day=1):
 5     if taozi > 0:
 6         eat_num = taozi // 2 + 1
 7         sum_num = taozi - eat_num
 8         day +=1
 9         func(sum_num,day)
10     else:
11         print(day)
12         return 0
13 func(taozi)

统计每一个出现的字符出现的次数:

 1 mylist = ['asdazxc','adxzc',['12390145fcsdjfhzkjxcmnasd','123987189asjkdsajkb'],'asdqwewqerq',['asd890q8390'],'asdhquiweqysa','asdhjkzhxjkckjasdh']
 2 #把一样的提出来
 3 #统计每一个出现的字符出现的次数
 4 #for循环实现
 5 dict_num = {}
 6 #key:对应的字符
 7 #value:出现的次数
 8 def get_num(seq):
 9     #字典是可变数据类型，所以直接可以在函数作用域内进行修改
10     for var in seq: #遍历整个列表数据
11         if type(var) == list:
12             #如果取出来的还是一个列表，那么就继续递归
13             get_num(var)
14         else: #如果碰到的是一个字符串
15             for i in var:  #遍历字符串，记录次数
16                 if i in dict_num:
17                     # 如果获取到的字符，已经存在了字典中，那么他的次数+1
18                     dict_num[i] = dict_num[i] + 1
19                 else:
20                     # 如果获取到的字符没出现过，那么就创建默认值1就行
21                     dict_num[i] = 1
22 get_num(mylist)
23 for key in dict_num:
24     print(key,':',dict_num[key])

 1 mylist = ['asdazxc','adxzc',['12390145fcsdjfhzkjxcmnasd','123987189asjkdsajkb'],'asdqwewqerq',['asd890q8390'],'asdhquiweqysa','asdhjkzhxjkckjasdh']
 2 sum_dict = {}
 3 def func(seq):
 4     for var in seq:
 5         if type(var) == str:
 6             for i in var:
 7                 if sum_dict.get(i):
 8                     sum_dict[i] = sum_dict[i]+1
 9                 else:
10                     sum_dict[i] = 1
11         else:
12             func(var)
13 func(mylist)
14 print(sum_dict)

脚本模拟环境为现在很火的游戏病毒公司

　　1, 有一种高繁殖高传播(只限空气与水) 难治愈但不危机生命的病毒

　　2, 脚本测算它的传播速度

　　3, 假设一个城市有1000万人口日出生率与死亡率抵消后人口增长率为日10万分之一

　　4, 病毒最初只有一个,以每天一倍的速度繁殖

　　5, 每1万个病毒可以感染一个病人

　　　　计算多少天可以感染全市人.

import time
import os
def func(day,viruses,population):
    day += 1
    viruses += viruses
    population = round(population * 1.00001)
    if viruses // 10000 > population:
        print('

今天是第%s天,全市的人都可能会被感染,所以请在此时间前研究出疫苗' % day)
        return
    print('今天是第%s 天 , 有细菌 %s 个  人口 %s' % (day,viruses,population))
    time.sleep(1)
    os.system('cls')
    return func(day,viruses,population)
func(0,1,10000000)

递归注意事项

Python中，递归的最大上限次数差不多是1000次左右
一个没有终止条件的递归会引发错误(类似一个死循环)
这是因为递归的每一次函数执行*，都会在内存中产生新的函数副本，递归的内存消耗要大于普通循环；但是同样的，消耗了内存，效率高**于普通循环

 1 >>> def func():
 2 ...     return func()
 3 ...
 4 >>> func()
 5 Traceback (most recent call last):
 6   File "<stdin>", line 1, in <module>
 7   File "<stdin>", line 2, in func
 8   File "<stdin>", line 2, in func
 9   File "<stdin>", line 2, in func
10   [Previous line repeated 995 more times]
11 RecursionError: maximum recursion depth exceeded
12 #这里我们在995次递归之后，达到上线，从而报错

我们也可以手动干预递归的上限，但是这是有风险的，要结合计算机本身内存来考虑

1 >>> import sys
2 >>> sys.setrecursionlimit(num)

在这里，num即为你想控制修改的最大递归上限次数