视频字幕
递归是一种强大的编程技术，其中函数调用自身来解决问题。递归有三个关键特点：基本情况，即不需要进一步递归的最简单情况；递归情况，将问题分解为更小的子问题；以及递归调用，函数调用自身。递归树展示了问题如何被分解，而阶乘函数是递归的经典例子。
汉诺塔是一个经典的递归问题。问题中有三根柱子和若干个不同大小的盘子，开始时所有盘子按从大到小顺序叠放在第一根柱子上。游戏规则要求每次只能移动一个盘子，且大盘子不能放在小盘子上面。目标是将所有盘子从第一根柱子移到第三根柱子上。图中展示了三个盘子的汉诺塔问题的初始状态、中间状态和最终状态。
汉诺塔问题可以通过递归优雅地解决。递归解法分为基本情况和递归情况。基本情况是当只有一个盘子时，直接将其从源柱移到目标柱。递归情况分三步：首先，将上面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次移动才能完成。递归思想不仅限于汉诺塔，它广泛应用于算法设计、数据结构和各种编程任务中。