宏观角度认识递归
听到递归，不少人都会对此充满些迷惑，今天我们就从不同的角度来认识递归，消除恐惧。
递归，简单来说，就是函数自己调用自己的情况，也就是在一个主问题中，我们会引申出一个相同的子问题，子问题继续引申下去，还是一个相同的子问题；
此处以二叉树中的后序遍历来借以理解：要先对根结点的左节点和右节点依次遍历，然后再遍历自身节点；
1. 将 1 作为根结点，依次遍历其左子树和右子树，再遍历 1 ；
2. 将 2 作为根结点，依次遍历其左子树和右子树，再遍历 2 ；
3. 将 4 作为根结点，依次遍历其左子树和右子树，再遍历 4 ；
......
类似于这种情况，每一个子问题，都是与主问题类似的，也就是每个子问题的执行方法都是相同的，就可以运用到递归了；
认识了递归后，我们要学会从另外一个角度来看递归：宏观角度看待递归的过程，以往的情况我们可能都会去画图来帮助理解，这也是一种好办法，但有时候会局限于这个思维；
所谓的宏观角度看待递归可以理解为三个点：
1. 不要太在意递归的细节展开图；
2. 把递归的函数当成一个黑盒；
3. 要坚信这个黑盒函数一定可以完成任务；
利用宏观角度思想来写递归：
1. 找到相同的子问题 -> 定义出函数头；
2. 针对一个子问题来理解是如何解决的 -> 定义出函数体；
3. 针对函数的出口做一下出口，避免死循环；
利用这个思想，对于二叉树的后序遍历来写一个伪代码：
1. 对于二叉树的后序遍历，它的主问题和子问题都是对于一个根结点，进行左子树遍历，然后右子树遍历，最后根结点自身遍历，因此这个问题就需要到了根结点的位置，才有办法去找到左右子树的位置从而去遍历，所以函数头可以定义为：void dfs(TreeNode* root)；
2. 通过上述对于子问题的描述，我们就要先对左子树遍历，然后右子树遍历，最后遍历自身节点，因此函数体可以这样来定义：dfs(root->left); dfs(root->right); printf(root-val); 此处就体现了宏观思想了，要对这个函数当成一个黑盒的，不用去过于在意它的细节展开；
3. 最后要考虑函数的出口，也就是当节点为 null 的时候，要直接return，因此添加条件：
if(root == null) return;
所以伪代码可以写为：
void dfs(TreeNode* root)
{
if(root == null) return;
dfs(root ->left);
dfs(root -> right);
printf(root->val);
}汉诺塔问题
面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）
先考虑圆盘为 1,2 两种情况进行分析：当圆盘数量为 1 的时候，可以直接放到 C 柱子上；
当圆盘数量为 2 的时候，就需要借助到 B 柱子来完成摆放了；
再考虑圆盘为 3 的情况进行分析：当圆盘数量为 3 的时候，观察下图，我们可以看出具体的流程：先将上面的两个盘子借助 C柱子 摆放到 B柱子上，然后最大的盘子再到 C 柱子上，最后 B 柱子上的两个盘子，再借助于 A 柱子回到 C 柱子上；
此时仔细思考，三个圆盘的时候， 要对最顶上的两个圆盘进行放置于 B 位置，这个操作就相当于当圆盘为 2 的时候的操作了。此时主问题的解决办法就和子问题的解决方法形成相似的情况了，也就是可以使用递归了。
因此，当有 n 个圆盘的时候，统一的解决办法都是如此：
1. A柱子上的 n-1 个圆盘借助于 C柱子，放到 B柱子上；
2. A柱子底下最大的圆盘放到 C柱子上；
3. B柱子上的圆盘借助于 A柱子放到 C柱子上；
1. 针对重复的子问题，定义函数头：
bfs(List<Integer> A, List<Integer> B, List<Integer> C,int n)
A,B,C 集合依次表示A集合借助于B集合移动到C集合上 + 针对A集合上n个圆盘进行移动；
2. 针对子问题进行理解，定义函数体：
2.1 将 A 上的 n-1 个圆盘借助于 C 移到 B 上：bfs(A,C,B,n-1);
2.2 将 A 上的最后一个圆盘移到 C 上；
2.3 将 B上的 n-1 个圆盘借助于 A 移到 C上：bfs(B,A,C,n-1);
3. 考虑出口的设计：
此时就要考虑圆盘数为 1 时的处理方式：将 A 上的圆盘直接放置于 C 上；
完成代码
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
bfs(A,B,C,A.size());
}
public void bfs(List<Integer> A, List<Integer> B, List<Integer> C,int n){
// 出口设计,当只有一个圆盘的时候，直接从 A 移动到 C
if(n == 1){
C.add(A.remove( A.size() - 1 ));
return;
}
bfs(A,C,B,n-1); // 1. 将 A 上的 n-1 个圆盘借助 C 放置 B 上
// 注意此处 A 的最后一个圆盘不能直接写 [0]
// 因为在递归的过程中，针对的是某个子问题
C.add(A.remove( A.size() - 1 )); // 2. 将 A 上的最后一个圆盘，放到 C 上
bfs(B,A,C,n-1); // 3. 将 B 上的 n-1 个圆盘借助 A 放到 C 上
}
}
