一、递归

  • mac上的python最大递归深度997次，但python官方文档上的最大递归深度是1000
  1. def func(count):
  2.     print("递归第%d" % count)
  3.     func(count+1)
  4. func(1)
  5. # 结果是：
  6. ......
  7. 递归第994次
  8. 递归第995次
  9. 递归第996次
  10. [Previous line repeated 993 more times]
  11.   File "/Volumes/workspace/python-study/re_st/递归与二分查找.py", line 2, in func
  12.     print("递归")
  13. RecursionError: maximum recursion depth exceeded while calling a Python object
  • 设置最大的递归深度
  1. import sys
  2. sys.setrecursionlimit(10000)
  3. # 可以设置递归深度，但是程序不一定能跑到

二、利用递归和os模块遍历所有的文件和文件夹

  1. import os
  2. # 树结构、遍历树结构
  3. filepath = '/Volumes/workspace'
  4. def read(filepath, n):
  5.     # 设置递归深度n
  6.     l = os.listdir(filepath)
  7.     # # os.listdir()查看的是当前路径下的文件夹列表，这一点非常重要，拿到路径后第一步就是获取列表
  8.   # 并且这一步必须放在函数内反复调用
  9.     # print(l.__iter__())
  10.     # # 列表
  11.     # print('__iter__' in dir(l))
  12.     # # 是可迭代的
  13.     # print('__next__' in dir(l))
  14.     # 但不是迭代器
  15.     for file in l:
  16.         if os.path.isdir(os.path.join(filepath, file)) and '.' not in file: 
  17.         # 判断是文件夹还是文件并且不是点号开头的文件夹
  18.     # os.path.join(filepath, file)拼接上一层文件路径和当前的文件夹名，形成当前文件夹的路径
  19.             print('\t'*n, file)
  20.             # 根据深度和制表符来控制缩进，显示文件夹之间的层次关系
  21.             # 打印文件夹的名字，
  22.             read(os.path.join(filepath, file), n + 1)# 递归的入口
  23.             # 如果是文件夹，再次循环是深度加1
  24.         else:
  25.             print('\t'*n, file) # 递归的出口
  26.             # 根据深度和制表符来控制缩进，显示文件与文件夹之间的层次关系
  28. read(filepath, 0)
  29. # 递归深度为0

三、二分查找法

  1. '''二分查找'''
  2. # # 二分查找的前提必须是被查找的对象是有序的
  3. l = [1,2,4,42,2,23,35,32,5,4,3,3256,23,233254,32, 312242, 132132,123, 213]
  4. s = set(l)
  5. l = list(s)
  6. l = sorted(l, key=lambda x : x, reverse=False)
  7. # key对应的函数返回的值应该是排序依据的内容的值，sorted()函数会对这些返回值来排序，
  8. # 在根据返回值的顺序排列整个对象的顺序
  9. # 去重
  10. print(l)
  11. '''方法一:while True无限循环'''
  12. # count = 1
  13. # n = 4
  14. # left = 0
  15. # right = len(l) - 1
  16. # while left <= right:
  17. #     middle = (left + right) // 2
  18. #     # 查找中间位置，必须用//，确保是整数值
  19. #     if n < l[middle]:
  20. #         right = middle - 1
  21. #         # 如果查找的值小于中间位置的值，那么值在左边，把right变成middle-1
  22. #     elif n > l[middle]:
  23. #         left = middle + 1
  24. #         # 如果查找的值大于中间位置的值，那么值在右边，把left变成middle+1
  25. #     else:
  26. #         print(count)
  27. #         print('查找%d后找到，位置在%d' % (count,middle))
  28. #         break
  29. #         # 如果整好等于中间位置的值，输出索引值，并退出程序
  30. #     count += 1
  31. # else:
  32. #     print('查找目标不在对象里')
  33. # # 循环结束还未找到，那么目标不在查找的对象里
  35. '''方法二:迭代'''
  37. def func(left, right, n, count):
  38.     if right >= left:
  39.         # 必须规定right >= left，等于时候说明只有一个元素，反之则查找失败
  40.         middle = (left + right) // 2
  41.         if n < l[middle]:
  42.             right = middle - 1
  43.         elif n > l[middle]:
  44.             left = middle + 1
  45.         elif n == l[middle]:
  46.             print ('查找%d次，找到位置在%d' % (count, middle))
  47.             return '查找成功'
  48.         count += 1
  49.         return func(left, right, n,count)
  50.     else:
  51.         return -1
  52.         # 列表中都是数字，在查找不到的时候返回数字-1，表示找不到，比较规范
  53. print(func(0, len(l) - 1, 2, 1))
  54. # 利用递归来实现二分法查找，上边的程序必须在递归之前先进行判断，要查找的值是否在
  55. # 查找对象中，不存在直接返回失败，这个程序必须有，没有的话值又不在对象中，系统会报
  56. # 超过最大递归深度的错误。