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

第7章 函数 第7章 函数 函数定义 函数调用及函数声明 数组作形参 变量的作用域 全局变量作用域的扩展 限制文件作用域 函数的易用性 递归1 递归2 库函数1 库函数2 团队开发++ 递归2 这节课我们继续讨论递归。 3 例7-26 n阶楼梯的走法 楼梯有n阶台阶，上楼时一步可以上1阶，也可以上2阶，编程计算n阶楼梯共有多少种不同的走法？ 设n阶台阶的走法为f(n)，当楼梯只有1阶时，显然只有一种走法，f(1)=1。 只有2阶时，有两种走法，一步一阶地或一步两阶地走上楼梯，f(2)=2。 楼梯多于2阶的时，规模比较大，怎样转化呢？ 根据第一步的走法可将上楼的走法分为两类：第一步上1阶的走法和第一步上2阶的走法。 楼梯有n阶台阶，上楼时一步可以上1阶，也可以上2阶，编程计算n阶楼梯共有多少种不同的走法？ 设n阶台阶的走法为f(n)，当楼梯只有1阶时，显然只有一种走法，f(1)=1。 只有2阶时，有两种走法，一步一阶地或一步两阶地走上楼梯，f(2)=2。 楼梯多于2阶的时，规模比较大，怎样转化呢？ 根据第一步的走法可将上楼的走法分为两类：第一步上1阶的走法和第一步上2阶的走法。 4 n阶楼梯的走法 n阶楼梯的不同走法等于第一步上1阶时的走法加上第一步上2阶时的走法。 第一步上1阶时的走法等于剩余的n-1阶楼梯的走法。 n-1阶楼梯的走法，与原问题相比，性质相同，规模变小。可用递归算法。 n阶台阶的走法为f(n)，则n-1阶楼梯的走法为f(n-1)。 第一步上2阶时的走法为f(n-2)。 n阶楼梯的走法： n阶楼梯的不同走法等于第一步上1阶时的走法加上第一步上2阶时的走法。 第一步上1阶时的走法等于剩余的n-1阶楼梯的走法。 n-1阶楼梯的走法，与原问题相比，性质相同，规模变小。可用递归算法。 n阶台阶的走法为f(n)，则n-1阶楼梯的走法为f(n-1)。 第一步上2阶时的走法为f(n-2)。 n阶楼梯的走法：当n=1时，f(n)=1，当n=2时，f(n)=2，当n>2时，f(n)=f(n-1)+f(n-2)。 5 n阶楼梯的走法 求n阶楼梯走法的递归函数如图所示。 程序中调用这个递归函数求出了4阶楼梯的走法。 6 分析upstairs(4)的执行过程 upstairs(4) upstairs(3) ① upstairs(2) ④ ＋ upstairs(2) ② upstairs(1) ③ ＋ 分析upstairs(4)的执行过程。 upstairs(4)转化为upstairs(3)+upstairs(2)，upstairs(3)先执行。 而upstairs(3)转化为upstairs(2)+upstairs(1)， upstairs(2)执行返回函数值2后，upstairs(1)执行并返回函数值1， upstairs(3)继续执行执行，返回值3. upstairs(2)执行返回函数值2。 upstairs(4)继续执行，返回值5。 7 分析upstairs(4)的执行过程 upstairs(4) upstairs(3) upstairs(2) upstairs(2) upstairs(1) 1->1->1->1 1->1->2 1->2->1 2->1->1 2->2 分析upstairs(4)的执行过程。 upstairs(4)先转化为upstairs(3)，即先上1阶，剩下3阶需要上。上法1-> upstairs(3)执行，先转化为upstairs(2)，即先上1阶，剩下2阶需要上。上法1->1-> upstairs(2)的值为2，即一步1阶或一步2阶，两种上法。上法为1->1->1->1或1->1->2两种。 upstairs(3)再转化为upstairs(1)，即先上2阶，剩下1阶需要上，上法1->2-> upstairs(1)的值为1，即一步1阶，上法1->2->1 upstairs(4)再转化为upstairs(2)，即先上2阶，剩下2阶需要上。上法2-> upstairs(2)的值为2，即一步1阶或一步2阶，两种上法。上法为2->1->1或2->2两种。 综上分析，共有5种上法。 8 例7-27 汉诺塔问题 有一个佛塔，塔内有3个标示为A、B、C的座，A座上有5个大小不等的盘子，大的在下面，小的在上面。现要求把5个盘子从A座移动到C座，每次只允许移动一个盘子，在移动过程中可以利用B座，但是3个座上要始终保持大盘在下面，小盘在上面。怎样移动？ 汉诺塔也称梵塔即佛塔。有一个佛塔，塔内有3个标示为A、B、C的座，A座上有5个大小不等的盘子，大的在下面，小的在上面。现要求把5个盘子从A座移动到C座，每次只允许移动一个盘子，在移动过程中可以利用B座，但是3个座上要始终保持大盘在下面，小盘在上面。怎样移动？ 9 例7-27