# 从递归到递推
我们其实生活在一个并不大的空间中，因此对这个世界的认识是由近及远、从少到多，一点点展开的，这也是我们固有认知的思维方式，这样的认知和思维方式能够让我们很容易理解具体事务，但限制了想象力和大局观。当需要思维触达那些远离我们生活经验的地方时，我们就会出现理解障碍，比如至今很难理解相对论，怎么也想不通光速为什么是恒定的。
和人不同，计算机在一开始就被设计用来处理大规模问题，因此计算机可以采用与常人完全不同的方式来解决问题。如果一个人能够站在计算机的角度去思考问题，可以称他有“计算思维”，如果一个人在做事时采用的是计算机解决问题的方法，我们会认为他有了计算机的方法论。在计算思维中，最重要的是一种自上而下、先全局后局部的逆向思维，它被称之为递归，与之相对应的是自下而上，从小到大的正向思维，它被称之为递推。
# 递归
要说清楚什么是递归，就要先说说递推。递推是人类本能的正向思维，我们学算术，从0数到100就是典型的递推。递推就是从小到大，从易到难，从局部到整体。用递推计算5!，其实就是1✖️2✖️3✖️4✖️5，递归则是把这个过程倒过来，比如要计算5!，那么就会假设4!是已知的，5!=4!✖️5，以此类推到1!，当我们知道它等于1就不再往下拓展了，接下来就倒推所有结果进行计算。
递归的思想只需要解决当前第一步的问题，就能解决全部问题，比如计算N的阶乘时，只需要关心N乘以某个数就行了，这个数就是（N-1）!,至于（N-1）!怎么算可以复制同一个过程。这就意味着它有两个前提条件，一个是每一个问题在形式上相同，另一个是必须要确定好结束条件。下面是一道很好玩是递归题目：
你和一位对手来做一个游戏，你们其中一个人先从1和2中挑一个数字，另一个人则在对方的基础上加1或加2，然后又轮到前面的人再次选择加1或加2，如此往复交替，谁正好加到20，谁就赢了，有什么策略可以保证自己一定能赢？
这个问题如果从小往大考虑就会比较有难度，但是倒过来想就会变得简单。想要抢到20就要先抢到17，因为抢到17以后，不管对方是加1还是加2，我们都能加到20。二想要抢到17，就要抢到14，以此类推就必须要抢到11、8、5、2，对于这个问题，先出2就赢定了，这就是递归思想。
# 汉诺塔
在计算机科学中，很多复杂问题不是数学问题，而是要通过一系列的操作来完成，比如对一个序列进行排序，分析自然语言，规划行驶路径，实现两类集合之间的匹配等等。这些问题常常也要用到递归思想。下面是一个经典的递归问题：
有三根柱子，A、B和T。A柱子上摞着N个盘子，小的放在大的上面，接下来按照下列规则将所有的盘子从A柱移动到B柱。
- 每次只能移动一个盘子。
- 任何时候小盘子都不能放在大盘子下面。
- T柱可以临时摆放盘子，但盘子的次序也不能违反第2条原则。
如何能将这些盘子从A柱移动到B柱？N=1的时候比较简单，直接将唯一的那个盘子从A柱移到B柱即可，记作A1->B1。N=2时也比较直观，先将A柱上的小盘子临时存放到T上，再将A柱上的大盘子移到B柱上，最后将T柱上的小盘子移到B柱上。上述的过程可以总结成三步：
- A1->T1
- A2->B2
- T1->B1
用递归的思想来总结这个过程就是Hanoi（N，起始点，目的地，中间临时存放位置）,代码如下：
void Hanoi(n,source,target,auxiliary) {
if(n > 0) {
Hanoi(n-1,source,auxiliary,target);
MoveTop(source,targer);
Hanoi(n-1,auxiliary,target,source);
}
}
# 遍历
在计算机中，树是一种抽象的数据结构，它有根，有枝干，还有叶子，这种数据结构有一个根节点，根节点下面可以有一些子节点，子节点下面还可以再有自己的子节点，对于不再有子节点的节点，也被称为叶子节点。
树本身严格的定义就是递归的，它包含两层含义，首先一个单独的节点本身就是一棵树，其次，任何一课树都有一个根节点，根节点下面有一些子树。这第一种情况就定义了递归的结束条件，第二种条件定义了树和它下面子树的递归关系。
我们经常会用到二叉树，二叉树中每一个节点的子树不超过两颗，因此人们习惯用左、右子树来区别他们，左右子树的节点就是左、右子节点。二叉树使用比较广泛的原因主要是它的子节点少，相对简单，另外这个结构很贴近日常的是非逻辑，又符合二进制。其实从本质上来看，任何树都可以是二叉树。
在实现递归算法时，我们需要从顶部到底部的很多中间状态一一保留，在走到最底部的时候，完成最基本的操作，然后根据保留下来的中间状态一一回溯，为了配合这类的算法，后进先出的数据结构应运而生，我们把这种数据结构称为“堆栈”。
为了理解堆栈，可以回顾一下汉诺塔问题，如果我们想要挪动第N个盘子，就要先挪走上面N-1个盘子，最初进入堆栈的是Hanoi（N,A,B,T）直到Hanoi（1,A,B,T）。最顶上的Hanoi（1,A,B,T）先被执行，然后依次执行，当所有都执行完毕后，栈清空。
计算机处理问题时，常常要把一个大问题自上而下的分解成很多小问题，一个个拆解开，分别解决之后，再得出整体答案，堆栈能够记录中间一步步分解复杂问题的过程，它先进后出的特点可以很自然的讲分解的问题合并。我们在调试一个程序，了解程序内部的复杂调用关系，其实都是通过堆栈来实现的。
# 嵌套
递归的特点是嵌套，就像俄罗斯套娃，递归其实也是嵌套的特例，它套的永远是自己。一个可以单独运行的主函数往往是一个空壳，通过调用真正的功能模块完成其任务，在功能模块中，整个程序要完成的功能被分解为一个个独立模块，它们之间可以相互调用，最后实现整个程序的设计功能。所以在编程的过程中，整个程序的设计思路应该是遵循自顶而下的递归原则，而不是按照流程顺序执行的流程一步步进行。
随着计算机发展，程序变得越来越复杂，一个大程序有上百万行代码，因此作为开发人员很难将程序的全部步骤想清楚，所以只能把大框架梳理一下，然后再层层递进的解决细节问题。为了防止一个细节影响到其他步骤，每一个模块都要封装好，为了使这些模块能够重复使用，最好一个模块只完成一个功能，如果要用到其他功能，就调用另一个模块，这样一来，整个程序就是嵌套的。初期面向对象和模块化设计，就是这么来的。
今天ChatGPT很火，其实它依赖的一个核心技术就是自然语言处理，自然语言处理的语法分析就是把一句话，一级一级的分析出语法结构，知道了不同的语法结构才能把人的语言提炼出明确的含义，提炼出不同概念之间的相关性，建立知识图谱。早期的自然语言处理，其实也是运用了嵌套的思维处理问题的。下面是一组经典的英语语法规则：
- 句子 = 主语部分 + 谓语部分
- 主语 = 定语 + 名词短语
- 定语 = 名词短语 | 形容词短语
- 名词短语 = 形容词 + 名词 | 名词
- 谓语部分 = 谓语 + 宾语
- 谓语部分 = 谓语 + 状语
- 宾语 = 句子 | 名词短语
- 状语 = 副词 + 动词
这上面每一条规则都可以被称为重写规则，也就是说左边的句子成分可以被右边的一个或一组句子成分代替。通过这些规则我们不难看出，句子其实是从上往下嵌套的，它们可以互相嵌套，比如一个句子可能包括宾语，而宾语可能又包含一个句子。