##### 递归 - 递归 - **递归**是一种在对象中进行[[自指]]的[[数学定义]]结构, 即将对象定义为自身的一个或多个实例, [[自然数]]的[[递归定义原理]]保证递归定义是唯一存在的. 递归在逻辑学, 数学和计算机科学中广泛应用, 尤其是在定义序列, 函数和数据结构时, 有[[递推关系]], [[递归函数]]等, 通常包括基本情况和递推步骤两个部分 - 基本情况, 定义对象的最简单情形, 直接给出值或定义, 这是递归的终止条件 - 递推步骤, 定义对象时使用更小规模的相同类型的对象, 这是通过自我引用来给出更复杂的对象定义 >[!example]- 递归 > - 阶乘 $n!$ > - 基本情况, $0! = 1$ 或 $1! = 1$ > - 递归步骤, 对于 $n > 1$, $n! = n \cdot (n-1)!$ > - $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 = 6$ > - 斐波那契数列 $F(n)$ > - 基本情况, $F(0) = 0$, $F(1) = 1$ > - 递归步骤, 对于 $n \geq 2$, $F(n) = F(n-1) + F(n-2)$ > - $F(4) = F(3) + F(2) = (F(2) + F(1)) + (F(1) + F(0)) = (1 + 1) + 1 = 3$