视频字幕
递归是一种编程技术，指一个函数或过程在执行过程中调用自身。递归通常用于解决可以分解为更小、结构相似的子问题的问题。以阶乘函数为例，当我们计算n的阶乘时，如果n等于0，直接返回1；否则，我们返回n乘以n-1的阶乘。这里，函数factorial调用了自身，但参数变小了，最终会到达基本情况n等于0，递归终止。
递归有两个关键要素：基本情况和递归步骤。基本情况是递归的终止条件，确保递归不会无限进行。递归步骤是函数调用自身的部分，但问题规模变小。以计算3的阶乘为例，我们首先调用factorial(3)，它依赖于factorial(2)，而factorial(2)又依赖于factorial(1)，factorial(1)依赖于factorial(0)。当到达基本情况factorial(0)时，直接返回1，然后逐层返回计算结果：factorial(1)返回1乘以1等于1，factorial(2)返回2乘以1等于2，最后factorial(3)返回3乘以2等于6。如果没有基本情况，递归将无限进行，导致栈溢出错误。
递归在编程中有广泛的应用场景。首先，递归非常适合处理树形结构，如文件系统遍历。当我们需要列出目录中的所有文件时，可以递归地遍历每个子目录。其次，递归是分治算法的基础，如归并排序和快速排序，这些算法将大问题分解为小问题，然后合并结果。递归也常用于动态规划问题，如计算斐波那契数列或解决汉诺塔问题。最后，递归是回溯算法的核心，用于解决迷宫问题或八皇后问题等需要尝试多种可能性的场景。在文件系统遍历的例子中，我们定义一个traverse函数，它打印当前路径，然后检查是否为目录，如果是，则递归遍历其中的每个项目。
递归和迭代是两种不同的编程方法，各有优缺点。递归通过函数调用自身来解决问题，代码通常更简洁易读，特别适合处理树形结构和分治问题。但递归可能导致栈溢出，且由于函数调用的开销，效率通常较低。迭代则使用循环结构来重复执行代码，虽然代码可能更复杂，但通常效率更高，不会导致栈溢出，适合简单的重复操作。以计算斐波那契数列为例，递归实现非常简洁：如果n小于等于1，直接返回n；否则，返回fib(n-1)加上fib(n-2)。而迭代实现则使用循环和变量来跟踪计算过程。在性能上，计算第35个斐波那契数，递归方法可能需要9.5秒，而迭代方法不到0.001秒，这是因为递归方法重复计算了许多子问题。
总结一下，递归是一种函数调用自身的编程技术，它将复杂问题分解为更简单的子问题。递归必须包含两个关键要素：基本情况作为终止条件，以及递归步骤使问题规模逐渐减小。递归特别适合处理树形结构、实现分治算法和解决回溯问题。虽然递归代码通常更简洁易读，但由于函数调用的开销，效率可能较低，且存在栈溢出的风险。在实际应用中，我们需要根据具体问题权衡使用递归还是迭代方法。理解递归思想对于解决复杂问题和提高编程能力非常重要。