先来看一下函数的执行流程:
http://pythontutor.com/visualize.html#mode=edit #这个网站可以帮到你;
def foo1(b, b1=3)
print("foo1 called", b, b1)
def foo2(c):
foo3(c)
print("foo2 called", c)
def foo3(d):
print("foo3 called", d)
def main():
print("main called")
foo1(100, 101)
foo2(200)
print("main ending")
main()
全局帧中生成foo1,foo2,foo3,main函数对象;
main函数调用;查找内建函数print压栈,将常量字符串压栈,调用函数,执行完成后弹出栈顶;
main中全局查找函数foo1压栈,将常量100,101压栈,调用函数foo1,创建栈帧,print函数压栈,字符串和变量b,b1压栈,调用函数,执行完成后弹出栈顶;
main中全局查找foo2函数压栈,讲常量200压栈,调用foo2,创建栈帧,foo3函数压栈,变量c引用压栈,调用foo3,创建栈帧,foo3完成print函数调用完成后弹出;foo2恢复调用,print执行完成后弹出栈顶;main中foo2调用结束弹出栈顶;main继续执行print函数调用,弹出栈顶,main函数返回;
简单说下我的理解:
函数嵌套时,外层函数调用压栈,在调用内层函数时压栈外层函数的进度,创建新的栈帧,后续依然,执行完成以后一层一层弹出;
递归函数
函数直接或间接调用自身就是递归;
递归需要有退出条件;
递归调用深度不宜过深,python对递归调用深度做了限制,默认是1000,超过递归深度限制,抛出:RecursionError: maxinum recursion depth exceeded
可以通过sys模块下的sys.getrecursionlimit()来更改;
递归调用对比:
import datetime
# Fib Seq
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
n = 35
# loop
for i in range(n-1):
pre, cur = cur, pre + cur
print(cur, end=' ')
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
# Fib Seq
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
# recursion
def fib1(n, pre=0,cur=1):
pre, cur = cur, pre + cur
print(cur, end=' ')
if n == 2:
return
fib1(n-1, pre, cur)
fib1(n)
delta = (datetime.datetime.now() - start
).total_seconds()
print(delta)
start = datetime.datetime.now()
def fib2(n):
if n < 2:
return 1
return fib2(n-1) + fib2(n-2)
for i in range(n):
print(fib2(i), end=' ')
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
递归性能(菲波那切数列):
递归:
import datetime
n = 35
start = datetime.datetime.now()
def fib(n):
return 1 if n < 2 else fib(n-1) + fib(n-2)
for i in range(n):
print(fib(i), end=' ')
delta = (datetime.datetime.now() -start).total_seconds()
print(delta)
for循环:
import datetime
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
n = 35
for i in range(n-1):
pre, cur = cur, pre + cur
print(cur, end=' ')
delta = (datetime.datetime.now() -start).total_seconds()
print(delta)
递归改进:
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
def fib(n, pre=0,cur=1): # recursion
pre, cur = cur, pre + cur
print(cur, end=' ')
if n == 2:
return
fib(n-1, pre, cur)
fib(n)
#fib函数和循环的思想类似,参数n是边界条件,用n来计算;上一次的计算结果直接作为函数实参.和循环比较,性能相近;
递归练习:
求n的阶乘
n = 10
def fac(n):
if n == 1:
return 1
return n * fac(n-1)
print(fac(n))
n = 10
def fac1(n,p = 1):
if n == 1:
return p
p *= n
#print(p)
fac1(n-1,p)
return p
print(fac1(n))
n = 10
def fac2(n,m = None):
if m is None:
m = [1]
if n == 1:
return m[0]
m[0] *= n
#print(m[0])
fac2(n-1, m)
return m
print(fac2(n))
将一个数逆序放入列表中,例如123=>[4,3,2,1]
def revert(x):
if x == -1:
return ''
return data[x] + revert(x-1)
print(revert(len(data)-1))
def revert(n,lst=None):
if lst is None:
lst = []
x,y = divmod(n,10)
lst.append(y)
if x == 0:
return lst
return revert(x,lst)
print(revert(12345))
num = 123456
def revert(num,target=[]):
if num:
target.append(num[len(num)-1]) #target.append(num[-1:])
revert(num[:len(num)-1])
return target
print(revert(str(num)))
猴子吃桃:猴子第一天摘下若干个桃子,当即吃了一半,不过瘾,又多吃了一个,第二天早上又将剩下的桃子吃掉一半,又多吃一个,以后每天早上都吃前一天剩下的一半零一个,第十天时,只剩下一个桃子,问第一天一共摘下多少个桃子
假设猴子摘了x个桃子
d1 x//2 -1
d2 d1//2 -1
d3 d2//2 -1
...
d9 d8//2 -1
d10 = 1
def peach(days = 1):
if days == 10:
return 1
return (peach(days+1)+1)*2
print(peach())
def peach(days = 10):
if days == 1:
return 1
return (peach(days - 1)+1)*2
print(peach())
匿名函数:
匿名函数即没有名字的函数,python借助lambda表达式构建匿名函数;
格式:
lambda 参数列表: 表达式
lambda x : x ** 2
(lambda x : x ** 2)(4) #调用
foo = lambda x : x ** 2 #不推荐这么用
匿名函数参数列表不需要小括号;冒号用来分割参数列表和表达式;不需要使用return,表达式的值,就是匿名函数的返回值;lambda表达式(匿名函数)只能写在一行上,被称为单行函数,主要用于高阶函数传参数,可以简化代码;
print((lambda :0)())
print((lambda x, y=3: x + y)(5))
print((lambda x, y=3: x + y)(5, 6))
print((lambda x, *, y=30: x + y)(5))
print((lambda x, *, y=30: x + y)(5, y=10))
print((lambda *args: (x for x in args))(*range(5)))
print((lambda *args: [x+1 for x in args])(*range(5)))
print((lambda *args: {x+2 for x in args})(*range(5)))
[x for x in (lambda *args: map(lambda x: x+1, args))(*range(5))] # 高阶函数
[x for x in (lambda *args: map(lambda x: (x+1,args), args))(*range(5))]