视频字幕
递归是编程中的一种重要思想，指的是函数调用自身来解决问题。就像俄罗斯套娃一样，大的套娃里面包含着小的套娃，大问题可以分解为相同类型的小问题。递归有两个核心要素：基础情况作为递归的终止条件，以及递归情况让函数调用自身处理更小的问题。
递归函数的工作原理基于调用栈机制。当递归函数被调用时，系统会在内存中创建一个新的栈帧，用来存储该次调用的参数和局部变量。每次递归调用都会在栈顶添加新的栈帧，形成调用栈。当函数执行完毕返回时，对应的栈帧会被销毁。这个过程包括分解问题、递归调用和合并结果三个阶段。
阶乘函数是递归的经典例子。数学上，n的阶乘定义为n乘以n减1的阶乘，基础情况是0的阶乘和1的阶乘都等于1。让我们看看计算5的阶乘的完整过程：首先调用factorial(5)，它需要计算5乘以factorial(4)的结果，然后继续递归调用直到factorial(1)返回1，最后逐层返回并计算出最终结果120。
斐波那契数列是另一个经典的递归例子。数列中每个数都是前两个数的和，递归关系为F(n)等于F(n-1)加F(n-2)，基础情况是F(1)和F(2)都等于1。但是这种递归实现存在严重的效率问题，因为会产生大量重复计算。比如计算F(5)时，F(3)会被重复计算多次，随着n增大，重复计算呈指数级增长。
设计递归算法需要遵循三个关键步骤。首先要明确递归函数的功能定义，清楚函数要解决什么问题。其次要寻找递归关系，即如何将大问题分解为相同类型的小问题。最后要确定基础情况，也就是递归的终止条件，这是防止无限递归的关键。常见的错误包括缺少基础情况、递归关系设计错误，以及可能导致的栈溢出问题。