Python之递归函数

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

Python是支持递归函数的。简单地说,一个递归函数就是直接或间接地调用自身的函数,并且要有退出条件。枯燥的概念令人生厌,我们直接来个例子看看递归函数是如何工作的。

例如我们对一个数字列表进行求和计算,我们可以使用内置的sum函数或者自己写一个函数来完成计算工作,接下来我们看看如何使用递归来完成求和运算:

In[1]: def mysum(L):
  ...:    if not L:
  ...:        return 0
  ...:    else:
  ...:        return L[0] + mysum(L[1:])
  ...:    

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

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

In[3]: def mysum(L):
  ...:    print(L)
  ...:    if not L:
  ...:        return 0
  ...:    else:
  ...:        return L[0] + 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中是没有三目运算符的,不过可以使用if/else来实现,代码如下:

In[1]: def mysum(L):
  ...:    return 0 if not L else L[0] + mysum(L[1:])
  ...: 

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

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

In[5]: def factorial(number):
  ...:    if number <=1:
  ...:        return 1
  ...:    else:
  ...:        return number * factorial(number-1)
  ...:    

In[6]: for i in range(11):
  ...:    print("{0:2}! = {1}".format(i, factorial(i)))
  ...:    
 0! = 1
 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 6! = 720
 7! = 5040
 8! = 40320
 9! = 362880
10! = 3628800

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

===> 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 (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in factorial
  ...
  File "<stdin>", line 4, in factorial
RuntimeError: maximum recursion depth exceeded

使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。

今天的内容就到这里,明天继续。

本文分享自微信公众号 - 小白的技术客栈(XBDJSKZ)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-12-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 或许,这会是全民皆知的一门编程语言

    不久前,国务院印发了《新一代人工智能发展规划》,其中明确指出,要实施全民智能教育项目,在中小学阶段设置人工智能相关课程,逐步推广编程教育,鼓励社会力量参与寓教于...

    企鹅号小编
  • IPython使用简易教程

    本文总结Ipython使用的知识。 ? 1 IPython 是什么? IPython (short for Interactive Python) was st...

    陆勤_数据人网
  • QingStor 对象存储发布新版本 Python SDK

    QingStor 对象存储近日发布了新版本的 Python SDK ,并开源在https://github.com/yunify/qingstor-sdk-py...

    BestSDK
  • Python scikit-learn 做线性回归

    线性回归是简单易用的机器学习算法,scikit-learn是python强大的机器学习库。 本篇文章利用线性回归算法预测波士顿的房价。波士顿房价数据集包含波士顿...

    陆勤_数据人网
  • Python语言做数据探索教程

    本文总结Python语言做数据探索的知识。 类似R语言做数据探索,利用Python语言做数据探索。 1 数据导入 2 数据类型变换 3 数据集变换 4 数据排序...

    陆勤_数据人网
  • Python玩机器学习简易教程

    本文介绍利用Python和Python的机器学习库scikit-learn完成一个端到端的机器学习项目。 俗话说,“师傅领进门,修行在个人”。本文就是扮演领进门...

    陆勤_数据人网
  • Anaconda软件安装TensorFlow教程

    本文介绍在Anaconda软件上安装TensorFlow,并且测试和验证。 Anaconda软件的安装,请阅读文章《Anaconda软件安装和简易使用教程》 第...

    陆勤_数据人网
  • 使用Python检测并绕过Web应用程序防火墙

    Web应用防火墙通常会被部署在Web客户端与Web服务器之间,以过滤来自服务器的恶意流量。而作为一名渗透测试人员,想要更好的突破目标系统,就必须要了解目标系统的...

    FB客服
  • 【重磅!】Facebook 发布开源框架 PyTorch,兼容 Python

    本周,Facebook 的 AI 研究团队发布了一个 Python 工具包,专门针对 GPU 加速的深度神经网络(DNN)编程。它有望辅助、或在一定程度上替代,...

    BestSDK
  • Python 安装配置

    本文介绍了 Python 的编译安装方法以及 pip 的使用。 安装 $ wget https://www.python.org/ftp/python/3.6....

    康怀帅

扫码关注云+社区

领取腾讯云代金券