一. 递归
1. 递归的定义: 在函数中调用函数本身, 就是递归.
- def func():
- print("我是真的好看!!!")
- func()
- func()
结果:
我是真的好看!!!
我是真的好看!!!
我是真的好看!!!
.......
在 python 中, 递归的最大深度是 1000, 但是不会到 1000, 在这之前就会给你报错.
- count = 1
- def func():
- global count
- print("我是真的好看!!!",count)
- count = count + 1
- func()
- func()
结果:
.......
我是真的好看!!! 997 #到 998 次就报错了
我是真的好看!!! 998 Traceback (most recent call last):
- File "E:/wanchengdezuoye / 复习 / 复习. py", line 1354, in <module>
- func()
遍历 D:/sylar 文件夹, 打印出所有的文件盒普通文件的文件名
- import os
- def func(filepath, n): # d:/sylar/
- # 1, 打开这个文件夹
- files = os.listdir(filepath)
- # 2. 拿到每一个文件名
- for file in files: # 文件名
- # 3. 获取到路径
- f_d = os.path.join(filepath, file) # d:/sylar / 文件名 /
- # 4. 判断是否是文件夹
- if os.path.isdir(f_d):
- # 5. 如果是文件夹. 继续再来一遍
- print("\t"*n, file,":") # 打印文件名
- func(f_d, n + 1)
- else: # 不是文件夹. 普通文件 递归出口, 最终在这里隐含着 return
- print("\t"*n, file)
- func("d:/sylar",0)
二. 二分法
定义: 二分查找, 每次能够排除掉一半的数据, 查找的效率很高, 但是必须是有序序列才可以使用二分法查找.
**** 要求: 查找的序列必须是有序序列 ******
- li = [22,33,44,55,66,77,88,99,105,126,236,345,564,888]
- n = 100
- left = 0 #左边的边界, 索引为 0
- right = len(li) - 1 #右边的边界, 列表中数据的数量 - 1 就是 888 的索引
- count = 1
- while left <= right: #当数据 n 在列表中, 左边小于右边, 否则当交叉的时候, 说明不在列表中
- mid = (left + right) // 2 #求中间值
- if li[mid]> n: #当列表的中间索引的值大于 n 时, 砍掉右面的
- right = mid - 1 #中间索引项左面移动一个, 变成右边的边界
- if li[mid] <n:
- left = mid + 1
- if li[mid] == n:
- print("在列表中")
- print(count)
- break
- count = count + 1
- else:
- print("不在列表中")
结果:
不在列表中
使用递归版二分法
- li = [22,33,44,55,66,77,88,99,105,126,236,345,564,888]
- def func(n,left,right):
- if left <= right: #边界
- mid = (left + right) // 2
- if n> li[mid]:
- left = mid + 1
- return func(n,left,right) #递归, 递归的入口
- if n < li[mid]:
- right = mid - 1
- return func(n,left,right) #深坑: 函数的返回值返回给函数, 要多吃调用
- if n == li[mid]:
- print("找到了")
- return mid #返回找到的数在列表中的位置
- else:
- print("没有") #递归的出口
- return -1 #没有找到, 返回 - 1,return 什么都不加, 返回 None
- ret = func(88,0,len(li)-1)
- print(ret)
结果:
找到了
6
来源: http://www.bubuko.com/infodetail-2729057.html