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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

判断单链表是否存在环

周末参加完美世界校园招聘中就有一道判断单链表是否有环的编程题。 写一个C/C++函数,来判断一个单链表是否具有环,如果存在环,则给出环的入口点。 有一个单链表,...

1799
来自专栏数据结构与算法

2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

2684
来自专栏数据结构与算法

洛谷P3382 【模板】三分法(三分)

970
来自专栏浪淘沙

Python学习总结3--Python基础

    a = 100 if a >= 0:     print(a) else:     print(-a) 其中,#为注...

501
来自专栏GreenLeaves

C#运算符的优先级

在C#中,一共有38个常用的运用符,根据它们所执行运算的特点和它们的优先级,为了便于记忆,我将它们归为七个等级:1、单元运算符和括号。2、常规算术运算符。3、位...

18410
来自专栏天天

运算符与表达式

531
来自专栏lhyt前端之路

js版本的(广、深)度优先搜索0. 前言1.队列、栈2.BFS1.1 矩阵形式的图的遍历1.2 树的BFS举例3.DFS

广度优先搜索(BFS)和深度优先搜索(DFS),大家可能在oj上见过,各种求路径、最短路径、最优方法、组合等等。于是,我们不妨动手试一下js版本怎么玩。

802
来自专栏小狼的世界

PHP中正则的使用

正则表达式,作为一种快速、便捷的处理字符串的工具,在各种编程语言中都有着广泛的用途,通过在PHP中的一些使用,下面记录一下关于PHP中正则使用的一些技巧。

603
来自专栏和蔼的张星的图像处理专栏

57. 三数之和双指针加set暴力去重

给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b + c = 0的三元组。

1021
来自专栏King_3的技术专栏

leetcode-479-Largest Palindrome Product(找到两个乘数相乘得到的最大的回文数)

1373

扫码关注云+社区