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

相关文章

来自专栏码匠的流水账

聊聊spring cloud的HystrixAutoConfiguration

本文主要研究一下spring cloud的HystrixAutoConfiguration

992
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3729
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2518
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2189
来自专栏WOLFRAM

向日葵中的数学之美

1843
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

421
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2828
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1521

扫码关注云+社区