Python3：怎么通过递归函数

函数的递归调用

成都网络公司-成都网站建设公司成都创新互联十载经验成就非凡，专业从事网站设计制作、成都做网站，成都网页设计，成都网页制作，软文发稿，广告投放等。十载来已成功提供全面的成都网站建设方案，打造行业特色的成都网站建设案例，建站热线：13518219792，我们期待您的来电！

递归问题是一个说简单也简单，说难也有点难理解的问题.我想非常有必要对其做一个总结.

首先理解一下递归的定义，递归就是直接或间接的调用自身.而至于什么时候要用到递归，递归和非递归又有那些区别？又是一个不太容易掌握的问题，更难的是对于递归调用的理解.下面我们就从程序+图形的角度对递归做一个全面的阐述.

我们从常见到的递归问题开始:

1 阶层函数

#include iostream

using namespace std;

int factorial(int n)

{

if (n == 0)

{

return 1;

}

else

{

int result = factorial(n-1);

return n * result;

}

}

int main()

{

int x = factorial(3);

cout x endl;

return 0;

}

这是一个递归求阶层函数的实现。很多朋友只是知道该这么实现的，也清楚它是通过不断的递归调用求出的结果.但他们有些不清楚中间发生了些什么.下面我们用图对此做一个清楚的流程:

根据上面这个图，大家可以很清楚的看出来这个函数的执行流程。我们的阶层函数factorial被调用了4次.并且我们可以看出在调用后面的调用中，前面的调用并不退出。他们同时存在内存中。可见这是一件很浪费资源的事情。我们该次的参数是3.如果我们传递10000呢。那结果就可想而知了.肯定是溢出了.就用int型来接收结果别说10000，100就会产生溢出.即使不溢出我想那肯定也是见很浪费资源的事情.我们可以做一个粗略的估计:每次函数调用就单变量所需的内存为:两个int型变量.n和result.在32位机器上占8B.那么10000就需要10001次函数调用.共需10001*8/1024 = 78KB.这只是变量所需的内存空间.其它的函数调用时函数入口地址等仍也需要占用内存空间。可见递归调用产生了一个不小的开销.

2 斐波那契数列

int Fib(int n)

{

if (n = 1)

{

return n;

}

else

{

return Fib(n-1) + Fib(n-2);

}

}

这个函数递归与上面的那个有些不同.每次调用函数都会引起另外两次的调用.最后将结果逐级返回.

我们可以看出这个递归函数同样在调用后买的函数时，前面的不退出而是在等待后面的结果，最后求出总结果。这就是递归.

3

#include iostream

using namespace std;

void recursiveFunction1(int num)

{

if (num 5)

{

cout num endl;

recursiveFunction1(num+1);

}

}

void recursiveFunction2(int num)

{

if (num 5)

{

recursiveFunction2(num+1);

cout num endl;

}

}

int main()

{

recursiveFunction1(0);

recursiveFunction2(0);

return 0;

}

运行结果:

1

2

3

4

4

3

2

1

该程序中有两个递归函数。传递同样的参数，但他们的输出结果刚好相反。理解这两个函数的调用过程可以很好的帮助我们理解递归:

我想能够把上面三个函数的递归调用过程理解了，你已经把递归调用理解的差不多了.并且从上面的递归调用中我们可以总结出递归的一个规律：他是逐级的调用，而在函数结束的时候是从最后面往前反序的结束.这种方式是很占用资源，也很费时的。但是有的时候使用递归写出来的程序很容易理解，很易读.

为什么使用递归:

1 有时候使用递归写出来的程序很容易理解，很易读.

2 有些问题只有递归能够解决.非递归的方法无法实现.如:汉诺塔.

递归的条件:

并不是说所有的问题都可以使用递归解决，他必须的满足一定的条件。即有一个出口点.也就是说当满足一定条件时，程序可以结束，从而完成递归调用，否则就陷入了无限的递归调用之中了.并且这个条件还要是可达到的.

递归有哪些优点:

易读，容易理解，代码一般比较短.

递归有哪些缺点:

占用内存资源多，费时，效率低下.

因此在我们写程序的时候不要轻易的使用递归，虽然他有他的优点，但是我们要在易读性和空间，效率上多做权衡.一般情况下我们还是使用非递归的方法解决问题.若一个算法非递归解法非常难于理解。我们使用递归也未尝不可.如:二叉树的遍历算法.非递归的算法很难与理解.而相比递归算法就容易理解很多.

对于递归调用的问题，我们在前一段时间写图形学程序时，其中有一个四连同填充算法就是使用递归的方法。结果当要填充的图形稍微大一些时，程序就自动关闭了.这不是一个人的问题，所有人写出来的都是这个问题.当时我们给与的解释就是堆栈溢出。就多次递归调用占用太多的内存资源致使堆栈溢出，程序没有内存资源执行下去，从而被操作系统强制关闭了.这是一个真真切切的例子。所以我们在使用递归的时候需要权衡再三.

python递归函数

def Sum(m): #函数返回两个值：递归次数，所求的值 if m==1:return 1,m return 1+Sum(m-1)[0],m+Sum(m-1)[1]cishu=Sum(10)[0] print cishu def Sum(m,n=1): ... if m==1:return n,m ... return n,m+Sum(m-1,n+1)[1] print Sum(10)[0] 10 print Sum(5)[0] 5

python循环、递归

for 变量 in range(次数)：被执行的语句                       变量：表示每次循环的次数，0-1之间

range（n）n表示产生0到n-1的整数序列共N个               range(m,n)  产生m到n-1的整数序列，共n-m个

循环for语句  ：for 循环变量 in遍历结构：语句体1  else：语句体2 

无限循环： while条件： 语句块

while 条件：语句体1 else: 语句体2

循环保留字：break     continue

方法1：from random import random

from time import perf_counter

DARTS=1000

hits=0.0

start =perf_counter()

for i in range(1,DARTS+1):

x,y=random(),random()

dist=pow(x**2+y**2,0.5)

if dist=1.0:

    hits =hits+1

pi=4*(hits/DARTS)

print("圆周率是:{}".format(pi))

print("运行时间是{:.5f}s".format(perf_counter()-start))

方法2：

pi=0

n=100

for k in range(n):

pi += 1/pow(16,k)*(\

    4/(8*k+1)-2/(8*k+4) - \

    1/(8*k+5) - 1/(8*k+6))

print("圆周率值是:{}".format(pi))

def 函数名 （0个或者多个）：函数体  renturn 返回值

def 函数名 （非可选参数，可选参数）：函数体  renturn 返回值

参数传递的两种方式：位置传递，名称传递

科赫雪花：

import turtle

def koch(size,n):

if n==0:

    turtle.fd(size)

else:

    for angle in [0,60,-120,60]:

        turtle.left(angle)

        koch(size/3,n-1)

def main():

turtle.setup(400,200)

turtle.penup()

turtle.pendown()

turtle.pensize(2)

l=3

koch(600,l)

turtle.right(120)

turtle.pencolor('blue')

koch(600,l)

turtle.right(120)

turtle.pencolor('red')

koch(600,l)

turtle.speed(3000)

turtle.hideturtle()

main()

阶乘：

def fact(n):

s=1

for i in range(1,n+1):

    s*=i

return s

c=eval(input("从键盘输入一个数字"))

print("阶乘结果",fact(c))

Python算法-爬楼梯与递归函数

可以看出来的是，该题可以用斐波那契数列解决。

楼梯一共有n层，每次只能走1层或者2层，而要走到最终的n层。不是从n-1或者就是n-2来的。

F(1) = 1

F(2) = 2

F(n) = F(n-1) + F(n-2) (n=3)

这是递归写法，但是会导致栈溢出。在计算机中，函数的调用是通过栈进行实现的，如果递归调用的次数过多，就会导致栈溢出。

针对这种情况就要使用方法二，改成非递归函数。

将递归进行改写，实现循环就不会导致栈溢出

后端编程Python3-调试、测试和性能剖析(下)

单元测试（Unit Testing）

为程序编写测试——如果做的到位——有助于减少bug的出现，并可以提高我们对程序按预期目标运行的信心。通常，测试并不能保证正确性，因为对大多数程序而言， 可能的输入范围以及可能的计算范围是如此之大，只有其中最小的一部分能被实际地进 行测试。尽管如此，通过仔细地选择测试的方法和目标，可以提高代码的质量。

大量不同类型的测试都可以进行，比如可用性测试、功能测试以及整合测试等。这里, 我们只讲单元测试一对单独的函数、类与方法进行测试，确保其符合预期的行为。

TDD的一个关键点是，当我们想添加一个功能时——比如为类添加一个方法—— 我们首次为其编写一个测试用例。当然，测试将失败，因为我们还没有实际编写该方法。现在，我们编写该方法，一旦方法通过了测试，就可以返回所有测试，确保我们新添加的代码没有任何预期外的副作用。一旦所有测试运行完毕（包括我们为新功能编写的测试），就可以对我们的代码进行检查，并有理有据地相信程序行为符合我们的期望——当然，前提是我们的测试是适当的。

比如，我们编写了一个函数，该函数在特定的索引位置插入一个字符串，可以像下面这样开始我们的TDD：

def insert_at（string, position, insert）:

"""Returns a copy of string with insert inserted at the position

string = "ABCDE"

result =[]

for i in range(-2, len(string) + 2):

... result.append(insert_at(string, i,“-”))

result[:5]

['ABC-DE', 'ABCD-E', '-ABCDE','A-BCDE', 'AB-CDE']

result[5:]

['ABC-DE', 'ABCD-E', 'ABCDE-', 'ABCDE-']

"""

return string

对不返回任何参数的函数或方法（通常返回None）,我们通常赋予其由pass构成的一个suite,对那些返回值被试用的，我们或者返回一个常数（比如0）,或者某个不变的参数——这也是我们这里所做的。（在更复杂的情况下，返回fake对象可能更有用一一对这样的类，提供mock对象的第三方模块是可用的。）

运行doctest时会失败，并列出每个预期内的字符串（'ABCD-EF'、'ABCDE-F' 等），及其实际获取的字符串（所有的都是'ABCD-EF'）。一旦确定doctest是充分的和正确的，就可以编写该函数的主体部分，在本例中只是简单的return string[:position] + insert+string[position:]。（如果我们编写的是 return string[:position] + insert,之后复制 string [:position]并将其粘贴在末尾以便减少一些输入操作，那么doctest会立即提示错误。）

Python的标准库提供了两个单元测试模块，一个是doctest,这里和前面都简单地提到过，另一个是unittest。此外，还有一些可用于Python的第三方测试工具。其中最著名的两个是nose (code.google.com/p/python-nose)与py.test (codespeak.net/py/dist/test/test.html), nose 致力于提供比标准的unittest 模块更广泛的功能，同时保持与该模块的兼容性，py.test则采用了与unittest有些不同的方法，试图尽可能消除样板测试代码。这两个第三方模块都支持测试发现，因此没必要写一个总体的测试程序——因为模块将自己搜索测试程序。这使得测试整个代码树或某一部分 (比如那些已经起作用的模块)变得很容易。那些对测试严重关切的人，在决定使用哪个测试工具之前，对这两个(以及任何其他有吸引力的)第三方模块进行研究都是值 得的。

创建doctest是直截了当的：我们在模块中编写测试、函数、类与方法的docstrings。 对于模块，我们简单地在末尾添加了 3行：

if __name__ =="__main__":

import doctest

doctest.testmod()

在程序内部使用doctest也是可能的。比如，blocks.py程序(其模块在后面)有自己函数的doctest，但以如下代码结尾：

if __name__== "__main__":

main()

这里简单地调用了程序的main()函数，并且没有执行程序的doctest。要实验程序的 doctest,有两种方法。一种是导入doctest模块，之后运行程序---比如，在控制台中输 入 python3 -m doctest blocks.py (在 Wndows 平台上，使用类似于 C:Python3 lpython.exe 这样的形式替代python3)。如果所有测试运行良好，就没有输出，因此，我们可能宁愿执行python3-m doctest blocks.py-v,因为这会列出每个执行的doctest,并在最后给出结果摘要。

另一种执行doctest的方法是使用unittest模块创建单独的测试程序。在概念上， unittest模块是根据Java的JUnit单元测试库进行建模的，并用于创建包含测试用例的测试套件。unittest模块可以基于doctests创建测试用例，而不需要知道程序或模块包含的任何事物——只要知道其包含doctest即可。因此，为给blocks.py程序制作一个测试套件，我们可以创建如下的简单程序(将其称为test_blocks.py)：

import doctest

import unittest

import blocks

suite = unittest.TestSuite()

suite.addTest(doctest.DocTestSuite(blocks))

runner = unittest.TextTestRunner()

print(runner.run(suite))

注意，如果釆用这种方法，程序的名称上会有一个隐含的约束：程序名必须是有效的模块名。因此，名为convert-incidents.py的程序的测试不能写成这样。因为import convert-incidents不是有效的，在Python标识符中，连接符是无效的（避开这一约束是可能的，但最简单的解决方案是使用总是有效模块名的程序文件名，比如，使用下划线替换连接符）。这里展示的结构（创建一个测试套件，添加一个或多个测试用例或测试套件，运行总体的测试套件，输出结果）是典型的机遇unittest的测试。运行时，这一特定实例产生如下结果：

...

.............................................................................................................

Ran 3 tests in 0.244s

OK

每次执行一个测试用例时，都会输出一个句点（因此上面的输出最前面有3个句点），之后是一行连接符，再之后是测试摘要（如果有任何一个测试失败，就会有更多的输出信息）。

如果我们尝试将测试分离开（典型情况下是要测试的每个程序和模块都有一个测试用例），就不要再使用doctests,而是直接使用unittest模块的功能——尤其是我们习惯于使用JUnit方法进行测试时ounittest模块会将测试分离于代码——对大型项目（测试编写人员与开发人员可能不一致）而言，这种方法特别有用。此外，unittest单元测试编写为独立的Python模块，因此，不会像在docstring内部编写测试用例时受到兼容性和明智性的限制。

unittest模块定义了 4个关键概念。测试夹具是一个用于描述创建测试（以及用完之后将其清理）所必需的代码的术语，典型实例是创建测试所用的一个输入文件，最后删除输入文件与结果输出文件。测试套件是一组测试用例的组合。测试用例是测试的基本单元—我们很快就会看到实例。测试运行者是执行一个或多个测试套件的对象。

典型情况下，测试套件是通过创建unittest.TestCase的子类实现的，其中每个名称 以“test”开头的方法都是一个测试用例。如果我们需要完成任何创建操作，就可以在一个名为setUp()的方法中实现；类似地，对任何清理操作，也可以实现一个名为 tearDown()的方法。在测试内部，有大量可供我们使用的unittest.TestCase方法，包括 assertTrue()、assertEqual()、assertAlmostEqual()（对于测试浮点数很有用）、assertRaises() 以及更多，还包括很多对应的逆方法，比如assertFalse()、assertNotEqual()、failIfEqual()、 failUnlessEqual ()等。

unittest模块进行了很好的归档，并且提供了大量功能，但在这里我们只是通过一 个非常简单的测试套件来感受一下该模块的使用。这里将要使用的实例,该练习要求创建一个Atomic模块，该模块可以用作一 个上下文管理器，以确保或者所有改变都应用于某个列表、集合或字典，或者所有改变都不应用。作为解决方案提供的Atomic.py模块使用30行代码来实现Atomic类， 并提供了 100行左右的模块doctest。这里，我们将创建test_Atomic.py模块，并使用 unittest测试替换doctest,以便可以删除doctest。

在编写测试模块之前，我们需要思考都需要哪些测试。我们需要测试3种不同的数据类型：列表、集合与字典。对于列表，需要测试的是插入项、删除项或修改项的值。对于集合，我们必须测试向其中添加或删除一个项。对于字典，我们必须测试的是插入一个项、修改一个项的值、删除一个项。此外，还必须要测试的是在失败的情况下，不会有任何改变实际生效。

结构上看，测试不同数据类型实质上是一样的，因此，我们将只为测试列表编写测试用例，而将其他的留作练习。test_Atomic.py模块必须导入unittest模块与要进行测试的Atomic模块。

创建unittest文件时，我们通常创建的是模块而非程序。在每个模块内部，我们定义一个或多个unittest.TestCase子类。比如，test_Atomic.py模块中仅一个单独的 unittest-TestCase子类，也就是TestAtomic (稍后将对其进行讲解)，并以如下两行结束:

if name == "__main__":

unittest.main()

这两行使得该模块可以单独运行。当然，该模块也可以被导入并从其他测试程序中运行——如果这只是多个测试套件中的一个，这一点是有意义的。

如果想要从其他测试程序中运行test_Atomic.py模块，那么可以编写一个与此类似的程序。我们习惯于使用unittest模块执行doctests,比如：

import unittest

import test_Atomic

suite = unittest.TestLoader().loadTestsFromTestCase(test_Atomic.TestAtomic)

runner = unittest.TextTestRunner()

pnnt(runner.run(suite))

这里，我们已经创建了一个单独的套件，这是通过让unittest模块读取test_Atomic 模块实现的，并且使用其每一个test*()方法(本实例中是test_list_success()、test_list_fail()，稍后很快就会看到)作为测试用例。

我们现在将查看TestAtomic类的实现。对通常的子类(不包括unittest.TestCase 子类)，不怎么常见的是，没有必要实现初始化程序。在这一案例中，我们将需要建立 一个方法，但不需要清理方法，并且我们将实现两个测试用例。

def setUp(self)：

self.original_list = list(range(10))

我们已经使用了 unittest.TestCase.setUp()方法来创建单独的测试数据片段。

def test_list_succeed(self):

items = self.original_list[:]

with Atomic.Atomic(items) as atomic:

atomic.append(1999)

atomic.insert(2, -915)

del atomic[5]

atomic[4]= -782

atomic.insert(0, -9)

self.assertEqual(items,

[-9, 0, 1, -915, 2, -782, 5, 6, 7, 8, 9, 1999])

def test_list_fail(self):

items = self.original_list[:]

with self.assertRaises(AttributeError):

with Atomic.Atomic(items) as atomic:

atomic.append(1999)

atomic.insert(2, -915)

del atomic[5]

atomic[4] = -782

atomic.poop() # Typo

self.assertListEqual(items, self.original_list)

这里，我们直接在测试方法中编写了测试代码，而不需要一个内部函数，也不再使用unittest.TestCase.assertRaised()作为上下文管理器(期望代码产生AttributeError)。 最后我们也使用了 Python 3.1 的 unittest.TestCase.assertListEqual()方法。

正如我们已经看到的，Python的测试模块易于使用，并且极为有用，在我们使用 TDD的情况下更是如此。它们还有比这里展示的要多得多的大量功能与特征——比如，跳过测试的能力，这有助于理解平台差别——并且这些都有很好的文档支持。缺失的一个功能——但nose与py.test提供了——是测试发现，尽管这一特征被期望在后续的Python版本(或许与Python 3.2—起)中出现。

性能剖析（Profiling）

如果程序运行很慢，或者消耗了比预期内要多得多的内存，那么问题通常是选择的算法或数据结构不合适，或者是以低效的方式进行实现。不管问题的原因是什么， 最好的方法都是准确地找到问题发生的地方,而不只是检査代码并试图对其进行优化。 随机优化会导致引入bug,或者对程序中本来对程序整体性能并没有实际影响的部分进行提速，而这并非解释器耗费大部分时间的地方。

在深入讨论profiling之前，注意一些易于学习和使用的Python程序设计习惯是有意义的，并且对提高程序性能不无裨益。这些技术都不是特定于某个Python版本的， 而是合理的Python程序设计风格。第一，在需要只读序列时，最好使用元组而非列表； 第二，使用生成器，而不是创建大的元组和列表并在其上进行迭代处理；第三，尽量使用Python内置的数据结构 dicts、lists、tuples 而不实现自己的自定义结构，因为内置的数据结构都是经过了高度优化的；第四，从小字符串中产生大字符串时， 不要对小字符串进行连接，而是在列表中累积，最后将字符串列表结合成为一个单独的字符串；第五，也是最后一点，如果某个对象(包括函数或方法)需要多次使用属性进行访问(比如访问模块中的某个函数)，或从某个数据结构中进行访问，那么较好的做法是创建并使用一个局部变量来访问该对象，以便提供更快的访问速度。

Python标准库提供了两个特别有用的模块，可以辅助调査代码的性能问题。一个是timeit模块——该模块可用于对一小段Python代码进行计时，并可用于诸如对两个或多个特定函数或方法的性能进行比较等场合。另一个是cProfile模块，可用于profile 程序的性能——该模块对调用计数与次数进行了详细分解，以便发现性能瓶颈所在。

为了解timeit模块，我们将查看一些小实例。假定有3个函数function_a()、 function_b()、function_c(), 3个函数执行同样的计算，但分别使用不同的算法。如果将这些函数放于同一个模块中(或分别导入)，就可以使用timeit模块对其进行运行和比较。下面给出的是模块最后使用的代码：

if __name__ == "__main__":

repeats = 1000

for function in ("function_a", "function_b", "function_c"):

t = timeit.Timer("{0}(X, Y)".format(function),"from __main__ import {0}, X, Y".format(function))

sec = t.timeit(repeats) / repeats

print("{function}() {sec:.6f} sec".format(**locals()))

赋予timeit.Timer()构造子的第一个参数是我们想要执行并计时的代码，其形式是字符串。这里，该字符串是“function_a(X,Y)”；第二个参数是可选的，还是一个待执行的字符串，这一次是在待计时的代码之前，以便提供一些建立工作。这里，我们从 __main__ (即this)模块导入了待测试的函数，还有两个作为输入数据传入的变量(X 与Y),这两个变量在该模块中是作为全局变量提供的。我们也可以很轻易地像从其他模块中导入数据一样来进行导入操作。

调用timeit.Timer对象的timeit()方法时，首先将执行构造子的第二个参数(如果有)， 之后执行构造子的第一个参数并对其执行时间进行计时。timeit.Timer.timeit()方法的返回值是以秒计数的时间，类型是float。默认情况下，timeit()方法重复100万次，并返回所 有这些执行的总秒数，但在这一特定案例中，只需要1000次反复就可以给出有用的结果, 因此对重复计数次数进行了显式指定。在对每个函数进行计时后，使用重复次数对总数进行除法操作，就得到了平均执行时间，并在控制台中打印出函数名与执行时间。

function_a() 0.001618 sec

function_b() 0.012786 sec

function_c() 0.003248 sec

在这一实例中，function_a()显然是最快的——至少对于这里使用的输入数据而言。 在有些情况下一一比如输入数据不同会对性能产生巨大影响——可能需要使用多组输入数据对每个函数进行测试，以便覆盖有代表性的测试用例，并对总执行时间或平均执行时间进行比较。

有时监控自己的代码进行计时并不是很方便，因此timeit模块提供了一种在命令行中对代码执行时间进行计时的途径。比如，要对MyModule.py模块中的函数function_a()进行计时，可以在控制台中输入如下命令：python3 -m timeit -n 1000 -s "from MyModule import function_a, X, Y" "function_a(X, Y)"(与通常所做的一样，对 Windows 环境，我们必须使用类似于C:Python3lpython.exe这样的内容来替换python3)。-m选项用于Python 解释器，使其可以加载指定的模块(这里是timeit),其他选项则由timeit模块进行处理。 -n选项指定了循环计数次数，-s选项指定了要建立，最后一个参数是要执行和计时的代码。命令完成后，会向控制台中打印运行结果，比如：

1000 loops, best of 3: 1.41 msec per loop

之后我们可以轻易地对其他两个函数进行计时，以便对其进行整体的比较。

cProfile模块(或者profile模块，这里统称为cProfile模块)也可以用于比较函数 与方法的性能。与只是提供原始计时的timeit模块不同的是，cProfile模块精确地展示 了有什么被调用以及每个调用耗费了多少时间。下面是用于比较与前面一样的3个函数的代码：

if __name__ == "__main__":

for function in ("function_a", "function_b", "function_c"):

cProfile.run("for i in ranged 1000): {0}(X, Y)".format(function))

我们必须将重复的次数放置在要传递给cProfile.run()函数的代码内部，但不需要做任何创建，因为模块函数会使用内省来寻找需要使用的函数与变量。这里没有使用显式的print()语句，因为默认情况下，cProfile.run()函数会在控制台中打印其输出。下面给出的是所有函数的相关结果(有些无关行被省略，格式也进行了稍许调整，以便与页面适应)：

1003 function calls in 1.661 CPU seconds

ncalls tottime percall cumtime percall filename:lineno(function)

1 0.003 0.003 1.661 1.661 :1 ( )

1000 1.658 0.002 1.658 0.002 MyModule.py:21 (function_a)

1 0.000 0.000 1.661 1.661 {built-in method exec}

5132003 function calls in 22.700 CPU seconds

ncalls tottime percall cumtime percall filename:lineno(function)

1 0.487 0.487 22.700 22.700 : 1 ( )

1000 0.011 0.000 22.213 0.022 MyModule.py:28(function_b)

5128000 7.048 0.000 7.048 0.000 MyModule.py:29( )

1000 0.00 50.000 0.005 0.000 {built-in method bisectjeft}

1 0.000 0.000 22.700 22.700 {built-in method exec}

1000 0.001 0.000 0.001 0.000 {built-in method len}

1000 15.149 0.015 22.196 0.022 {built-in method sorted}

5129003 function calls in 12.987 CPU seconds

ncalls tottime percall cumtime percall filename:lineno(function)

1 0.205 0.205 12.987 12.987 :l ( )

1000 6.472 0.006 12.782 0.013 MyModule.py:36(function_c)

5128000 6.311 0.000 6.311 0.000 MyModule.py:37( )

1 0.000 0.000 12.987 12.987 {built-in method exec}

ncalls ("调用的次数")列列出了对指定函数(在filename:lineno(function)中列出) 的调用次数。回想一下我们重复了 1000次调用，因此必须将这个次数记住。tottime (“总的时间”)列列出了某个函数中耗费的总时间，但是排除了函数调用的其他函数内部花费的时间。第一个percall列列出了对函数的每次调用的平均时间(tottime // ncalls)。 cumtime ("累积时间")列出了在函数中耗费的时间，并且包含了函数调用的其他函数内部花费的时间。第二个percall列列出了对函数的每次调用的平均时间，包括其调用的函数耗费的时间。

这种输出信息要比timeit模块的原始计时信息富有启发意义的多。我们立即可以发现，function_b()与function_c()使用了被调用5000次以上的生成器，使得它们的速度至少要比function_a()慢10倍以上。并且，function_b()调用了更多通常意义上的函数，包括调用内置的sorted()函数，这使得其几乎比function_c()还要慢两倍。当然,timeit() 模块提供了足够的信息来查看计时上存在的这些差别，但cProfile模块允许我们了解为什么会存在这些差别。正如timeit模块允许对代码进行计时而又不需要对其监控一样，cProfile模块也可以做到这一点。然而，从命令行使用cProfile模块时，我们不能精确地指定要执行的 是什么——而只是执行给定的程序或模块，并报告所有这些的计时结果。需要使用的 命令行是python3 -m cProfile programOrModule.py,产生的输出信息与前面看到的一 样，下面给出的是输出信息样例，格式上进行了一些调整，并忽略了大多数行：

10272458 function calls (10272457 primitive calls) in 37.718 CPU secs

ncalls tottime percall cumtime percall filename:lineno(function)

10.000 0.000 37.718 37.718 :1 ( )

10.719 0.719 37.717 37.717 :12( )

1000 1.569 0.002 1.569 0.002 :20(function_a)

1000 0.011 0.000 22.560 0.023 :27(function_b)

5128000 7.078 0.000 7.078 0.000 :28( )

1000 6.510 0.007 12.825 0.013 :35(function_c)

5128000 6.316 0.000 6.316 0.000 :36( )

在cProfile术语学中，原始调用指的就是非递归的函数调用。

以这种方式使用cProfile模块对于识别值得进一步研究的区域是有用的。比如，这里 我们可以清晰地看到function_b()需要耗费更长的时间，但是我们怎样获取进一步的详细资料？我们可以使用cProfile.run("function_b()")来替换对function_b()的调用。或者可以保存完全的profile数据并使用pstats模块对其进行分析。要保存profile,就必须对命令行进行稍许修改:python3 -m cProfile -o profileDataFile programOrModule.py。 之后可以对 profile 数据进行分析，比如启动IDLE,导入pstats模块，赋予其已保存的profileDataFile,或者也可以在控制台中交互式地使用pstats。

下面给出的是一个非常短的控制台会话实例，为使其适合页面展示，进行了适当调整，我们自己的输入则以粗体展示：

$ python3 -m cProfile -o profile.dat MyModule.py

$ python3 -m pstats

Welcome to the profile statistics browser.

% read profile.dat

profile.dat% callers function_b

Random listing order was used

List reduced from 44 to 1 due to restriction

Function was called by...

ncalls tottime cumtime

:27(function_b) - 1000 0.011 22.251 :12( )

profile.dat% callees function_b

Random listing order was used

List reduced from 44 to 1 due to restriction

Function called...

ncalls tottime cumtime

:27(function_b)-

1000 0.005 0.005 built-in method bisectJeft

1000 0.001 0.001 built-in method len

1000 1 5.297 22.234 built-in method sorted

profile.dat% quit

输入help可以获取命令列表，help后面跟随命令名可以获取该命令的更多信息。比如, help stats将列出可以赋予stats命令的参数。还有其他一些可用的工具，可以提供profile数据的图形化展示形式，比如 RunSnakeRun (), 该工具需要依赖于wxPython GUI库。

使用timeit与cProfile模块，我们可以识别出我们自己代码中哪些区域会耗费超过预期的时间；使用cProfile模块，还可以准确算岀时间消耗在哪里。

以上内容部分摘自视频课程 05后端编程Python-19调试、测试和性能调优(下) ，更多实操示例请参照视频讲解。跟着张员外讲编程，学习更轻松，不花钱还能学习真本领。

Python 实现递归

一、使用递归的背景

先来看一个☝️接口结构：

这个孩子，他是一个列表，下面有6个元素

展开children下第一个元素[0]看看：

发现[0]除了包含一些字段信息，还包含了 children 这个字段（喜当爹），同时这个children下包含了2个元素：

展开他的第一个元素，不出所料，也含有children字段（人均有娃）

可以理解为children是个对象，他包含了一些属性，特别的是其中有一个属性与父级children是一模一样的，他包含父级children所有的属性。

比如每个children都包含了一个name字段，我们要拿到所有children里name字段的值，这时候就要用到递归啦～

二、find_children.py

拆分理解：

1.首先import requests库，用它请求并获取接口返回的数据

2.若children以上还有很多层级，可以缩小数据范围，定位到children的上一层级

3.来看看定义的函数

我们的函数调用：find_children(node_f, 'children')

其中，node_f：json字段

    children：递归对象

 以下这段是实现递归的核心：

   if items['children']:

 items['children']不为None，表示该元素下的children字段还有子类数据值，此时满足if条件，可理解为 if 1。

 items['children']为None，表示该元素下children值为None，没有后续可递归值，此时不满足if条件，可理解为 if 0，不会再执行if下的语句（不会再递归）。

至此，每一层级中children的name以及下一层级children的name就都取出来了

希望到这里能帮助大家理解递归的思路，以后根据这个模板直接套用就行

（晚安啦～）

源码参考：

网页题目：包含python递归函数调试的词条
URL网址：http://scyanting.com/article/heodos.html