目录
一、简单讲解递归
- 什么是递归：百度百科给出的解释，但其实就只一句话说，函数自己调用自己。
- 为什么会使用递归 ：就是可以将一个主问题分成与主问题相同逻辑的多个子问题，子问题又能再分。
- 如何理解递归：初学：递归展开的细节图，熟悉：理解二叉树中的题目，大乘：宏观看待递归过程：不在意递归的细节图，把递归函数当成一个能解决任务的东西。
- 如何写好一个递归：
4.1. 先找到相同的子问题，确定函数头如何设计；
4.2. 只关心一个子问题的解决方式，确定函数的书写；
4.3. 注意递归函数的结束条件，避免死递归。
接下来使用递归的算法题来深入理解递归。
二、⾯试题08.06.汉诺塔问题
题目链接：⾯试题08.06.汉诺塔问题
题目描述：
题目分析：
一个经典的递归问题，3根柱子，将A柱子上的盘子全部放在C上，转移过程中只能小盘子在大盘子上。
解题思路：
- 先找到相同的子问题：我们要将n个盘子从A借助B放去C，那我们就先将n-1个盘子从A借助C放入B，再将最后一个盘子从A放入C；以此确定函数头设计为
void dfs(A,B,C, 盘子个数 )
- 一个子问题的解决思路：
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);
- 递归函数的结束条件：只有一个盘子就只要移动就行了。
解题代码如下：
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);
}
}
三、合并两个有序链表
题目链接：合并两个有序链表
题目描述：
解题思路：
- 先找到相同的子问题：拿到一个节点后，剩下节点与另一个链表不就又是两个链表合并吗。函数头
dfs(l1,l2) - 一个子问题解决思路：
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;
}
- 递归结束条件：如果有一个链表为空就不用合并，直接返回另一个链表即可。
解题代码：
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.反转链表。
题目描述：
解题思路：
- 先找到相同的子问题：翻转了一个节点之后，剩下节点组成的链表又是一个反转链表问题。
函数头设计就使用题目的函数头ListNode reverseList(ListNode head)。 - 一个子问题的解决思路： 就使用两个节点。
2.1 先将head的下一个节点的next域指向head即head.next.next = head；
2.2 再将head的next域指向null，在进行这一步之前需要将next域的值记录下来作为反转后的链表的头结点；
ListNode newHead = head.next;
head.next = null;
- 递归结束条件：当要反转的链表只有一个节点或者没有节点就返回。
解题代码：
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.两两交换链表中的节点。
题目描述：
解题思路：
- 先找到相同的子问题：我们交换了两个节点之后，剩下节点组成的链表又是一个两两交换节点问题。所以函数头设计就是题目给出的函数
ListNode swapPairs(ListNode head)。 - 一个子问题的解决思路：
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)
题目描述：
解题思路：递归实现快速幂
- 先找到相同的子问题：有两种看法：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) - 一个子问题的解决方法：就是上面的第二种方法，但是我们需要考虑n是否为负数，是否为奇数，所以我们将递归函数单独拿出来，两个函数中分别对n进行一次判断。
- 递归结束条件：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);
}
}