Python_递归

递归：一种直接直接或者间接调用自身算法的过程

递归在调用的过程中，是在上一层循环还没有结束直接进入下一层，多层嵌套调用实现调用

例1：

 1 def func(n):
 2     print(n)
 3     if n > 1:
 4         t = func(n / 2)
 5         print('t', t)                        # 当循环结束，会一层一层退出循环，退出一层打印一层
 6     else:
 7         print('已经是最小了')
 8     print('n', n)                             
 9     return n                                # 返回n 用于观察 t 退出循环
10 func(100)

num

结果：

100
50.0
25.0
12.5
6.25
3.125
1.5625
0.78125
已经是最小了
n 0.78125
t 0.78125
n 1.5625
t 1.5625
n 3.125
t 3.125
n 6.25
t 6.25
n 12.5
t 12.5
n 25.0
t 25.0
n 50.0
t 50.0
n 100

result

例2：裴波那契数列：（用递归实现）（0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987）

1 def num(x, y, stop):
2     if x+y < stop:                    # 递归数列结束值，如果没有条件限制会直接报错
3                                             # 因为过度的递归会造成栈溢出
4         z = x + y
5         print(z)
6         num(y, z, stop)
7 num(0, 1, 1000) 

num

结果：

1
2
3
5
8
13
21
34
55
89
144
233
377
610
987

result

 二分算法：

 1 def binary(binary_para, search):
 2     bi = int(len(binary_para)/2)             # 分为两部分 bi 为下标
 3     if search == binary_para[0]:             # 判断传入数是否为第一个
 4         print('列表里存在，并且这是列表第一个数: %s' % search)
 5     elif len(binary_para) > 1:                  # 利用递归不断二分
 6         if binary_para[bi] > search:
 7             print('分段值(前）：', binary_para[bi])              # 打印分段的值
 8             binary(binary_para[:bi], search)
 9         elif binary_para[bi] < search:
10             print('分段值（后）：', binary_para[bi])
11             binary(binary_para[bi:], search)
12         else:
13             print('你找到了，列表里有这个数！！')
14 
15     else:
16         print('这个列表里 没有 这个数！！')
17 
18 
19 if __name__ == '__main__':             # 在自己.py文件里，可以运行，其他文件访问不运行此方法
20     size = list(range(4, 300000, 10))         # 区间（4,300000）间断10个数的列表
21     # binary(size， 1)
22     binary(size, 12138)

binary

结果：

分段值(前）： 150004
分段值(前）： 75004
分段值(前）： 37504
分段值(前）： 18754
分段值（后）： 9374
分段值(前）： 14064
分段值（后）： 11714
分段值(前）： 12884
分段值(前）： 12294
分段值（后）： 12004
分段值(前）： 12144
分段值（后）： 12074
分段值（后）： 12104
分段值（后）： 12124
分段值（后）： 12134
这个列表里 没有 这个数！！

result