Python实现，递归算法，深度优先、广度优先
其实递归说白了就是循环本身函数，只不过下次循环的输入值是上次循环的结果值。关于递归算法，我经常把它用在搜索、计算中。我们来看一个简单的例子：
计算Demo
'要实现1，3，7，15，31''有如下数列，请问第7位是多少 --> 127 ' #普通写法 def simple(time): '''如上可以看出规则为 1 * 2 + 1 ''' '''此时如果硬写代码会比较繁琐，''' time -= 1 for i in range(time): if i == 0: factor = (0 * 2 + 1) val = factor * 2 + 1 factor = val return factor print(f'硬写:{simple(7)}') #递归算法 def loop(time, n=1, factor=0): val = factor * 2 + 1 if n == time: return val return loop(time, n + 1, val) print(f'递归:{loop(7)}')
从上述代码中可以看到，用递归计算真的是非常方便了。虽然是个很简单的例子，但是也可以看出来递归算法节省了很多代码并且逻辑也是非常清晰。对于我们Python来讲，简洁、明了的代码才是最好的代码，所以力荐！！！
搜索Demo（深度优先、广度优先）
关于递归算法， 上面的例子以及充分展示了，不再多说。下面讲一下在递归中经常用到的搜索方法。
深度优先：
广度优先：
'''搜索''' lis= [('文件1','文件5','文件8','文件21'), ('文件12','文件4','文件2','文件34'), ('文件18','文件10','文件9','文件16')] '''这里以搜索文件举例，如上有三层：深度优先搜索指的是由 0.0->0.1->0.2 -> 1.0->1.1->1.2 #广度优先搜索指的是由 0.0->1.0->2.0 -> 0.1->1.1->2.1'''
无论都是通过遍历而来，只不过遍历的时候给出了方向而已。
看一个简单的例子
'''搜索''' lis = [('文件1', '文件5', '文件8', '文件21'), ('文件12', '文件4', '文件2', '文件34'), ('文件18', '文件10', '文件9', '文件16')] # 假如我们要找'文件2' # 深度优先： 文件1->文件5 frequency = 0 for tup_index in range(len(lis)): # 得到lis总长度，通过索引遍历 for k in range(len(lis[tup_index])): frequency += 1 if lis[tup_index][k] == '文件2': print(f'找到了,位置是{tup_index, k},共查找{frequency}次') # 广度优先： 文件1->文件12 import numpy as np frequency = 0 lis = np.transpose(lis) # 转置一下 ''' [['文件1' '文件12' '文件18'] ['文件5' '文件4' '文件10'] ['文件8' '文件2' '文件9']]''' for tup_index in range(len(lis)): # 得到lis总长度，通过索引遍历 for k in range(len(lis[tup_index])): frequency += 1 if lis[tup_index][k] == '文件2': '''因为我们转置了，所以得出来的位置 2,1 需要对调为 1,2''' print(f'找到了,位置是{k, tup_index},共查找{frequency}次')
这两种方法视实际情况而用，无所谓好坏。也可以结合使用。如下：
[('文件1','文件5','文件8','文件21'), ('文件12','文件4','文件2','文件34'), ('文件18','文件10','文件9','文件16')] 问：请找到'文件2'！ 已知: '文件2' 在 '文件12' 之后且'文件12'在第一层。 答：可以先利用广度优先找到'文件12'，需2步，找到之后再用深度优先往下找，需2步，总共4步找到 '文件2'。
好啦，到此递归算法的使用也就差不多啦。
