对递归的的一点理解

作为一个刚准备跨行的小白，这几天在刷题时看到了很多大神写的递归算法，深受震撼，而自己对递归的理解也一直迷迷糊糊，看大神们写的代码也很容易就把自己绕了进去了。最近偶然看到一篇帖子，感觉自己对递归有了新的理解，因此在这里记录一下。

首先我认为在设计递归算法一定要从整体去考虑。在设计算法的内部结构之前，我们就要把我们的函数当做是已经能实现完整功能了，我们所要做的工作就是通过调用这个函数把我们所需要的函数功能再次的实现出来。

以经典的链表反转问题为例

ListNode reverse(ListNode head){
  if(head==null&&head.next==null) return head;
  ListNode node = reverse(head.next);
  head.next.next = head;
  head.next = null;
  return node;
}

首先要明确递归一定是对我们输入参数紧挨着的下一个参数进行操作，也就是把当前参数下的返回值用下一个参数下的返回值表示出来。

接下来我们就来设计针对链表反转的递归算法。

这里我们先跳出函数内部，先明确我们设计的函数的返回值，

reverse(ListNode head);

我们最终设计的是一个reverse函数，该函数返回的也就是以head为头结点的链表的反转，上面我们有说过递归是对我们输入参数紧挨着的下一个参数进行操作，也就是head.next,也就是说我们要用reverse(ListNode head.next)来实现reverse(ListNode head)，那么接下来思路就很简单了。

记得我们之前说过的，我们是要先假设我们的reverse()函数是已经成立的，所以reverse(ListNode head.next)的输出就是下面虚线框中的样子：

当然这时候我们需要用一个node新节点把反转后的部分链表给存起来，显然此时的结果还不是我们想要的反转链表，因为节点1和2的方向还没有翻转过来。因为我们的最终目的是实现reverse(ListNode head)，所以我们就需要下面的语句把1节点变成reverse(ListNode head.next)链表的最后一个节点。

  head.next.next = head;
  head.next = null;

上面两条语句很容易理解，就是把1节点变成2节点的后继节点，再把1节点的后继节点变成null，这样一来实际上node链表就成为了我们需要的reverse(ListNode head)的返回值，我们用return把它返回即可。