【算法】递归

一、简单讲解递归

1. 什么是递归：百度百科给出的解释，但其实就只一句话说，函数自己调用自己。
2. 为什么会使用递归 ：就是可以将一个主问题分成与主问题相同逻辑的多个子问题，子问题又能再分。
3. 如何理解递归：初学：递归展开的细节图，熟悉：理解二叉树中的题目，大乘：宏观看待递归过程：不在意递归的细节图，把递归函数当成一个能解决任务的东西。
4. 如何写好一个递归：
   4.1. 先找到相同的子问题，确定函数头如何设计；
   4.2. 只关心一个子问题的解决方式，确定函数的书写；
   4.3. 注意递归函数的结束条件，避免死递归。

接下来使用递归的算法题来深入理解递归。

二、⾯试题08.06.汉诺塔问题

题目链接：⾯试题08.06.汉诺塔问题
题目描述：

题目分析：
一个经典的递归问题，3根柱子，将A柱子上的盘子全部放在C上，转移过程中只能小盘子在大盘子上。

解题思路：

1. 先找到相同的子问题：我们要将n个盘子从A借助B放去C，那我们就先将n-1个盘子从A借助C放入B，再将最后一个盘子从A放入C；以此确定函数头设计为void dfs(A,B,C, 盘子个数 )
   
2. 一个子问题的解决思路：
   2.1. 先将n-1个盘子从A借助C放入B；
   2.2 将最后一个盘子从A放入C；
   2.3 将n-1个盘子从B借助A放入C;
   所以函数的书写如下：

dfs(A,C,B,n-1);
C.add(A.remove(A.size()-1));
dfs(B,A,C,n-1);

3. 递归函数的结束条件：只有一个盘子就只要移动就行了。

解题代码如下：

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }
    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        if(n == 1) {
            C.add(A.remove(A.size()-1));
            return;
        } 
        dfs(A,C,B,n-1);
        C.add(A.remove(A.size()-1));
        dfs(B,A,C,n-1);
    } 
}

三、合并两个有序链表

题目链接：合并两个有序链表
题目描述：

解题思路：

1. 先找到相同的子问题：拿到一个节点后，剩下节点与另一个链表不就又是两个链表合并吗。函数头dfs(l1,l2)
2. 一个子问题解决思路：
   2.1 将现在两个链表中较小的头结点作为合并后的头结点；
   2.2 在合并剩余的链表。
   函数的书写：

		if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

3. 递归结束条件：如果有一个链表为空就不用合并，直接返回另一个链表即可。

解题代码：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

四、206.反转链表

题目链接：206.反转链表。

题目描述：

解题思路：

1. 先找到相同的子问题：翻转了一个节点之后，剩下节点组成的链表又是一个反转链表问题。
   函数头设计就使用题目的函数头ListNode reverseList(ListNode head)。
2. 一个子问题的解决思路： 就使用两个节点。
   2.1 先将head的下一个节点的next域指向head即head.next.next = head；
   2.2 再将head的next域指向null，在进行这一步之前需要将next域的值记录下来作为反转后的链表的头结点；

  ListNode newHead = head.next;
  head.next = null;

3. 递归结束条件：当要反转的链表只有一个节点或者没有节点就返回。

解题代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

五、24.两两交换链表中的节点

题目链接：24.两两交换链表中的节点。

题目描述：

解题思路：

1. 先找到相同的子问题：我们交换了两个节点之后，剩下节点组成的链表又是一个两两交换节点问题。所以函数头设计就是题目给出的函数ListNode swapPairs(ListNode head)。
2. 一个子问题的解决思路：
   2.1 交换两个节点的思路：head的下一个节点的next域指向head，head的next执行后续链表交换后返回的头结点。
   2.2 注意在修改之前记录一下head的next的节点和head的next的next。

解题代码：

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode newHead = head.next;
        ListNode node = newHead.next;
        newHead.next = head;
        head.next = swapPairs(node);
        return newHead;
    }
}

六、50.Pow(x,n)

题目链接：50.Pow(x,n)

题目描述：

解题思路：递归实现快速幂

1. 先找到相同的子问题：有两种看法：x的n次方等于x的n-1次方乘x，但是这种的时间复杂度是O(n)，还有就是x的n次方等于x的n/2次方乘x的n/2次方，根据n是不是偶数判断需要再乘一个x不，这样的时间复杂度是O(logN)。所以设计函数头跟题目一样double myPow(double x, int n)
2. 一个子问题的解决方法：就是上面的第二种方法，但是我们需要考虑n是否为负数，是否为奇数，所以我们将递归函数单独拿出来，两个函数中分别对n进行一次判断。
3. 递归结束条件：n为0的时候就返回0。

解题代码：

class Solution {
    public double myPow(double x, int n) {
        return (n < 0) ? (1 / pow(x,-n)) : pow(x,n); 
    }
    public double pow(double x, int n) {
        if(n == 0) return 1.0;
        double tmp = pow(x,n/2);
        return (n % 2 == 0) ? (tmp * tmp) : (x * tmp * tmp); 
    }
}