生成器
- 自定义的迭代器
- yield关键字: 和return一样,接收值,但不终止函数
def func():
print('from 1')
yield 1
print('form 2')
yield
return 1
func调用之后变成了一个迭代器,yield默认返回None
g = func()
print(g.__next__())
print(g.__next__())
from 1
1
form 2
None
def func():
print('from 1')
yield 1,2
print('from 2')
yield ['a',1,2],2
g = func()
for k,v in g:
print(k,v)
from 1
1 2
from 2
['a', 1, 2] 2
有关yield的理解
一个带有yield的函数，加上括号就是一个生成器，它和普通函数不同，生成生成器时看上去像是调用，但不会执行任何函数代码，直到对其调用next()（在for循环中会自动调用next()） 才开始执行。
虽然执行流程仍按函数的流程执行，但每执行到一个yield语句就会中断，并且返回一个迭代值，下次执行时则从yield的下一个语句继续执行。看上去就像是一个函数在正常执行过程中被yield切割了数次，每次中断都会运行那一段的代码，并且通过yield返回当前的迭代值
yield的好处是把一个函数改写成了一个生成器，就获得了迭代能力，比起用类的实例保存状态来计算下一个next()的值,不仅代码简洁，而且执行流程异常清晰.
而当函数执行结束时，生成器会自动抛出StopIteration 异常，表示迭代完成。在for循环里，无须处理StopIteration 异常，循环会正常结束。
所以有点就是利用迭代，减少内存消耗，让代码更整洁。
在一个 generator function 中，如果没有 return，则默认执行至函数完毕，如果在执行过程中 return，则直接抛出 StopIteration 终止迭代。
实现range()函数
def range(end, start=0, step=1):
count = start
while count < end:
yield count
count += step
g = range(10)
print(g.__next__())
print(g.__next__())
print(g.__next__())
0
1
2
更完善的写法
def range(*args):
start = 0
step = 1
if len(args) == 1:
end = args[0]
elif len(args) == 2:
start = args[0]
end = args[1]
elif len(args) == 3:
start = args[0]
end = args[1]
step = args[2]
else:
raise ('传错了')
count = start
while count<end:
yield count
count += step
g = range(2,10,2)
print(g.__next__())
print(g.__next__())
print(g.__next__())
2
4
6
生成器表达式
tup = (i for i in range(5)) # 生成了一个老母鸡
print(tup.__next__())
for i in tup:
print(i)
0
1
2
3
4
lis = [i for i in range(5)] # 生成了一筐鸡蛋
print(lis)
[0, 1, 2, 3, 4]
递归
- 函数自己调用自己,类似于循环,但这个循环必须有结束条件
思考
def guess_age(count):
count -= 1
if count == 1:
return 26
return guess_age(count)+2
res = guess_age(5)
print(res)
32
斐波那契额
def feib(n):
if n <= 0:
return None
if n == 1 or n == 2:
return 1
else:
return feib(n-1) + feib(n-2)
print(feib(10))
55
汉诺塔
def han(n, a, b, c):
if n <= 0:
return None
if n == 1:
print (a,'-->', c)
else:
han(n-1, a, c, b)
han(1, a, b, c)
han(n-1, b, a, c)
han(3, 'a', 'b', 'c')
a --> c
a --> b
c --> b
a --> c
b --> a
b --> c
a --> c
二分法
- 这种写法是比较通用的，使用
in来进行筛选，把第一个值进行比对。 - 如果是排序好的数列的话，也可以取列表中间的索引的值，使用
值的大小来比对
lis = [i for i in range(1000000)]
num = 789433
def erfen(lis, num):
time = len(lis) // 2
if lis[0] == num:
print('找到了')
return None
if num in lis[:time]:
lis = lis[:time]
erfen(lis, num)
elif num in lis[time:]:
lis = lis[time:]
erfen(lis, num)
else:
print('找不到')
erfen(lis, num)
找到了