初学者理解递归

理解递归：

三道题套路解决递归问题 | lyl's blog (lyl0724.github.io)

写递归需要知道：

首先是终止条件

然后是在方法体哪里调用自己这个方法，即在哪里自己调用自己

再就是需要return什么

1.理解递归的一种方式

以leetcode第21题举例， 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

关于return L1的个人理解: 递归的核心在于,我只关注我这一层要干什么,返回什么,至于我的下一层(规模减1),我不管,我就是甩手掌柜.

好,现在我要merge L1,L2.我要怎么做?

• 显然,如果L1空或L2空,我直接返回L1或L2就行,这很好理解.

• 如果L1第一个元素小于L2的? 那我得把L1的这个元素放到最前面,至于后面的那串长啥样 ,我不管. 我只要接过下级员工干完活后给我的包裹, 然后把我干的活附上去(令L1->next = 这个包裹)就行

• 这个包裹是下级员工干的活,即merge(L1->next, L2)

我该返回啥?

• 现在不管我的下一层干了什么,又返回了什么给我, 我只要知道,假设我的工具人们都完成了任务, 那我的任务也就完成了,可以返回最终结果了

• 最终结果就是我一开始接手的L1头结点+下级员工给我的大包裹,要一并交上去, 这样我的boss才能根据我给它的L1头节点往下找,检查我完成的工作

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
 
    }
}

2.再次理解递归

注：使用递归时，当我们递归到最后一层，就是即将回溯但还没回溯的最后一层，在这一层我们是只会进入终止条件，在终止条件这里终止，然后向回回溯，不会再运行下面的语句。

也就是说，我们终止条件下面的语句，就不是写给最后一层递归的。。。

当然，任何一层都有可能成为最后一层，主要是看它是否符合终止条件，符合了，向下的递归结束，开始回溯

这里我们以leetcode101举例，判断一棵树是否轴对称

递归的难点在于：找到可以递归的点 为什么很多人觉得递归一看就会，一写就废。 或者说是自己写无法写出来，关键就是你对递归理解的深不深。

对于此题： 递归的点怎么找？从拿到题的第一时间开始，思路如下：

1.怎么判断一棵树是不是对称二叉树？ 答案：如果所给根节点，为空，那么是对称。如果不为空的话，当他的左子树与右子树对称时，他对称

2.那么怎么知道左子树与右子树对不对称呢？在这我直接叫为左树和右树 答案：如果左树的左孩子与右树的右孩子对称，左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。

仔细读这句话，是不是有点绕？怎么感觉有一个功能A我想实现，但我去实现A的时候又要用到A实现后的功能呢？

当你思考到这里的时候，递归点已经出现了： 递归点：我在尝试判断左树与右树对称的条件时，发现其跟两树的孩子的对称情况有关系。

想到这里，你不必有太多疑问，上手去按思路写代码，函数A（左树，右树）功能是返回是否对称

def 函数A（左树，右树）： 左树节点值等于右树节点值 且 函数A（左树的左子树，右树的右子树），函数A（左树的右子树，右树的左子树）均为真 才返回真

实现完毕。。。

    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        return  digui(root.left, root.right);
    }
 
    public  boolean digui(TreeNode left,TreeNode right){
        
       //终止条件，下面两个都是
        if (left==null&&right==null){
            return true;
        }
        if (left==null||right==null||right.val!=left.val){
            return false;
        }
        
        
        return  digui(left.left, right.right)&&digui(left.right, right.left);
    }

3.再再次理解递归

leetcode206，翻转链表，给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

这次是一个关于链表的题，并不是很复杂的递归，甚至递归的方法不在方法体中，它直接将方法体当做返回值进行return，总之就是递归方法先传进来两个相连的节点，将这两个节点反转之后，在调用这个递归函数，将第二个节点以及它的下一个节点传入，继续进行翻转，直到翻转到最后一个节点。

我们在这道题里面可以发现，递归中我们的终止条件并不仅仅是终止条件这么简单，它return回去的值，有时候会在方法体中被用到，有时候会直接当做最终结果返回。

    public ListNode reverseList1(ListNode head) {
          return reverse(null, head);
    }
 
    //使用递归
    public ListNode reverse(ListNode pre,ListNode cur) {
          if (cur==null){
              return pre;
          }
          ListNode next=cur.next;
          cur.next=pre;
          return reverse(cur,next);
    }

注：上面对题目的分析部分某些是个人的理解，某些则取自leetcode评论区，个人觉得大佬们分析的很好！有助于大家对递归的理解~