5.5函数的递归(课件）-《程序设计基础（python）》同步教学（人邮版）

函数的递归 Simple Easy Open Free Portable 1 目录 contents 函数递归的思想△ 01 递归实例☆ 02 2 PART 01 函数递归的思想 3 什么是递归？ 一个函数间接或直接的调用自己称为函数的递归调用，实现递归调用的函数称为递归函数。 4 什么情况下，我们会使用递归呢？ 如果一个实际问题可以分解为若干个与原问题性质相同、规模较小的子问题，这样的问题就可以利用递归函数来解决。碰到这类问题，我们可以分三步来化解。 第1步：将原问题分解为一个或多个与原问题性质相同、规模较小的子问题。 第2步：对子问题按照同样的原则继续分解，直到得到一个已知有解的，不用再分解的子问题。 第3步：从有解的子问题的解出发，依次求得规模稍大的子问题的解，最终求得原问题的解。 5 递归方法在解决实际问题时，可以分为以下2个阶段： 1.递归调用阶段：第1步和第2步是第一阶段，称为递归调用阶段，该阶段将原问题不断地分解为新的子问题，逐渐从未知向已知的方向逼近，最终到达已知子问题的解，这时递归调用阶段结束。 2.递推回代阶段：第3步是第二个阶段，该阶段从已知子问题的解出发，按照递推的过程，逐一回代求值，最终得到原问题的解。 6 实现递归的关键： 如何建立一个模型用子问题来表示原问题，即：递归关系；同时如何使递归调用结束，不至于无限期地调用下去，即：给出递归终止的条件。 7 PART 02 递归实例 8 例1：用递归法求n! def fact(n): if n==1 : return 1 return n * fact(n - 1) s = fact(4) print(s) 9 让我们来分析一下这个程序： 分析：n!=n*(n-1) *(n-2)…*1=n*(n-1)!，所以我们可以得到如下关系： 1 n=1 n！= n*(n-1)! n>1 10 求n!，应先求(n-1)!；而求(n-1)!，又需要先求(n-2)!；而求(n–2)!，又可以变成求(n-3)!，...，如此递推，直到最后变成求1!的问题。而根据公式有1!=1（这就是本问题的递归终止条件）。由终止条件得到1!结果后，再反过来依次求出2!，3!，...，直到最后求出n!。 设求n!的函数为fact(n)，函数体内求n!，只要n>1，可用n*fact(n-1)表示，即fact(n)函数体内将递归调用fact()自身；一旦参数n为1，则终止调用函数自身并给出函数值1。 11 我们以n=4为例，说明递归调用和递归回代的过程： Fact(4) 返回 4*Fact(3) Fact(3) 返回 3*Fact(2) Fact(2) 返回 2*Fact(1) Fact(1) 返回 1 调用 调用 调用 回代6 回代2 回代1 12 1.函数递归的思想△ 2.递归实例☆ LOREM 本节小结 13 模块分类 Simple Easy Open Free Portable 14 什么是模块 Python 模块(Module)，是一个 Python 文件，以 .py 结尾，能够帮助程序人员有逻辑地组织 Python 代码段。 把相关的代码分配到一个模块里能让你的代码更好用，更易懂。 15 模块分类 内置模块 自定义模块 第三方模块 16 什么是内置模块 Python自带的模块 17 什么是第三方模块 不在系统内置中，需用使用pip下载安装后，才能使用 什么是自定义模块 程序员自己编写的公共代码，在本地应用 18 安装第三方模块 安装方法，以安装TensorFlow为例，分为两种安装方式 1）使用Pycharm安装 2）使用pip安装 19 使用Pycharm安装第三方模块 setting中搜索Python interpreter,然后点击右侧的“+”号 在搜索框中输入模块名称“tensorflow” 点击Install Package 20 使用pip安装第三方模块 运行cmd,然后输入命令 pip install tensorflow -i https://pypi.tuna.tsinghua.edu.cn/simple -i 代表使用指定的镜像源，本例使用是清华镜像源。 21 编写和使用自定义模块 为了能在多个项目都使用相同的Python源码，因此我们通常将程序写到文件中以便永久保存下来，需要时就通过python name.py方式去执行，此时name.py就是自定义模块。 22 自定义模块使用案例 编辑dada.py,作为自定义模块 #dada.py print('from the dada.py') name = 'dada' def read(): print('模块：',name) 将dada.py 放入python的lib目录中 在新项目中 import dada dada.read() 23 $$