递归，一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的。
核心原理和前提条件
递归的核心原理
递归的本质是**“大事化小”**，它通常包含两个阶段的过程：
- 递推（向下拆解）： 函数将一个复杂的大问题，分解为一个或多个规模更小的、与原问题性质相同的子问题。这个过程不断重复，直到问题小到可以直接得出答案。
- 回归（向上回溯）： 当最底层的子问题（基准情形）得到解决后，答案会沿着调用栈一层一层地返回，供上一层函数使用，最终解决最初的大问题。
[!NOTE]
==🖥️ 内存中的运作机制：调用栈 (Call Stack)==
在计算机底层，递归是依靠**栈（Stack）**这种数据结构来实现的。
- 每次函数调用自身时，系统会把当前函数的状态（局部变量、返回地址等）压入栈中（称为“压栈”）。
- 当遇到终止条件后，函数开始执行完毕，状态从栈顶弹出（称为“出栈”），并将结果返回给上一层。
- 如果递归层数太深，栈空间被耗尽，就会发生**“栈溢出”（Stack Overflow）**错误。
递归的前提条件
-
边界
不需要递归就可以解决的简单问题，或者说我们约定俗称的东西。如斐波那契数列中，n=0和n=1的情况。
-
递推关系
将“大事”化为“小事”的方法。如我们知道F
n=Fn-1+Fn-2。==我们需要主要，递推关系要往边界推进，不然会进入死循环==
[!WARNING]
说一个重要的事，不要去想F
n到底怎么实现的，也就是递归的具体实现过程。这是一个真实的故事，本人在写该笔记时为了写的仔细一点，曾思考过递归究竟怎么实现的，茶不思饭不想白白浪费了一周的时间，重新看了教程才发现，没人研究这个。
==千万不要思考递归的实现原理，轻则走火入魔白白浪费时间，重则修为全废失去学习动力==
时间与空间复杂度分析
| 递归类型 | 时间复杂度 | 空间复杂度 | 分析说明 |
|---|---|---|---|
| 线性递归 | O(n) | O(n) | 每次递归调用一次自身，递归深度为n。典型例子：阶乘计算 return n * fact(n-1)，单链表遍历。时间复杂度由递归深度决定，空间复杂度等于递归深度。 |
| 分治递归 | O(n log n) | O(n) 或 O(log n) | 每次递归调用多个自身，问题规模减半。典型例子：归并排序 T(n) = 2T(n/2) + O(n)。时间复杂度由递归深度和每层工作量决定，空间复杂度取决于递归深度和合并过程的额外空间。 |
| 指数级递归 | O(2ⁿ) | O(n) | 每次递归调用多个自身且存在大量重复计算。典型例子：朴素斐波那契 return fib(n-1) + fib(n-2)。时间复杂度呈指数级增长，空间复杂度由递归树的最大深度决定。 |
| 尾递归 | O(n) | O(1) 或 O(n) | 递归调用是函数的最后一个操作。典型例子：尾递归阶乘 return factorial_tail(n-1, n*acc)。若语言支持尾调用优化，空间复杂度可降至O(1)，否则仍为O(n)。 |
| 记忆化递归 | O(n) | O(n) | 使用缓存存储中间结果避免重复计算。典型例子：记忆化斐波那契 if n in memo: return memo[n]。时间复杂度从O(2ⁿ)降至O(n)，但空间复杂度仍为O(n)。 |
| 二分查找递归 | O(log n) | O(log n) | 每次递归将问题规模减半。典型例子：binary_search(arr, l, mid-1, x)。时间复杂度与迭代版本相同，但空间复杂度增加为O(log n)。 |
| 树遍历递归 | O(n) | O(n) | 递归深度等于树的高度。典型例子：二叉树前序遍历 preorder(node.left); preorder(node.right)。最坏情况下（单链结构）空间复杂度为O(n)。 |
| 汉诺塔问题 | O(2ⁿ) | O(n) | 典型的指数级递归问题。递推式：T(n) = 2T(n-1) + O(1) = O(2ⁿ)。空间复杂度由递归深度n决定。 |
思路和步骤
干讲着没意思，我们来看具体例子：
-
乘阶
我们想知道n！，虽然直接求很难，但如果我们知道了（n-1）！我们就可以知道n! = (n-1)! * n,
这时候我们就只要知道（n-1）!就可以了。
刚好我们可以知道1！就是1。
我们便可以实现一个方法：如果我们得到了1，那便返回1。
若是其他数n，便返回（n-1）！ * n。
只要方法向着边界1收敛。我们就可以相信（n-1）！一定会实现
int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } -
斐波那契数列
篇幅有限，就跳过小兔子的故事
我们直接假设有：
1 2 3 4 5 6 1 1 2 3 5 8 我们如果想要知道第n个数是什么，我们需要看第（n-1）和第（n-2）的数，两数之和便是第n个数，而第一和第二个数是1
我们可以推出：F(1)=1, F(2)=2, F(n)=F(n-1)+F(n-2)
可以发现，我们已经得到了边界和递归关系，并且递推关系是往边界推进的。
我们便可以：
int fib(int n) { if (n <= 2) return 1; return fib(n-1) + fib(n-2); }
[!CAUTION]
在斐波那契数列实现中，我们在一个函数中一次调用了两次自己，这意味着fib（n-2）将在fib（n-1）中再次调用一次，重复实现已经实现的方法，这将浪费我们的内存。
所以我们可以将已经求出的数值保存起来，防止重复求值。