其实这是第二遍刷剑指offer，发现已经忘得差不多了…虽然说有印象，但该不会写还是不会写。果然纯粹为刷题而刷题，完全不总结还是没啥用啊。所以这次根据题号顺序对里面的算法思想做个总结。
递归怎么解
对于算法ruo ji来说真的很不愿意用递归…因为绕来绕去一定会把自己绕进去。在平时写题时能不用就不用，宁愿写个超级复杂的循环也不想用递归。 但是..!在一定场景下递归真的很简洁很容易。比如这道
根据前序中序序列重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
在草稿纸上画了一通，已经明确核心思想：
-
每次取出前序遍历序列的第一个数作为根节点，找出它在中序序列的位置, 即
let index = vin.indexOf(pre[0]);。 且下一次递归的前序序列也会根据中序序列中的节点数被分成两半。一半是pre.slice(1, index + 1)，一半是pre.slice(index + 1) -
以这个数为分界点，将中序遍历序列分为两半。前半部分为左子树，后半部分为右子树。 即
let left = vin.slice(0, index);和let right = vin.slice(index + 1);
明确之后，感觉要用递归，但还是试试循环求解。若是循环，每次拆解中序序列时会非常麻烦，因为会产生很多的零碎序列片段。
所以应该使用递归，但每次递归产生的结果是什么？应该返回什么？这个是递归的重点。根据题目，既然最后的结果应该是一颗完整的数，所以递归结果即return的内容一定是一个含有val，左右节点的树节点。
即
//返回值是一个节点，已经包括其左右子树
return {
val: pre[0],
left: reConstructBinaryTree(pre.slice(1, index + 1), left),
right: reConstructBinaryTree(pre.slice(index + 1), right)
}
根据这道题，会发现其实递归的难点并不在于算法，而在于对每次递归产生的结果及返回值的把握，一定要搞清楚返回值到底是什么。
还有剑指offer里的第三题也是关于递归的，不过跟这道题思想有点不一样。
从尾到头打印链表
- 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
当然可以无脑循环+unshift，不过估计面试可以直接结束了
如果要用递归的话，明确下一次递归应该是这次递归头结点的next节点,但还是一直卡在应该返回什么。很容易知道如果递归到最后尾节点时可以直接返回值不用递归了。所以应该分界讨论其返回值
- 如果不是最后节点，那这次循环得到的结果应该是一个尾节点到head.next的结果数组
- 如果是尾节点，这才是最开始，将其直接push进数组即可。
//递归，
let res = [];
if(head) {
if(head.next) {
res = printListFromTailToHead(head.next);
//若不是最后节点
//这个函数返回的应该已经是一个从尾到头的结果数组
}
res.push(head.val);
//若是最后节点
//直接将其置加入数组
}
return res;
…还有一个神级看不懂的递归方法，求解
if(head){
printListFromTailToHead(head.next);
res.unshift(head.val);
}
return res;
递归产生的问题
虽然说递归看上去很厉害很万能，但有时递归会产生非常多的重复计算造成时间复杂度非常大。例如经典的Fibonacci数列。
Fibonacci数列
虽然一句return Fibonacci(n-1) + Fibonacci(n-1)就可以解决，但这样效率非常低，面试时这么写肯定是拿不到offer了
不用递归就只能用循环了，整体只用记录三个数即可
function Fibonacci(n) {
let pre = 0, cur = 1,res;
if(n === 0) return pre;
if(n === 1) return cur;
for(let i = 2; i<=n; i++) {
res = pre + cur;
pre = cur;
cur = res;
}
return res;
}
跳台阶
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
对于每次情况，不然就跳1级，不然就跳2级，只有这两种情况，且对于n级台阶跳法有f(n)种。
- 如果这次跳1级，还剩下n-1级台阶要跳，即跳法是f(n-1)
- 如果这次跳2级，还剩下n-2级台阶要跳，即跳法是f(n-2)
- 结合前面两种，即
f(n) = f(n-1) + f(n-2)，本质是一个斐波那契数列，且f(1) = 1, f(2) = 2
变态跳台阶
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
与上题很像，对于每次情况：
- 跳1级，剩下跳法f(n-1)
- 跳2级，剩下跳法f(n-2)
- 跳3级，剩下跳法f(n-3)
…
- 跳n-1级，剩下跳法f(1) 所以f(n) = f(1) + f(2) + f(3) + … + f(n-1)，且f(1) = 1, f(2) = 2 也可以理解成，每增加1级，跳法翻倍（因为每次都前一个数加两遍）
function jumpFloorII(number)
{
// write code here
let res = 1;
if(number === 1) return res;
for(let i = 2; i <=number; i++) {
res = res*2;
}
return res;
}
同样可以用递归来做，这里的递归跟循环基本上一致。
function JumpFloorII(number) {
if(target === 1) {
return 1;
} else {
return 2* JumpFloorII(target);
}
}
总结
整体来说，递归对于很多复杂的算法题非常有帮助，但在使用递归的同时需要注意其算法复杂度是否太大。并且递归对我的一个最大难点就是：
- 递归的返回值与递归状态之间的关系
可以
- *模拟递归到底时的情况，
- 明确每一次递归产生的结果是什么，
- 不同次数递归之间的关系。
