大佬教程收集整理的这篇文章主要介绍了08.python 函数执行流程、函数递归,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
C语言中,函数的活动和栈有关。 栈是后进先出的数据结构。栈是由底端向顶端生长,栈顶加入数据称为压栈、入栈,栈顶弹出数据称为出栈。
def add(x, y):
r = x + y
print(r)
return r
def main():
a = 1
b = add(a, 2)
return b
main()
问题:如果再次调用main函数,和刚才的main函数调用,有什么关系?
每一次函数调用都会创建一个独立的栈帧入栈。 因此,可以得到这样一句不准确的话:哪怕是同一个函数两次调用,每一次调用都是独立的,这两次调用没什么关系。
斐波那契数列Fibonacci number:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式::F(n)=F(n-1)+F(n-2) 有F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)
# 循环实现
def fib_v1(n): # n>=3
a = b = 1
for i in range(n-2):
a, b = b, a + b
return b
fib_v1(101)
fib_v1(35)
使用递归实现,需要使用上面的递推公式
# 递归
def fib_v2(n):
if n < 3:
return 1
return fib_v2(n-1) + fib_v2(n-2)
# 递归
def fib_v2(n):
return 1 if n < 3 else fib_v2(n-1) + fib_v2(n-2)
fib_v2(35) # 9227465
递归实现很美,但是执行fib(35)就已经非常慢了,为什么? 以fib(5)为例。看了下图后,fib(6)是怎样计算的呢?
![iShot2022-01-12 15.26.51](/Users/apple/Downloads/iShot2022-01-12 15.26.51.png)
这个函数进行了大量的重复计算,所以慢。
使用时间差或者%%timeit来测试一下这两个版本斐波那契数列的效率。很明显循环版效率高。 难道递归函数实现,就意味着效率低吗? 能否改进一下fib_v2函数?
# 递归
def fib_v3(n, a=1, b=1):
if n < 3:
return b
a, b = b, a + b
#print(n, a, b)
return fib_v3(n-1, a, b) # 函数调用次数就成了循环次数,将上次的计算结果代入下次函
数调用
fib_v3(101) # fib_v3(35)
# 提示:用fib_v3(3)代入思考递归后计算了几次
思考时,也比较简单,思考fib_v3(3)来编写递归版本代码。 经过比较,发现fib_v3性能不错,和fib_v1循环版接近。但是递归函数有深度限制,函数调用开销较大。
def foo1():
foo2()
def foo2():
foo1()
foo1()
间接递归调用,是函数通过别的函数调用了自己,这一样是递归。 只要是递归调用,不管是直接还是间接,都要注意边界返回问题。但是间接递归调用有时候是非常不明显,代码调用复杂时,很难发现出现了递归调用,这是非常危险的。 所有,使用良好的代码规范来避免这种递归的发生。
#方式一
def factorial(n):
s=1
for i in range(2,n+1):
s*=i
return s
#方式二
def factorial(n):
s=1
for i in range(n,1,-1):
s*=i
return s
#方式三
def factorial(n,p=1):
if n==1:
return p
else:
return factorial(n-1,p*n)
#方式四
def factorial(n):
if n<2:
return 1
return factorial(n-1) *n
猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想吃时,只剩下一个桃子了。求第一天共摘多少个桃子
#循环实现
peach = 1
days = 9
for i in range(days):
peach=2 * (peach+1)
print(peach)
#递归实现
def fn(days=9,peach=1):
peach=2*(peach+1)
if days==1:
return peach
return fn(days-1,peach)
print(fn())
#方式三
def peach(days=10):
if days==1:
return 1
return 2 *(peach(day-1)+1)
print(peach())
以上是大佬教程为你收集整理的08.python 函数执行流程、函数递归全部内容,希望文章能够帮你解决08.python 函数执行流程、函数递归所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。