前言
再没对递归理解之前，递归始终我的噩梦，对于写递归代码始终都是无从下手，但当了解了递归之后，才惊叹到，编程真的是一门艺术。在01世界里，递归是极其重要的一种算法思维，不可能绕的开。这一章咱们从调用栈、图解、调试、用递归写链表的形式，再进一步坚固上一章链表的同时，也更进一步了解递归这种算法思维。
什么是递归？
《盗梦空间》大家应该都看过，那么你能够把递归设想成电影里的梦幻，当在这一层没有失去答案时，就进入下一层的梦幻，直到在最初一层找到了答案，而后返回到上一层梦幻，逐层返回直到事实世界，递归完结。所以递归二字形容的其实是解决问题的两个过程，首先是递，而后是归。而递与归之间的临界点，又能够叫做递归终止条件，意思是咱们通知计算机：行了，别递了，开始归的过程吧您嘞。
函数调用栈
为了更好的了解递归，函数调用栈这个前提还是得先弄明确了，咱们首先来看下这段程序`：
function a() { b(); console.log('a')}function b() { c(); console.log('b')}function c() { console.log('c');}a(); // c b a简略先说下JavaScript的执行机制，当遇到函数执行时，会为其创立一个执行上下文，而后压入一个栈构造内，当这个函数执行实现之后，就会从栈顶弹出，这是引擎追踪函数执行的一个机制。再看上述代码时，执行a函数，就将a推入调用栈，然而a函数还没执行完时又遇到了b函数的执行，所以又将b函数推入调用栈，再b函数里又执行了c函数，所以就向调用栈里推入c函数。在c函数里打上断点后，咱们能够在浏览器的调用栈里看到三个函数最终入栈的程序：
出栈的机会是以后栈顶的函数执行结束时，就弹出，所以最终打印的程序是c b a。
其实递归函数的调用是雷同的，只有没到递归的终止条件，就始终将雷同的函数压入栈，这也就是递的过程。当遇到了终止条件后，就开始从栈顶弹出函数，当递归函数的零碎栈全副弹出，归的过程完结后，整个递归也就完结。
如何写递归代码
举一个例子，求解字符串的逆序，如abcd返回dcba，请应用递归。
- 拆解反复逻辑子问题
既然是求abcd的逆序，拆解后那就是求解d加上剩下abc的逆序；求解abc的逆序，那就又是求解c加上ab的逆序，直到问题被拆解到不能拆解为止。
- 找到递归终止条件
没有终止条件的递归会有限递归上来，直至爆栈，所以咱们要给递归函数设置一个终止条件，满足条件后，就不要再递上来了。很显著这个题目的终止条件是当字符串长度为1时就不必拆解了，为了兼容传入空字符串，能够将终止条件设置为字符串为空时。
- 应用套路
递归也是有套路的，如果勤加练习，并没有太难，这里再附上一个编写递归函数的根本步骤：
function recursion(params) { 1. 递归终止条件 (防止有限递归) 2. 以后函数层逻辑解决 (递归函数的次要解决逻辑) 3. 进入下一层函数 (再次执行递归函数) 4. 解决以后层函数其余逻辑 (可能有这一步，也可能没有)}所以代码如下，略微具体些↓：
function reverseStr(s) { if (s === "") { // 终止条件 return ""; } const lastC = s[s.length - 1]; // 字符串的最初一位 const otherC = s.slice(0, -1); // 除去最初一位的其余字符串 return lastC + reverseStr(otherC); // 进入递归下一层}还是应用画图的形式，更不便的高深莫测其外部执行逻辑。
如何调试递归代码
人的大脑是习惯平淡无奇的，所以这也是递归代码难了解的中央。而计算机善于确实是反复，那么如何调试递归程序就很重要，这里分享几个我常常会应用到小技巧。
- 最小示例代入
debugger法
例如求解的字符串的逆序，就代入abc，而后在递归的函数的外部打上断点，一层层去看以后层的变量变动是否合乎解决逻辑。
console.log大法
在递归函数的外部间接在每个要害节点输入须要观测的变量变动，看是否合乎逻辑。
- 借助浏览器调用栈
借助debugger，在进入的递归函数层数足够深了之后，切换零碎栈Call Stack里的递归层数，并通过Local查看该层变量的值，查看对应的参数的状况。
应用递归解决链表问题
链表和树都是非常适合学习并了解递归算法的示例，所以之后全副都会应用递归，也是为之后更难了解的回溯打好根底。
再解决链表问题时，如果没有思路，能够用纸和笔把指针指向的过程画下来，而后再尝试从外面找到重复子问题会很有帮忙。
206. 反转链表↓
反转一个单链表输出: 1->2->3->4->5->NULL输入: 5->4->3->2->1->NULL上一章应用循环，这次尝试应用递归解决。因为是链表，所以思路是扭转指针的指向。子问题就是让最初一个节点指向它之前的节点。首先还是递的过程，咱们须要递到最初一个节点。而后开始归，让它的指针指向倒数第二个节点即可，所以要晓得倒数第二个节点，然而原先倒数第二个节点正指着倒数第一节点了，此时它们就会造成一个互指的环，最初再让倒数第二个节点指向空即可，断开环。
代码如下：
var reverseList = function (head) { if (head === null || head.next === null) { return head } const node = reverseList(head.next) // 最初一个节点 head.next.next = head // 让3指向2、让2指向1。 head.next = null // 让2指向空、让1指向空。 return node};83. 链表去重↓
给定一个排序链表，删除所有反复的元素，使得每个元素只呈现一次。输出: 1->1->2输入: 1->2输出: 1->1->2->3->3输入: 1->2->3有了链表反转的技巧后，再解这个题目就很容易了，还是递归到底，因为咱们晓得倒数一个节点和倒数第二个节点，所以再归的过程里，如果倒数两个节点的值雷同，则倒数第二个指向它的下下个节点即可。这个绝对简略，再了解了反转后，应用之前的递归调试法去了解置信一点都不难，就不画图了。
var deleteDuplicates = function (head) { if (head === null || head.next === null) { return head } const ret = deleteDuplicates(head.next) // 递归到底去，因为递归的终结条件，ret就是最初一个节点 // 而此时head就是倒数第二个节点 if (ret.val === head.val) { head.next = ret.next // 倒数第二个节点指向它的下下个节点 } return head};21. 合并两个有序链表↓
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输出：1->2->4, 1->3->4输入：1->1->2->3->4->4首先还是拆解子问题，子问题是最小值的节点拼接上残余曾经合并好的两个链表。例如1指向的就是23与124拼接好的后果；剩下的最小节点还是1，那么剩下的1指向的就是23与24拼接好的后果。持续拆解中转问题不能拆解为止，如果某一个节点曾经到头，那么阐明另一个链表所有的值都比这个链表大，间接返回即可。代码如下：
var mergeTwoLists = function (l1, l2) { if (l1 == null) { // l1到了头，阐明l2接下来都比l1最大值还大 return l2 } if (l2 == null) { // 同理 return l1 } if (l1.val > l2.val) { l2.next = mergeTwoLists(l1, l2.next) // 则l2换下一个更大节点来比拟 return l2 // 以后小节点指向拼接好的后果后，返回 } else { l1.next = mergeTwoLists(l1.next, l2) // 同理换更大的节点来比拟 return l1 // 同理 }};24. 两两替换链表中的节点↓
给定一个链表，两两替换其中相邻的节点，并返回替换后的链表。你不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。 1->2->3->4, 返回 2->1->4->3.如果尝试用纸和笔画出过程，就很容易发现子问题，让第一个节点指向第二个节点之后曾经替换好的链表，而后让第二个节点指向之前的节点。
var swapPairs = function (head) { if (head === null || head.next === null) { //判断head.next是为了避免链表节点个数是奇数 return head } const firstNode = head // 链表的第一个节点 const secondNode = head.next // 链表的第二个节点 firstNode.next = swapPairs(secondNode.next) // 第一个节点指向第二个节点之后曾经替换好的链表 secondNode.next = firstNode // 第二个节点指向第一个节点 return secondNode // 返回第二个节点作为新的头节点};快慢指针解决链表问题
有些简单的链表问题内的子问题可能须要用上，也是解决局部链表问题的一种小技巧。
876. 链表的两头结点↓
给定一个带有头结点 head 的非空单链表，返回链表的两头结点。如果有两个两头结点，则返回第二个两头结点。1->2->3->4->5返回3->4->5设置两个指针，慢指针一次走一步，快指针一次走两步，当快指针走完时，正好慢指针在链表的两头。
var middleNode = function (head) { let slow = head // 慢指针 let fast = head // 快指针 while (fast !== null && fast.next !== null) { fast = fast.next.next // 走两步 slow = slow.next // 走一步 } return slow // 走完后慢指针指向两头节点};141. 环形链表↓
给定一个链表，判断链表中是否有环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。输出：3->2->0->-4，pos=1。 输入：true。尾部链接到下标1的地位，为有环。输出：3->2->0->-4，pos=-1。输出：false。尾部没有链接，没环。快指针一次走两步，慢指针一次走一步，如果这个链表是循环的，快慢指针总会相遇；如果是直线行驶，没有环的话，快指针就会走到空。
var hasCycle = function (head) { let slow = head let fast = head while(fast !== null && fast.next !== null) { slow = slow.next fast = fast.next.next if (slow === fast) { // 相遇了 return true } } return false};19. 删除链表的倒数第N个节点↓
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.阐明：给定的 n 保障无效。进阶尝试：你能尝试应用一趟扫描实现吗？首先删除链表第n个节点，则须要找到它之前的节点，让它之前的节点跨过要删除的节点即可。
而后问题是怎么一趟扫描找到倒数第n个节点之前的节点？咱们还是能够应用快慢指针的形式，须要删除倒数第几个，就让快指针多走几步，快指针把先走的几步走完后，快慢指针一起走，快指针到了头，慢指针停留的地位正好就是待删除节点之前的节点。
最初删除该节点，返回链表头节点即可。代码如下：
var removeNthFromEnd = function (head, n) { const dummy = new ListNode() // 设置一个虚构节点，对立边界解决 dummy.next = head let slow = dummy // 因为要找的是待删除之前节点的缘故 let fast = dummy.next // 让快指针当时就当先一步 while (fast !== null) { if (n > 0) { // 先把当先的走完 n-- fast = fast.next } else { // 而后一起走 fast = fast.next slow = slow.next // 走完后慢指针正好在待删除节点之前 } } const delNode = slow.next slow.next = delNode.next // 移除待删除节点 delNode.next = null return dummy.next // 返回头节点};最初
写递归也没什么其余的技巧，无非就是多练、多画、多想、多调试。下一章将开始介绍树结构，正好有一个与链表和树都相干的问题，大家能够尝试解决。本章github源码
力扣 109. 有序链表转换二叉搜寻树给定一个单链表，其中的元素按升序排序，将其转换为高度均衡的二叉搜寻树。