#学习笔记
第2周-第5课 | 哈希表、映射、集合
1. 哈希表、映射、集合的实现与特性
- Hash table
- 哈希表，也加散列表，是根据关键码值（key value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫作散列表（Hash Function）,存放记录的数组叫做哈希表（或散列表）。
- 通过哈希函数就会把要存储的值，能够映射到一个位置，这里的位置就是它的下标index，任何一个对象或者数据传进来，它就会映射到一个int的下标，然后放在这个数组中即可，不然就没办法有效地放。
- 现实中应用的列子：
- 比如说经常要存一些数据的话，根据一个人或者根据某一个具体的，而不是根据一个数字来存它的相对应的信息。比如人有他的地址信息，电话号码信息还有其他各种信息等。就以这个人的人名或者他的身份证号作为比如他的ID，然后后面就记录他各种信息。
- 还有用户信息表以及后续的缓存，还有键值对的存放，这里就是Redis，现实中写后端的都会使用，这些结构里面都是用了大量的哈希表。
- 哈希表的基础实现原理
- 首先要有存储的值，如何存呢？就有一个像哈希函数这样一个东西，要存储的值传给哈希函数之后，它就会返回一个下标，这个下标就是整数，就把这个值存在返回下标的这个位置，这样存下来即可。要存储的值的下标为什么会对应返回的下标的呢？就是所谓的哈希函数，这个哈希函数可以有很多种，在Java里面的话，基本有一个叫Hash Code的方法，需要重载一下。
- 现实中的哈希函数其实相对来说较为复杂，而且哈希函数选的好的话，可以让这些数值尽量的分散，而不会发生所谓的碰撞。
- 不同的字符串最后算出来发现都是相同的数，像这种情况叫做哈希碰撞。
- 现在比较火的区块链、比特币以及大数据的技术里面经常要用到所谓哈希表。
- 这里所谓的哈希碰撞也就是说对于不同要存储的数据，它经过哈希函数之后会得到一个相同的值，对应的下标都是在相同的位置，怎么办呢？
- 这种情况很常见，下标相同的话就说明，这个下标位置要存多个元素，我们要做的事情也比较简单，其实有几种办法。
- 一个的话就是一次往下面存占别人的位置，最好的一种方式或者是相对在工程上常用的一种方式，就是再增加一个维度，这个位置不止存一个数了，而是存多个数，也就是从这里开始拉出来一个链表，这样的方法叫做拉链式解决冲突法。
- 那么在冲突位置拉出一个链表。把都应该放在这个下标位置的元素，依次在链表中弄出来，这时候会发现一个数据进来通过哈希得到它的下标的值，这整个操作是O(1)的，也就是O(1)可以查询到它的位置，但是如果很多的元素都积累在相同的位置，这是后哈希表的它的查询时间就要遍历链表，所以这个时间如果链表很长的话，它就会效率进行退化，退化到所谓的O(n)的级别。但是如果设计的比较好的话，哈希函数它的碰撞的概率很少，所以在平均时间的话，可以认为整个哈希函数的查询它是O(1)的。
- 现实中哈希表的完整结构
- 如果发生碰撞之后就拉链拉出来，大部分的位置都是只有一个元素完美哈希的，其他少数的位置会有一些冲突，有冲突的话就把这个元素累加起来就行，就是串联起来形成一个链表即可，这就是所谓的哈希表常见的完整结构。
- 注意：和之前将的优先队列一样，以及后面的红黑树和AVL一样，像哈希表这样的结构，以及常见的哈希函数，都是在工程里面常用的非常常用。所以高级的语言以及标准的库STL、Java的各种库、C++还有出名的Boost的库以及Python各种库，都已经把这些内生就已经实现好了，直接用就行，不要手写。但是要掌握它的使用方式。
- 哈希表复杂分析
- 查询添加删除大部分情况下都是O(1)的，有一种情况就是最坏情况，就是这个哈希函数选的非常不好，或者是哈希表的它的整个size太小了，就导致经常会发生冲突，以一冲突的话它就变成成一个链表了，退化成链表之后，很多时候它的复杂度就退化成O(1)了，这就是它不好的地方。
- 现在计算机内存肯定越来越大，所以哈希表可以开的很大很大，同时哈希函数不断地优化，那么一般来说都可以认为哈希表在正常情况下，就是O(1)的时间复杂度进行查询添加和删除元素。
- 一般用map和set他们的区别是：map就是键值对，key是不重复的，value可以重复。set的话就是不重复的元素集合，它是一个键值对的关系，而这个没有键值对，就是一个单个的元素，这里面单个元素就是不重复的。
- 作业：写一个HashMap的小总结放在课后作业的个人总结里面。
- 复杂度的分析
- 这些高级语言的TreeMap和TreeSet都是使用红黑树来实现的，所以在这里它是严格平衡的红黑树，在所有的操作里都是O(logn)的时间复杂度来实现的。
2. 实战题目解析：有效的字母异位词等问题
- anagram异位词，所谓的异位词指的是它字母出现的次数都是一样的，然后字母组合顺序不一样。
- 切题四件套
- clarification 和面试官把这个题目过一遍。
- possible solutions –> optimal (time & space)从中找出一个最优的 时间和控件的复杂度是最好的
- code 开始写代码
- test cases 进行测试样例的阐述
- 首先不知道anagram异位词的话要和面试官确认一下。
- 就是大小写是不是敏感的，这个要提前给面试官说。
- 暴力法
- 思路：直接把整个字符串按照字符的顺序来sort，sort之后就比较sorted array，string是否相等就行了。它的时间复杂度是O(nlogn)的，这里的n表示字符串的长度。
- 哈希表
- 思路：这个哈希表可以想成它就是一个map，来统计每个字符串的频次，如果这两个字符串，每一个字母它出现的频次都是一样的，那么它肯定就是anagram。
- 根据这种方法其实有一些技术的处理，第一个单词碰到一个字母，它计数就加一，到了第二个单词，碰到相应的计数它的值就进行减一，最后看这个map是否为空。以及要做一件事情，因为它一个ASCII码最大的值就是0到255，就是用一个长度为256的数组来计数，其实它也是一种相当简化了的哈希表，只不过它的哈希函数就是它的ASCII码的值，其实它也是一个哈希表的值。
- 官方题解：排序：直接进行排序。哈希表：就是每个字母来统计它出现频次。
- 加强版本：字母异位词分组
- 思路：先排序之后，用排序后的字母当成它的key，然后存到了一个map里面，最后把这个map的值进行归类了之后输出。
- 两数之和 用哈希表如何求解
- 哈希表关键就是枚举a，这里要a + b = target，其实就可以转换成对于任何一个数组里面的元素a，就枚举a，就要找target - a 这个是不是也在数组里面， 对于for each a，check (target - a)，is exist in this nums array， 关键就是这么一个条件。
- 如何检查是否存在nums里面呢？不用其他数据结构，那就必须在这数组里面在剩下的除了a之外的剩下的元素里面在循环查找，那就变成是O(n)的了。在家外面的循环加载一起，这个算法就变成O(n^2)了。
- 这里关键就在于需要用哈希表，哈希表需要一开始把整个数组都在哈希表里面存一下，那么查询就变成O(1)的了，那么外面的话还是O(n)的，里面查询target - a是否存在，是O(1) 的时间复杂度，整个时间复杂度就进化为O(n)了，也是这个题目的最佳解法。
- 看官方题解，暴力方法试着写一遍。两遍哈希：一开始把所有这些元素都放到哈希表里面去，第二次就判断target - nums[i]是否在哈希表里面，这是它所谓的两遍哈希的方法，它的时间复杂度就已经是O(n)了，虽然是两次，但是它数量级还是O(n)的，所以已经是最优的解法。这里还可以试一遍哈希，其实可以一遍完成再进行迭代并将元素插入到表中的同时，还会回过头来检查变种是否已经存在当前元素所对应的目标元素，如果它存在，那我们已经找到了对应解，并理解将其返回。
- 尝试着把这个代码写一下是否也能够写出来，写完之后参考题解代码，同时参考一下国际站里面的那些国际化大牛，他们的代码是怎样的，和你的代码进行比较。2sum以及3sum还有4sum，这个题目是老生常谈的考试题目，特别高频，以至于后来面试的时候面试官都不好意思出这种2sum题目。
- 养成习惯，一定要主动去看别人的代码学习和得到反馈，要从世界上吸取全世界最精华的代码。看打分最高的，然后和自己的代码比一下，看自己的代码是否是足够简洁的，同时养成简洁的习惯。
- 一种特别好的学习方法：养成收藏精选代码的习惯，对于初学者很有帮助。把有很多不同的方法的题目，全部都把它的要点就是罗列起来，之后每一次面试之前看一下这些代码，这样就养成真正面试的时候下笔如有神，写出来的话就是多种解法，且皆为比较优化的代码。代码中的ord就是任何一个值，任何一个字符，ord得出它的ASCII码值以及其他用不同语言的都把它写在这里。
- 养成总结代码的习惯，形成自己的，至少是基于算法数据结构的一个精选代码库的概念，同时还可以把它放在GitHub上面去，把自己在网上学习觉得不错的代码都放在一个代码库里面。
- 实战题目 / 课后作业
- https://leetcode-cn.com/problems/valid-anagram/description/
- https://leetcode-cn.com/problems/group-anagrams/
- https://leetcode-cn.com/problems/two-sum/description/
第2周-第6课 | 树、二叉树、二叉搜索树
1. 树、二叉树、二叉搜索树的实现和特性
- 数据结构分为一维和二维，树是二维的数据结构。
- 链表的一维结构，链表它有头和尾，而且有个next指针不断地往后指，这叫单链表。如果是双链表，还有一个前继指针往前指，它最大的问题就是在查询的时候太慢，要O(n)的时间复杂度，因为要查询中间的结点或者是第某个节点，它必须从头一个一个往后挪，正是因为这个原因后来就出现了一个叫跳表一样的结构，就加上了更快的索引，比如从头指针直接跨到第二个节点。跳表加速思想：要加速最关键在于升维。也就是二维数据结构。
- 二维数据结构：常见的其实就是树和图。
- 在单链表中，如果它的next指针有很多的时候，它不再是一个next，而是有多个next，有next1，next2，next3指向多个节点的话它就变成一颗树了。
- 树的基本定义以及相应的特点
- 首先要有一个根节点，然后又有左子树和右子树或左儿子又儿子，叫做根节点的儿子节点，整个就叫做子树。相对于儿子节点来说的话，它就有父亲节点。某个节点既可以是父亲节点，同时也可以是某个节点的儿子节点，两个平级的结点就是兄弟结点。可以有不同的层。
- 在现实中用的最多的其实就是二叉树
- 二叉树就是它的儿子节点只有两个。
- 树和图最关键的一个差别是什么？
- 最关键的差别就是看有没有环。如果它这个一个节点本身只连到新的儿子节点，永远都不会走回去，
- 比如说F节点要是还有个一个儿子的指针要指向E，或这是指向了C或者是指向了A的话，那就相当于会形成一个环。形成环的情况下，我们按照定义不称树，而是叫做图。
- 在特殊情况下可以简化地理解为，Linked List 是特殊化的 Tree（因为有两个next指针），Tree是特殊化的Graph（没有环的图就是树）。特殊化的记忆。
- 树节点的定义
- 为什么会出来树这么一个结构？从最外层它的实际生活需求以及工程需求上来讲为什么会出现树。
- 出现树的本质并不是说一维的结构不好用，要变个二维的结构出来炫酷或者怎样，或者是要加速，因为一维太慢了要变成加速这样。
- 因为我们人类本身生活在一个三维的世界里面，四维的世界里面当然也包括了二维。所以人类的很多本身它的工程实践的话，其实就是在二维的基础上要去解决的，而树本身的话就是人经常会碰到的一种情况。就类似于飞机本身并不是人发明创造的，而是看到鸟在飞之后想到的。
- 树本身最常见的一种情况就是在Filbonacci斐波那锲数组求解的时候，暴力递归它的程序就两行代码看起来很简单，但其实它扩散出去的结点其实是一个树状的结点，假设算n = 20的时候画出递归树，这里从20可以扩散出不同的结点，叫做它递归的状态树，简称递归树。它本身就是一个树形结构，像20每次分叉成两个，那么每个相应的结点也分叉成两个，最后就变成一个所谓的递归树的这么一个结构，它本身就是树形的。
- 另外像现在比较火的AlphaGo，以及各种棋类的游戏，不管哪一个选手开始下了之后，棋盘的状态就是向外扩散成不同的状态，每个不同的状态再往下面走，棋盘的状态本身也是一个树形结构。从空棋盘状态开始，每一个人都可以走不同的步，走了之后棋盘就往下继续扩散出不同的状态，形成第二层第三层第四层的树的结点，到了最后的叶子结点就是这个棋盘的某一个终极形态，这个终极形态肯定就是不能再下了，其中有一方赢了或者输了，或者是和棋的状态。
- 而本身的话不同的棋它的树状的空间，我们叫做它的状态树的空间，同时还有一个叫做博弈的空间，也可以叫做decision tree 叫决策树的空间。复杂度不一样，最后决定了这个棋或者这个游戏它的复杂度。
- 经常做的第一件时间就是数的遍历，为什么需要遍历呢？
- 一维的结构数组或者链表，要查询里面的节点，就必须遍历。如果是一颗非常基本的树，它的里面的结点全部都是无序的，要查找一个元素的话就必须要遍历。遍历的话就是把所有的结点都走一遍，如何走呢？其他的数据结构就循环一遍，一直循环到没有。
- 因为树状的话就会有左子树和右子树这么一种情况，那就类似的递归去把它反复的求证。递归的代码就是左中后序遍历，为什么叫这种结构？就是因为要查自己的根节点的值，同时还要访问左子树和右子树，总共需要三句语言，这三句语言的顺序最后就变成了不同的遍历方式。
- 三种不同的遍历方式：
- 前序(Pre-order)遍历：根-左-右
- 中序(In-order)遍历：左-根-右
- 后续(Post-order)遍历：左-右-根
- 整个遍历基本上就基于递归的，为什么基于递归呢？
- 就是树的定义本身的话，它没法有效地进行所谓的循环，其实也可以强行循环，比如说用广度优先遍历，但是很多情况下它这种结构写循环相对比较麻烦，而写递归调用相对比较简单。不同的序的遍历，其实严格老说就四行语句，非常简洁。所以树的各种操作都是基于递归的。
- 一种特殊的树：二叉搜索树Binary Search Tree，为什么要叫二叉搜索树？
- 因为如果只是一个普通的树的话，要查找里面的结点，就必须把它的树给遍历一遍。要遍历的话就是O(n)的算法复杂度，他和一个链表基本上没有太大的区别，会觉得这个没有什么太大意义。一般来说树的结构会把它变得更加有序，查找和维护起来就会更加的有效。
- 二叉搜索树的定义
- 二叉搜索树，也成二叉搜索树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是指一颗空树或者具有下列性质的二叉树：
- 左子树上所有结点的值均小于它的根节点的值；
- 右子树上所有结点的值均大于它的根节点的值；
- 以此类推：左、右子树也分别为二叉查找树。（这就是重复性！！！）
- 中序遍历：升序排列
- 二叉搜索树的常见操作以及效率
- 二叉搜索树的查询和插入都不再是O(n)，而是是O(logn)，所以就相当于加速了。
- 单链表它的插入虽然很快，但它查询都是O(n)的。二叉搜索树用二维结构同时让它有序地排列，不管他的插入操作还有查询操作以及其他操作都是O(logn)的，这样的话就快了很多。
- 常见操作是怎样进行的？
- 如何查询其中一个节点的过程
- 如果这个树是完全无序的话，就只能遍历，不管是用前中后序，最后的时间复杂度平均来说就是O(n)的。
- 既然是二叉搜索树，应该如何遍历？如果它小于根结点说明只要查某一边就行，只要查另一边就行，所以每次都可以筛掉一半的结点。正是因为这个方式，最后它和二分搜索的时间复杂度差不多，就是每次减半，就是O(log2n)的时间复杂度，这就是它加速的一个过程。
- 如果找不到的话，它把路径都走完了之后，发现这个结点最后不在这个树里面，然后返回找不到这么一个过程。
- 如何插入的过程
- 如果要插入一个结点的话，那么首先要做的一件事情，其实就是查找这个结点，查找这个结点如果查找到的话，就把count + 1，要是查找不到的话，就在最后查找到的位置添加这个结点就行了。
- 去查的过程中要是没有查到的话，最后到达的位置就是这个结点需要在的位置。
- 创建的过程
- 一颗空树就是二叉搜索树，关键在于后面怎么创建，也就是把所有的结点依次插入到这颗二叉搜索是树里面去即可，也就是不断地调用插入操即可。
- 删除过程 分两种
- 第一如果是它在叶子上的话删除起来比较简单，直接删除即可，删掉之后树的形态没有发生任何变化。关键的在于就是删的一些结点是一些关键性的结点，就是所谓的比如说根节点或者是某个子树的根结点。
- 按照逻辑思考，删掉根结点这个树首先是不成树了，但是它左右子树肯定是存在的，要怎么办？要拉一个结点放在这个地方来当垫背的，来继续充当这颗子树的根节点，那么应该拿哪个垫背的？应该拿和要删除的根节点最接近的结点，或者是刚好大于右子树的结点，这两种方法都可以。
- 一般来说的话，是取第一个大于要删除的根节点的结点。也就是选它子树里面最小的结点，把它替换上去即可，这是相对来说最简单的一种。
- 它的大部分时间复杂度是O(logn)的。这就是二叉搜索树，它的特点就是它大部分操作都是O(logn)的。
- 有一种特殊情况，这颗树退化成了一根棍子，就是它只有右结点，这就变成了一个单链表了，这种极端情况下，要查某一个节点的话，就必须一步一步一直走下去，所以就退化成O(n)d的时间复杂度了。那要怎么加速它呢？就是把它配平，变成平衡二叉树。
2. 实战题目解析：二叉树的中序遍历
- 树的面试题解法一般都是递归，为什么？
- 第一个原因的话就是它的代码本身，它的树的定义没有所谓的它的后继这么一个结构，或者是说一个便于循环的结构，而是更多的是左结点右结点，这样的话要去访问它的子树的话，经常更好的一种方式，是直接对它的左结点再调用相同的遍历函数。
- 前中后序的代码把它记下来，然后放在心里面做成机械话的记忆。
- 中序遍历：前的话就是根左右，中的话就是左根右，后续的话就是左右根。那么既然是左根右的话，那么它就会往左走，一直走到最左边这个结点，然后再上一个节点，然后再往右依次走下去，然后再回到根节点，然后开始右子树也是依次左根右。
- 把代码和它递归的程序写清楚即可，先熟悉前中后序的代码，能够写的下来即可。
- 实战题目
- https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
- https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
- https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
- https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
- https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
- 题目就是前中后序的变形，有些就是直接是原题，写的话就直接上去套代码模板去写即可。
- 二叉树的中序遍历
- 按照中序遍历左根右代码模板输出即可。
- 这是一个数的结构，根据1、null、2、3就得到一个树，那么它返回的结果是132，因为左边没有直接是根节点，然后再左子树走到3最左子树是3，然后再左子树走到3最后左子树是3。进阶：通过迭代算法完成。
- 官方题解：1、递归 2、基于栈的访问 3、莫里斯遍历
- 递归本身并不存在所谓的效率差、效率低的问题。只要程序本身算法复杂度没有写残即可。举个例子Fibonacci数列如果只是傻递归，没有把中间结果存储起来，导致本身线性可以解决的问题，需要指数级的时间复杂度才能解决的话，这是不合理的。但是问题本身不在递归上面，而是在程序本身写傻了，而写傻的原因可能是对于递归的状态树不是特别熟悉写傻的。所以的话问题本身并不在递归而是没有用缓存。
- 递归和非递归的方式，递归是不是一定会慢一点呢？其实递归慢的地方就是在它要多开一些栈，如果递归深度很深的话，的确可能会有这样的问题，但是一般情况下，现在计算机的存储方式和编译器对于递归，特别是尾递归的优化，就直接认为递归和循环它的效率是一样的，不需要刻意地规避递归这个问题，也不需要直接有有色眼镜，一看到又递归调用就是慢，没有这个说法的。
- 栈迭代的方式虽然提高效率，但是嵌套非常烧脑，不易理解，容易造成一看就懂，一写就废，网友的这个说法有些严重。介绍了他的一种叫做颜色标记法，它的特点就是写法相对比较统一，且对于前中后序都一样的。核心思想看一下，然后直接看他的代码。
- 颜色标记法代码本身的话其实就是维护了一个栈，对栈的这个元素不断地从栈里面去出来，如果栈是白色的话，说明之前没有访问过，也就是刚放进去的，那么就是把它的左右结点一次压入栈里面，同时的话还把它结点本身，也就是根节点也放入栈里面去，如果它不是白色，说明是灰色之前访问过的，那就直接输出这个结果就行了。这段代码其实就是手动维护了一个递归的栈，他其实就是在做递归，只不过他用栈来模拟这么一个递归，这种写的方式可以看到它本身的话并不是输入哪一种比较经典的写法，而是自己就是类似于灵活运用或者发明创造出来的一个，可以去学习一下，但它本质的话就是他自己手动维护了一个栈，然后把元素依次压入栈，同时在模拟递归的效果，从栈里面每次取出的时候，再把它的左根右，他这里是右根左压到这个栈里面去，这种写的效果，其实就是右根左的写法就可模板写法基本上没什么差别，只需要把访问右结点和访问左结点这两句话，互相调换一下即可。
第2周-第7课 | 泛型递归、树的递归
1. 递归的实现、特性以及思维要点
- 很多时候树的数据结构很多都是递归定的定义。
- 递归也就是所谓的泛型递归，以及关于树的各种递归。
- 树的面试题解法一般都是递归，主要原因是因为：第一它的结点和树本身，它数据结构的定义就是用递归的方式进行的。第二就是不仅是树本身，二叉树以及搜索二叉树，它在定义它数据结构和它的算法特性的时候，也是有所谓的重复性，也就是自相似性。
- 比如二叉搜索树，它是左子树都要小于根结点，右子树都要大于根节点，且左右子树具有相似的特征，或者说以此类推，左右子树也满足以上特点。
- 树的遍历也同理可得，前中序遍历它就是一个递归的函数，函数本身非常漂亮。
- 递归 Recursion
- 递归其实本质上它就类似于循环，只不过是通过循环体调用自己，来进行所谓的循环，为什么会有这样的一种形式，就是因为在计算机语言在创造的时候，它本质上就是汇编，而汇编它有个特点，它没有所谓的循环嵌套这么一说，很多的时候它更多的用的就是，之前有一段函数或者指令写在什么地方，就直接不断地反复跳到之前的那段指令不断地去执行，其实这就是所谓的递归。而循环本身可以把它编译出来，看它的汇编代码，其实和递归本身有异曲同工之处。所以递归和循环它们没有明显的边界。
- 递归从现实意义上来讲的话，就是从前有座山，山里有个庙，庙里有个和尚敲代码，然后再返回1。现实生活中很多时候也有所谓的重复性，这种重复性其实用计算机解决，就能够给大家省很多的事情。那么这种现实生活的话，更多是来自于一部电影，比较好类比，就是找到这种所谓的归去来兮的感觉，这部电影就是盗梦空间。
- 盗梦空间
- 它的主线的情节其实就是从飞机开始，然后去到城市，再往下不断地递归，走到最后在一个雪山的屋子里面，那么已经是第三层或者第四层递归了，每一层时间会变慢。它每进到一层递归就相当于一个新的世界或者是一个互不干扰的世界在里面做一些事情，再下到另外一层再做一些事情。如果要返回现实世界的话，必须一层一层再回来。而且每次下去或者是回来的时候，它自身会发生改变的，或者把自己的状态带到下一层去，发生了改变再带回来，但是环境里面的其他的东西其实是不受影响的，也就是说下一层的环境不会影响这一层环境里面的人和物，除非是主角或者主角相关的人，就可以理解为这些人的话是函数的参数。
- 递归的特点是向下进入到不同的递归层，也就是所谓的梦境，向上又回到原来的层。一般来说它不能直接跳跃，而是必须一层层地下，然后一层一层地回来，所谓的就是有一种对称性，或者叫做归去来兮的感觉。
- 这里是用声音同步回到上一层，所谓这种同步的关系就是用参数进行函数不同层之间的传递变量。
- 每一层的环境和周围的人都是一份拷贝，也就是他进到每一层的话，这每一层的房子建筑和那些无关的人物，其实就是类似于硬生生地整个创造了一份新的世界，把这个世界全部都打坏了之后，去到下一层或者回到上一层，上一层的世界里面的楼还是不受影响的。然而主角等几个人，就是主角那个团队，他可以穿越不同的梦境，同时把自身和自己所要携带的东西，都可以带到不同的梦境里面去发生变化，且把变化可以携带回来。而这样主角团队这个就类似于函数里面的参数，同时还会有一些全局变量。
- 更加强调的是通过现实中盗梦空间的这样一个跳跃的含义，递归它整个发生和显示中怎么联系在一起的。
- 多思考这三点，平时在做类似于题目的时候或者写程序都想到盗梦空间。
- 最简单的递归形式 求它的阶乘
- 求递归本身就是写一个函数即可，每次就括它自己调n - 1，那么递归最后的运行方式就成了这么一个所谓的递归栈。就一层一层一层展开，而这种形式就更像一种剥洋葱的形式，所谓的剥洋葱就是类似于一个栈的形式一层一层一层进去，然后再把它剥开，而栈本身的话就是递归滴啊用的时候，它系统给我们做了一个这样的调用栈。
- 现实中要解决的递归经常会更加得复杂一些，抽样出来一份递归的代码模板，非常的实用。代码本身不长，结构是更加重要的，记住这四个结构模块。
- 整个递归代码分为四块。
- Recursion Terminator递归终结条件，也就是写递归的函数开始的话一定要记得先把函数，就是递归的中止条件给写上。这点如果不注意的话，最后造成的结果就是无限递归或者叫做死循环，类似于死递归之类的。
- 处理当前层逻辑，处理这一层要进行的逻辑就在这里完成这一层要进行的业务代码逻辑代码。
- 下探到下一层，这里它的参数来标记当前是哪一层，必须要加一，同时把相应的参数paraneter放下去就行了。
- 清理当前层，要是递归完了话，这一层有些东西可能要清理把它清理，有些时候不需要清理着一层，因为它这一层的很多时候，它这一层本身的哪些环境，它是拷贝一份出来的，但很多时候会有一些全局变量，还有其他的一些事情要进行清理的，那就在最后这一部分来清理即可。
- 三个思维要点：这些思维要点主要针对觉得递归难以领悟或的
- 不要人肉进行递归（最大误区），这点主要针对如果后来递归开始慢慢比较熟练了之后，一定要抛弃这样的习惯，就是不要再进行人肉递归了。如果刚开始学的话，可以再之上把递归所进行的状态，也就所谓的递归的状态树画出来可以，但是到后面的话，希望主动抛弃人肉递归，以及要画递归的状态树这么一种特点。一定要记得就直接看函数本身开始写即可，不然永远没法有效地掌握或者熟练使用递归。
- 找到最近最简方法，将其拆解成可重复解决的问题（也就是找最近重复子问题）。为什么要找最近重复子问题？就是因为我们写的程序的指令，只包括if else 然后 for 和 while loop ，然后就是第三部分就是递归调用，正式因为所有的代码只有这三部分，如果是比较复杂的程序，逻辑比较多，但却可以用比如五行语句或者十行语句解决，就是因为因为这个很复杂，觉得很多的逻辑本身有所谓的可重复性。
- 数学归纳法思维，数学归纳法的思维其实就和上面是一样的，数学归纳法的要点就是最开始最简单的条件是成立的，比如n = 1 ,n = 2的时候是成立的，且第二点能够证明当n成立的时候，可以推倒出n + 1 也成立的，那么就类似于放鞭炮一样，第一个保证可以把它点燃，同时还可以保证前一个炮竹炸的时候后一个炮竹也会炸，那么这一串炮竹一百响，只要点燃第一颗，后面肯定都可以证明能够爆炸的。
- 这就是所谓递归的理论部分。
- 注意把Java和Python的两个递归代码模板认真去看，然后记下来，一定要养成机械化的记忆，也就是一开始写递归的话，这个模板的四部分马上写下来。记住三个思维要点