安博 C语言培训 C6ppt课件.pptVIP

纲要 了解递归 讨论为使递归函数正确工作而必须满足的 条件 描述递归函数在执行时如何工作 理解堆栈在递归函数执行过程中的作用 递归 递归的来历：拉丁语词根“re”的意思是“后退”，拉丁语后缀“currere”的意思是“运行” 递归在字面上的意思是“向回运行”或“再次发生，特别是以特定的间隙再次发生” 在计算机编程的环境下，单词“递归”指的是能够调用自己的函数 示例： int myRecursive(int x) { . . . myRecursive(x-1); . . . } 递归 递归 我们还可以用数学归纳法来定义阶乘，比如说， 如下递归的进行定义： n!= n x (n-1)! （例如，n 乘以 n-1 的阶乘，如果 n 0 的话） = 1 (如果 n = 0） 下面给出了 n 的阶乘的正式递归定义： n!=1 如果 n = 0 if (n==0)  return 1; else return factorial(n-1) * n; } 这是一个递归函数，因为 factorial 在函数体 中调用了自己 斐波纳契数列 汉诺塔 在著名的汉诺塔问题中，有三根柱子，分别标为 A、B 和 C，以及 n 个盘子，它们的直径为 1、2、3 . . . n 一开始所有的盘子均以从大到小的顺序从底往上堆在一个柱子上 现在的问题是将全部 n 个盘子从 A 柱（初始位置）移到 C 柱（最终位置），移动中的规则如下： 一次只能移动一个盘子 尺寸较大的盘子不能放置在较小的盘子顶上 汉诺塔 此处的问题是我们必须在遵循某些规则的情况下将 n 个盘子从 A 柱移动到 C 柱上 我们可以采取一系列移动，使某个柱子（例如 A、B 或 C）顶部的盘子放置在其它某个柱子的顶上，以此来实现任务 然而，我们应该注意不能把尺寸较大的盘子放置在较小的盘子上 一次移动可以被指定为一条用以下形式表示的指令：将 X 柱最上面的盘子移到 Y 柱上 汉诺塔 下面是可能的移动： 将 A 柱最顶端的盘子（最小的盘子）移到 C 将 A 柱上最顶部的盘子（现在是尺寸中等的盘子了）移到 B 柱 将 C 柱最顶端的盘子（最小的盘子）移到 B 将 A 柱最顶端的盘子（最大的盘子）移到 C 柱 将 B 柱最顶端的盘子（最小的盘子）移到 A 柱 将 B 柱上最顶部的盘子（尺寸中等的盘子）移到 C 柱 将 A 柱最顶端的盘子（最小的盘子）移到 C 柱 汉诺塔 要解决这个难题，有一些条件必须要遵守： A 柱上最大的盘子应该移到 C 柱的底部，这是它的最终目的地 仅当它上面所有的盘子都从 A 柱移开了，这才是可能的 同时，当最大的盘子可以自由移动时，C 柱必须是空的，这样我们才可以将最大的盘子从 A 柱移到 C 柱上。 请务必注意：正如前面所提及的那样，要将最大的盘子从 A 柱移到 C 柱，其它所有盘子都必须在 B 柱上（并且没有盘子放置于比它小的盘子上） 汉诺塔 假设有三个名为 from、to 和 temp 的变量，以便帮助我们开发出一种算法，并最终生成一个 C 语言函数 from 和 to 的值可以是 1，2 或 3。从目前的解释来看，我们已经知道 temp 的值可以根据 from 和 to 的值计算得到 假设三个柱子的号码是 1，2 和 3。这三个数字的和是 6。这将导致下面的关系： from + to + temp = 6 所以，temp = (6 - from - to) 汉诺塔 当 n = 1 时，只需一次移动就可以完成传送了（例如，将唯一一个盘子从初始柱子移动到最终那根柱子上） 当 n 1 时，我们可以通过以下移动将 n 个盘子从 A 柱移动 C 柱： 使用 C 柱作为临时位置，将 (n - 1) 个盘子从 A 柱传送到 B 柱 现在，A 柱只有一个盘子了，即最大的盘子。 将该盘子从 A 柱移到 C 柱 使用 A 柱作为临时位置，将 (n - 1) 个盘子从 B 柱移到 C 柱 汉诺塔 在传送期间盘子驻留其上的临时柱子为 temp，我们可以如下计算出它： Temp = 6 - from - to 要将 n 个盘子从 from 柱移动到 to 柱，我们首先要检查 n = 1 是否成立。如果成立，那么解决方法很简单，只需要一次移动而已。 如果不成立，就如下将问题分解成三个子问题，并依次解决它们： 将 n - 1 个盘子从 from 柱移到 temp 柱 将 1 个盘子从 from 柱移到 to 柱 将 n - 1 个盘子从 temp 柱移到 to 柱 小结 了解递归 讨论为使递归函数正确工作而必须满足的各种条件 描述递归函数在执行时如何工作 理解堆栈在递归函数执行过程中