2025年Python从放弃到入门——递归函数recur

科技前沿 • 2025-02-26 11:24 • 阅读 44

大家好，我是讯享网，很高兴认识大家。

简介

在一个函数体内，可以调用其他函数。
如果一个函数的函数体内调用了该函数本身，该函数就是递归函数。
递归函数必须要有明确的递归结束条件，也称为递归出口。
用递归解决的问题必须满足两个条件：
1.可以通过递归调用来缩小问题的规模，且新问题和原问题有着相同的形式。
2.递归可以在满足一定的条件后退出。

计算阶乘就是一个典型的例子。

def fact(n): if n==1: return 1 return n*fact(n-1) print('fact(6)=',fact(6)) fact(6)= 720

讯享网

在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

讯享网print('fact(1000)=',fact(1000)) RecursionError: maximum recursion depth exceeded in comparison

递归与循环

先来看一个计算列表元素和的例子。

def mysum(L): if not L: return 0 else: return L[0]+mysum(L[1:]) L=[1,2,3,4,5] print(mysum(L)) 15

理论上，所有的递归函数都可以写成循环的方式。

讯享网

讯享网sum=0 while L: sum+=L[0] L=L[1:] print(sum) 15

然而，如果L=[1,[2,[3,4],5],6,[7,8]] ，显然简单的循环语句不起作用，可以用递归来应对这种一般性的嵌套。isinstance用来做数据类型判断。

L=[1,[2,[3,4],5],6,[7,8]] def sumtree(L): tot=0 for x in L: if not isinstance(x,list): tot+=x else: tot+=sumtree(x) return tot print(sumtree(L)) 36

队列和栈

递归调用内部，Python通过在每一次递归调用时把信息压入调用栈（stack）顶来实现递归，因此它记住了在什么地方返回以及在什么地方稍后继续。

让我们不使用递归而实现递归风格的过程式编程来显式地追踪步骤。
先进先出队列

讯享网L=[1,[2,[3,4],5],6,[7,8]] def sumtree1(L): tot=0 items=list(L) while items: front=items.pop(0) if not isinstance(front,list): tot+=front else: items.extend(front) #将pop出的元素放到列表后面 return tot print(sumtree1(L)) 36

后进先出栈

def sumtree2(L): tot=0 items=list(L) while items: front=items.pop(0) if not isinstance(front,list): tot+=front else: items[:0]=front #将pop出的元素放到列表前面 return tot print(sumtree2(L)) 36

2025年Python从放弃到入门——递归函数recur

简介

递归与循环

队列和栈

相关推荐