7.5 递归（第一课）-高二《新概念C语言能力教程》同步教学课件 （电工版2020）

第7章 函数 第7章 函数 函数定义 函数调用及函数声明 数组作形参 变量的作用域 全局变量作用域的扩展 限制文件作用域 函数的易用性 递归1 递归2 库函数1 库函数2 团队开发++ 递归1 递归像特殊的迭代，这节课我们讨论递归。 3 7.5.1 递归算法与递归函数 分析问题时经常发现，一些难以直接解决的规模较大的问题，往往可以转化为一些规模较小且与原问题性质相同的子问题。问题的难易程度通常与其规模相关，问题的规模越小，问题就越容易解决。 以求23的阶乘为例，23!=23×22!，原问题变成了23乘22的阶乘。只要求出22的阶乘，进行一次乘法运算就可得到23的阶乘。乘法运算非常简单，可以忽略，关键是求22的阶乘。 从原来求23!到现在求22!，问题的性质没有变，规模变小了，难度降低了。 分析问题时经常发现，一些难以直接解决的规模较大的问题，往往可以转化为一些规模较小且与原问题性质相同的子问题。 问题的难易程度通常与其规模相关，问题的规模越小，问题就越容易解决。 以求23的阶乘为例，23!=23×22!，原问题变成了23乘22的阶乘。只要求出22的阶乘，进行一次乘法运算就可得到23的阶乘。 乘法运算非常简单，可以忽略，关键是求22的阶乘。 从原来求23!到现在求22!，问题的性质没有变，规模变小了，难度降低了。 4 性质相同，规模变小 22!=22×21! ，求22的阶乘又可转化为求21的阶乘。 23!=23×22!，22!=22×21! ，21!=21×20!，……， 3!=3×2!， 2!=2×1! ， 由于性质相同，故子问题可以继续转化性质相同的子问题，……，只要性质相同，就可以一直转化下去。每转化一次，子问题的规模变小一点。随着转化的进行，子问题的规模会逐渐变小，子问题的难度也逐渐降低。 当子问题有解时，停止转化，然后沿着转化过程逆向求解，即由子问题的解得到稍大一点问题的解，……，最终得到原问题的解。 22!=22×21! ，求22的阶乘又可转化为求21的阶乘。 23!=23×22!，22!=22×21! ，21!=21×20!，……， 3!=3×2!， 2!=2×1! ， 由于性质相同，故子问题可以继续转化性质相同的子问题，……，只要性质相同，就可以一直转化下去。每转化一次， 子问题的规模变小一点。随着转化的进行，子问题的规模会逐渐变小，子问题的难度也逐渐降低。 当子问题有解时，停止转化，然后沿着转化过程逆向求解，即由子问题的解得到稍大一点问题的解，……，最终得到原问题的解。 5 递进和回归即递归 原问题转化子问题的过程可称为递进；23!=23×22!，22!=22×21! ，21!=21×20!，……， 3!=3×2!， 2!=2×1! ， 由子问题的解得到原问题的解的过程可称为回归。1!=1，2!=2×1=2，3!=3×2=6，4!=4×6=24，……，23!=23×？ 通过递进和回归两个过程解决问题的方法称为“递归”。 用递归算法求阶乘的过程怎样在C语言中实现呢？ 递归算法用函数实现。 原问题转化子问题的过程可称为递进；由子问题的解得到原问题的解的过程可称为回归。 通过递进和回归两个过程解决问题的方法称为“递归”。 23!=23×22!，22!=22×21! ，21!=21×20!，……， 3!=3×2!， 2!=2×1! ， 1!=1，2!=2×1=2，3!=3×2=6，4!=4×6=24，……，23!=23×？ 用递归算法求阶乘的过程怎样在C语言中实现呢？ 递归算法用函数实现。 6 例7-22 用递归算法求阶乘。 函数fac可以求出整数n的阶乘，首部为unsigned int fac(int n)。 如果整数n的值为0或1，问题有解，无需转化，则直接返回结果；否则，规模较大，需要转化为(n-1)!，返回n * (n-1)!。 函数的定义为： 没有求阶乘的操作符!，用什么命令求(n - 1)的阶乘？ 函数fac可以求出整数n的阶乘，首部为unsigned int fac(int n)。 如果整数n的值为0或1，问题有解，无需转化，则直接返回结果；否则，规模较大，需要转化为(n-1)!，返回n * (n-1)!。 函数的定义为： 若n == 0 || n == 1，则返回1;，否则，返回n * (n - 1)!。 函数的定义很容易理解，但没有没有求阶乘的操作符!，用什么命令求(n - 1)的阶乘？ 用关键字命令？用函数命令？ 7 用函数命令求(n - 1)的阶乘 fac函数可以求出整数n的阶乘，unsigned int fac(int n)。 可以直接调用fac函数求整数n - 1的阶乘，即fac(n - 1)的返回值就是n - 1的阶乘。 在函数的定义中直接调用了函数自身。 直接或间接调用了自身的函数又