为什么你学不会递归？( 三 ) _递归

我们就缩小范围，先对 2->3->4递归下试试，即代码如下
1Node reverseList(Node head){2 if(head == null || head.next == null){3 return head;4 }5 // 我们先把递归的结果保存起来，先不返回，因为我们还不清楚这样递归是对还是错。，6 Node newList = reverseList(head.next);7}我们在第一步的时候，就已经定义了 reverseLis t函数的功能可以把一个单链表反转，所以，我们对 2->3->4反转之后的结果应该是这样：

文章插图

我们把 2->3->4 递归成 4->3->2 。不过，1 这个节点我们并没有去碰它，所以 1 的 next 节点仍然是连接这 2 。
接下来呢？该怎么办？
其实，接下来就简单了，我们接下来只需要把节点 2 的 next 指向 1，然后把 1 的 next 指向 null,不就行了？，即通过改变 newList 链表之后的结果如下：

文章插图

也就是说，reverseList(head) 等价于 ** reverseList(head.next)** + 改变一下1，2两个节点的指向。好了，等价关系找出来了，代码如下(有详细的解释)：
1//用递归的方法反转链表 2public static Node reverseList2(Node head){ 3 // 1.递归结束条件 4 if (head == null || head.next == null) { 5 return head; 6 } 7 // 递归反转子链表 8 Node newList = reverseList2(head.next); 9 // 改变 1，2节点的指向。10 // 通过 head.next获取节点211 Node t1 = head.next;12 // 让 2 的 next 指向 213 t1.next = head;14 // 1 的 next 指向 null.15 head.next = null;16 // 把调整之后的链表返回。17 return newList;18 }这道题的第三步看的很懵？正常，因为你做的太少了，可能没有想到还可以这样，多练几道就可以了。但是，我希望通过这三道题，给了你以后用递归做题时的一些思路，你以后做题可以按照我这个模式去想。通过一篇文章是不可能掌握递归的，还得多练，我相信，只要你认真看我的这篇文章，多看几次，一定能找到一些思路！！

我已经强调了好多次，多练几道了，所以呢，后面我也会找大概 10 道递归的练习题供大家学习，不过，我找的可能会有一定的难度。不会像今天这样，比较简单，所以呢，初学者还得自己多去找题练练，相信我，掌握了递归，你的思维抽象能力会更强！

接下来我讲讲有关递归的一些优化。
有关递归的一些优化思路
1. 考虑是否重复计算
告诉你吧，如果你使用递归的时候不进行优化，是有非常非常非常多的子问题被重复计算的。

啥是子问题？f(n-1),f(n-2)….就是 f(n) 的子问题了。

例如对于案例2那道题，f(n) = f(n-1) + f(n-2) 。递归调用的状态图如下：

文章插图

看到没有，递归计算的时候，重复计算了两次 f(5)，五次 f(4) 。。。。这是非常恐怖的，n 越大，重复计算的就越多，所以我们必须进行优化。
如何优化？一般我们可以把我们计算的结果保证起来，例如把 f(4) 的计算结果保证起来，当再次要计算 f(4) 的时候，我们先判断一下，之前是否计算过，如果计算过，直接把 f(4) 的结果取出来就可以了，没有计算过的话，再递归计算。
用什么保存呢？可以用数组或者 HashMap 保存，我们用数组来保存把，把 n 作为我们的数组下标，f(n) 作为值，例如 arr[n] = f(n) 。f(n) 还没有计算过的时候，我们让 arr[n] 等于一个特殊值，例如 arr[n] = -1 。
当我们要判断的时候，如果 arr[n] = -1，则证明 f(n) 没有计算过，否则，f(n) 就已经计算过了，且 f(n) = arr[n] 。直接把值取出来就行了。代码如下：
1// 我们实现假定 arr 数组已经初始化好的了。2int f(int n){ 3 if(n <= 1){ 4 return n; 5 } 6 //先判断有没计算过 7 if(arr[n] != -1){ 8 //计算过，直接返回 9 return arr[n];10 }else{11 // 没有计算过，递归计算,并且把结果保存到 arr数组里12 arr[n] = f(n-1) + f(n-1);13 reutrn arr[n];14 }15}也就是说，使用递归的时候，必要
须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来。
2. 考虑是否可以自底向上
对于递归的问题，我们一般都是从上往下递归的，直到递归到最底，再一层一层着把值返回。
不过，有时候当 n 比较大的时候，例如当 n = 10000 时，那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。