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 条评论
登录 后参与评论

相关文章

来自专栏java学习

面试题12(如何正确使用this)

哪些语句能放在如下代码中所示位置,而不会导致编译错误? public class ThisUse{ int plane; static int ...

2473
来自专栏IT笔记

JAVA中基本数据类型和引用数据类型特点

特点: 一、从概念方面来说 基本数据类型:变量名指向具体的数值 引用数据类型:变量名指向存数据对象的内存地址,即变量名指向hash值 二、从内存构建方面来说...

2498
来自专栏java学习

面试题31(关于重载与重写的正确的理解?)

一个类中,有两个方法名、形参类型、顺序和个数都完全一样,返回值不一样的方法,这种现象叫覆盖。( )? A 正确 B 错误 考点:考察求职者对重载与重写的正确的理...

2725
来自专栏ACM算法日常

Find the nth digit(二分查找) - HDU 1597

...

672
来自专栏Python攻城狮

Python高级编程-装饰器1.装饰器的理解 2.多个装饰器 3.装饰器(decorator)功能 4.装饰器示例

装饰器是程序开发中经常会用到的一个功能,用好了装饰器,开发效率如虎添翼,所以这也是Python面试中必问的问题,但对于好多初次接触这个知识的人来讲,这个功能有点...

662
来自专栏mukekeheart的iOS之旅

OC学习2——C语言特性之函数

1、OC是在C语言的基础上进行扩展的,在OC中直接用C语言进行coding也是可以通过编译的。因此,函数定义的语法格式如下: 函数返回值类型 函数名(形参列表...

2807
来自专栏Bingo的深度学习杂货店

Q189 Rotate Array

Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

3487
来自专栏企鹅号快讯

Python之递归函数

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

1888
来自专栏鬼谷君

Python中的join()函数的用法

Python中有join()和os.path.join()两个函数,具体作用如下:     join():    连接字符串数组。将字符串、元组、列表中的元素以...

331
来自专栏Small Code

【Python】小谈numpy数组占用内存空间问题

之前跟同学讨论过numpy数组的占用空间大小问题,但是今天给忘了,又重新试验了一下,主要是利用sys模块的getsizeof函数,使用的版本是 Python3....

27510

扫描关注云+社区