视频字幕
递归是一种强大的编程技术,其中函数调用自身来解决问题。递归有三个关键特点:基本情况,即不需要进一步递归的最简单情况;递归情况,将问题分解为更小的子问题;以及递归调用,函数调用自身。递归树展示了问题如何被分解,而阶乘函数是递归的经典例子。
汉诺塔是一个经典的递归问题。问题中有三根柱子和若干个不同大小的盘子,开始时所有盘子按从大到小顺序叠放在第一根柱子上。游戏规则要求每次只能移动一个盘子,且大盘子不能放在小盘子上面。目标是将所有盘子从第一根柱子移到第三根柱子上。图中展示了三个盘子的汉诺塔问题的初始状态、中间状态和最终状态。
汉诺塔问题可以通过递归优雅地解决。递归解法分为基本情况和递归情况。基本情况是当只有一个盘子时,直接将其从源柱移到目标柱。递归情况分三步:首先,将上面n-1个盘子从源柱移到辅助柱;然后,将最大的盘子从源柱移到目标柱;最后,将n-1个盘子从辅助柱移到目标柱。代码实现了这个递归算法,而右侧图表展示了递归调用的层次结构。
让我们看看3个盘子的汉诺塔问题的完整移动过程。根据递归算法,总共需要2的n次方减1次移动,对于3个盘子,就是2的3次方减1,等于7次移动。具体步骤是:将盘子1从A移到C,将盘子2从A移到B,将盘子1从C移到B,将盘子3从A移到C,将盘子1从B移到A,将盘子2从B移到C,最后将盘子1从A移到C。通过这7步,所有盘子都按照规则成功地从A柱移动到了C柱。
总结一下我们所学的内容:递归是一种强大的问题解决方法,它将复杂问题分解为更小的同类子问题。递归算法必须包含基本情况作为终止条件,以及递归情况来处理一般情况。汉诺塔问题是递归的经典应用,完美展示了问题分解的优雅性。对于n个盘子的汉诺塔问题,需要2的n次方减1次移动才能完成。递归思想不仅限于汉诺塔,它广泛应用于算法设计、数据结构和各种编程任务中。