递归
递归的思路基本就是把一个大问题拆分成相同分量的小问题。
我们来举一个例子吧。
假设你是一个非常懒的总监，你上司给了你100份文件去处理。与其说你自己把所有的文件都处理了，你的做法是：
从100张纸最上面抽一张来处理，然后把剩下的99张推给你的助理。
然后你的助理也跟你一样懒。他采取了与你一样的策略：处理最上面的文件，然后把剩下的所有交给他的助理。
这样的一个链式反应到最后一位实习生，他发现他的上司给了他0份文件处理。这位实习生说“我手里没有文件了”，于是文件的处理结果就从后往前层层上报给你。到最后答案传给你的时候，100份文件的结果就已经全部累加给你了。
这样一番操作就叫做递归。我们可以用这样一个公式来表示：
$$f(n) = f(n-1) + n$$
其中，$n$就是你负责的那份文件，而$f(n-1)$就是你推给你助理的工作。
基准条件
后文都用Base Case来指代这个名词，因为基准条件听起来很怪。
递归的危险之处就是，你的问题可能永远不会结束。例如在上面的例子中如果在0份文件之后出现了-1份文件，那么你就别想着得到最后的结果了。
在编程的世界中，我们管这样的情况叫做栈溢出 (Stack Overflow)。
这就是为什么在递归编程中，我们要选择一个合适的Base Case，来告诉计算机我们什么时候开始向前返回结果。递归的每个子循环前，我们都需要根据Base Case来检查一下：这个子问题到底够不够简单，导致我能直接知道这个子问题的结果？
人话讲在刚才的例子中，Base Case就是：$n = 0$。
当你在编写递归代码的时候，永远将你的Base Case写在最前面。这样你就在最大限度上避免了栈溢出问题。
调用栈
调用栈 (Call Stack) 是追踪递归程序运行的栈——一种数据结构。
每次你在递归中调用了一个子进程，例如$f(2)$调用了$f(1)$，计算机就需要先暂停$f(2)$的计算，把它的计算过程“暂存”起来，放在一边（放在栈里）。随后，我们进行$f(1)$的计算。
如果你的递归函数需要1000个子进程，那么你的调用栈里就存放了1000个进程，能吃掉你不少内存。即便我们不创建新的数组变量，递归也需要$O(n)$的内存复杂度来跟踪这些“暂停”的进程。
$O(n)$是复杂度的表示。有关复杂度的内容会放在后面去讲。
回溯算法
回溯 (Backtracking)，或者有些教材叫做排列 (Permutations)，是递归的一个进阶使用场景：
给定了一个数组[a, b, c]，你的目标是输出数组中所有元素可能的排列样式：abc, acb, bac, bca, cab, cba。
我们可以按照这样的思路来解决问题：
- 将
a的位置固定在数组的最前面，随后找出[b,c]的所有排列 - 同理固定
b的位置，然后找出[a,c]的所有排列 - 固定
c找[a,b]
与其使用基础的递归算法，我们需要在某处重置外层程序的状态。我们的程序大概要按照这样的方式去运行：
- 将
a换到前面，然后调用递归 - 递归被调用后，下一步就是将
b换到前面。不过需要注意的是在将b置顶之前，我们需要撤回我们在第一步中做的动作，也就是将a的位置重置，将数组状态归零。
像这样的步骤，我们管它叫回溯 (Backtracking)：这是一个计算-递归-归位的逻辑。
自测
读者不妨来尝试一下下面的几个问题，来测试自己对该章节的理解是否到位：
有这样一个递归程序，作用是反转任何输入数组。例如:
输入：[5, 3, 1, 4, 8]
输出: [8, 4, 1, 3, 5]
a) 设计该递归程序
b) 如果数组有100个元素，那么调用栈里面会堆积多少子进程？
a) 题解
首先交换首位两个元素。[5, 3, 1, 4, 8] → [**8**, 3, 1, 4, **5**]
下一步对中间的元素使用递归。
不妨设两个指针：$p$为头指针，$q$是尾指针。$A$是输入数组。
Base Case：当$p \geq q$时，代表指针在中间相遇。出现这个情况就代表我们应该终止程序了。
Base Case检查后，我们就可以交换A[p]和A[q]的位置了。
交换后，我们移动指针：将$p = p + 1, q = q - 1$，然后对指针内的元素调用递归。
b) 题解
因为每次子进程会在数列中减去首尾两个元素，因此深度为$n/2$。答案是50。
继续使用例Cpt.1.1：
给定了一个数组[a, b, c]，你的目标是输出数组中所有元素可能的排列样式：abc, acb, bac, bca, cab, cba。
如果我们在回溯阶段，忘了做关键的回溯步骤，那么输出行数将会更多，还是程序会输出相同行数的输出，但是内容完全错误？
题解
输出同样数量的行数，但是结果错误。