Python之递归函数

Python之递归函数

好久没有更新内容了,也好久没有给大家打个招呼了,小白想死你们了。今天跟大家说说Python中的递归函数。

Python是支持递归函数的。简单地说,一个递归函数就是直接或间接地调用自身的函数,并且要有退出条件。枯燥的概念令人生厌,我们直接来个例子看看递归函数是如何工作的。例如我们对一个数字列表进行求和计算,我们可以使用内置的函数或者自己写一个函数来完成计算工作,接下来我们看看如何使用递归来完成求和运算:

In[1]:defmysum(L):

...:ifnotL:

...:return

...:else:

...:returnL[]+mysum(L[1:])

...:

In[2]:mysum([1,2,3,4,5])

Out[2]:15

如果对上面的函数较为困惑,可以使用函数来打印每次递归时列表的值:

In[3]:defmysum(L):

...:print(L)

...:ifnotL:

...:return

...:else:

...:returnL[]+mysum(L[1:])

...:

In[4]:mysum([1,2,3,4,5])

[1,2,3,4,5]

[2,3,4,5]

[3,4,5]

[4,5]

[5]

[]

Out[4]:15

通过上述的输出可以发现:每次递归时,列表的长度都变短了,直到列表变为空时,递归终止。对于上面的代码,我们可以使用另外一种代码形式来实现,也就是使用三目运算符,然而在Python中是没有三目运算符的,不过可以使用来实现,代码如下:

In[1]:defmysum(L):

...:returnifnotLelseL[]+mysum(L[1:])

...:

In[2]:mysum([1,2,3,4,5])

Out[2]:15

说到递归还有一个阶乘的例子要个大家说说:

In[5]:deffactorial(number):

...:ifnumber

...:return1

...:else:

...:returnnumber*factorial(number-1)

...:

In[6]:foriinrange(11):

...:print("! = ".format(i,factorial(i)))

...:

!=1

1!=1

2!=2

3!=6

4!=24

5!=120

6!=720

7!=5040

8!=40320

9!=362880

10!=3628800

如果计算,可以根据函数定义看到其计算过程:

===>factorial(5)

===>5*factorial(4)

===>5*(4*factorial(3))

===>5*(4*(3*factorial(2)))

===>5*(4*(3*(2*factorial(1))))

===>5*(4*(3*(2*1)))

===>5*(4*(3*2))

===>5*(4*6)

===>5*24

===>120

使用递归函数需要注意防止栈溢出。在计算机中,函数调用是通过栈(stack) 这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函 数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的 次数过多,会导致栈溢出。可以试试factorial(1000):

>>>factorial(1000)

Traceback(mostrecentcalllast):

File"",line1,in

File"",line4,infactorial

...

File"",line4,infactorial

RuntimeError:maximumrecursiondepthexceeded

使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。今天的内容就到这里,明天继续。

本文来自企鹅号 - 小白的技术客栈媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Petrichor的专栏

tensorflow编程: Variables

tf.moving_average_variables tf.global_variables_initializer tf.local_variabl...

1611
来自专栏androidBlog

归并排序 递归版和非递归版的实现(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

2851
来自专栏技术换美食换不换

块状链表

的复杂度,而如果将整个块状链表维护成有序的,它甚至可以实现平衡树的一些操作[1],毕竟平衡树也可以看作是一种维护序列的方法。 又因为块状链表只在每个分块记录一...

1142
来自专栏AILearning

一个面试题:截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串

一个面试题: 编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串。 但 是要保证汉字不被截半个,如“我ABC”4,应该截为“我AB”,...

2449
来自专栏进击的程序猿

Laravel之Pipeline1. 背景2. 基本操作3. 动手实现4. Laravel中Pipeline实现5. 总结

在Laravel中经常需要对一个对象,经过多个中间层处理后,才到真正处理的函数,Laravel将这种常用操作抽象出来,叫做Pipeline

792
来自专栏有趣的Python

慕课网-C++远征之继承篇(下)-学习笔记

C++远征之继承篇(下) 多继承与多重继承 多重继承: ? 多重继承 ? 多重继承-Is-a关系 class Person { }; class Soldie...

4469
来自专栏cs

串匹配算法

问题:给定二个字符串S和T,在主串S中查找子串T的过程称之为字符串匹配问题(string matching,也称之为模式匹配)。在文本处理系统,操作系统,编译系...

35210
来自专栏数据小魔方

左手用R右手Python系列之——数据框与apply向量运算

R语言与Python中的apply函数都有着丰富的应用场景,恰到好处的使用apply函数,可以避免在很多场景下书写冗余的代码,这不仅能提高代码可读性,而且提高代...

72911
来自专栏五分钟学算法

每天一算:Reverse Linked List

1521
来自专栏机器学习从入门到成神

字符串面试题(二)— 间隔字符串逆序

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1623

扫码关注云+社区

领取腾讯云代金券