递归题型
1.汉诺塔问题
面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）
题目的大概意思：将A柱中的盘子放到C柱中，必须要满足从下往上是大盘子到小盘子的过程且一次只能放一个盘子。
拿到这道题时首先需要总结规律：当 n = 1时，直接将A中盘子放到C中就可以了；当 n == 2时，我们需要先将A中最上面的小盘子放到B中，然后将A中剩下的大盘子放到C中，然后直接将B中的小盘子放在C中大盘子上面；当 n = 3 时，先将大盘子上面的两个小盘子借助C放到B中，然后按照之前的操作把大盘子放到C中，最后将B中的两个盘子借助A放到C上。经总结可以将所有的盘子都分成三步走（盘子为一时比较特殊）。
如果编写递归的代码？
首先函数头：找出重复子问题
其次函数体：只关心某一个子问题在做什么
最后递归出口：子问题无法再细分的条件
将上述步骤按部就班运用到这个汉诺塔中
重复子问题：无论多少个盘子，都需要重复三步。第一步：将A中除最大盘子外将n-1个盘子借助C柱转移到B柱中；第二步：将A中最大盘子放到C柱中；第三步：将B中n-1个盘子借助A柱全部移到C柱大盘子上。
递归三步
- 函数头
void dfs(List<Integer> A, List<Integer> B, List<Integer> C, n)
即表达的意思是，A中n个盘子借助B转移到C中；
- 函数体
设计函数体，只需要关注子问题在做什么也就是，也就是前面说到的三步
第一步：dfs(A, C, B, n-1);
第二步：将A中剩下盘子放到C中
第三步：dfs(B, A, C,n-1);
- 递归出口
当n == 1 时，直接将A中盘子放到C中，再return返回即可；
编写代码
public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A, B, C, A.size());}public static 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);}2.合并两个有序链表
21. 合并两个有序链表 - 力扣（LeetCode）
题目意思是将两个有序数组合并成一个有序数组。
定义两个指针，返回有序链表的头指针。当找到较小节点后，还是需要对剩下的节点进行合并，这样还是重复相同问题“合并”，所以采用递归算法也可以解决这道题。
递归三步
- 函数头
mergeTwoLists(ListNode list1, ListNode list2)
将两个有序链表合并；
- 函数体
先对list1，list2比大小，将较小的节点作为头节点返回，再在较小的节点后面添加节点（如：list1.next = mergeTwoLists(list1.next, list2) ）；最后返回头结点。
- 递归出口
当list1为空时，返回list2；相反list2为空时，返回list1；
编写代码
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;}}3.反转链表
206. 反转链表 - 力扣（LeetCode）
反转链表：题目意思是将链表的尾结点通过代码实现变成头结点，链表的头结点将变成尾结点；
拿到这题首先会想先将头结点的下一个节点的next指向头结点，然后再重复相同问题，但是这样就找不到后面的节点了；
这是就需要调正顺序了，可以先找到尾节点，将尾节点的next指向前一个结点就可以了。那么怎么实现呢？可以想象成链表是一棵二叉树（单分支），首先要通过递归找到叶子结点，并创建一个头结点作为最后的返回值，然后将该节点的next的next指向自己，再将自己的节点的next置为空。
递归三步
- 函数头
给一个链表的头结点，递归会自己逆序，返回逆序后的头结点；
ListNode reverseList(ListNode head)
- 函数体
把当前节点逆序完后返回的头结点放到一个新创建的头结点上，然后把当前节点逆序并将其next置为空。
- 递归出口
当节点为空时返回当前节点，或者当节点的next为空时也返回当前节点。
编写代码
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;}
4.两两链表交换
24. 两两交换链表中的节点 - 力扣（LeetCode）
拿出两个节点后剩下的节点任要进行两两交换，然后返回头结点，出现重复子问题时就可以用到递归算法解决问题。这题与反转链表的流程差不多，可以放在一块做。
递归三步
- 函数头
ListNode swapPairs(ListNode head)
直接使用OJ中的方法，刚好符合所需参数以及返回值
- 函数体
当改变两两节点的交界处时，需要一个节点来保存下一个交接节点的地址，然后将两个节点进行上图交换。
- 递归出口
当节点为空时返回当前节点，或者当节点的next为空时也返回当前节点。
编写代码
public ListNode swapPairs(ListNode head) {if (head == null || head.next == null){return head;}ListNode curNext = head.next.next;head.next.next = head;ListNode newHead = head.next;head.next = swapPairs(curNext);return newHead;}5.快速幂
50. Pow(x, n) - 力扣（LeetCode）
如果我们只是一个一个进行相乘的话，那么当数据很多很大时，时间复杂度也就随之升高，那么递归的意义就没用了。所以相对而言就不能一个一个计算，那么我们因该怎么求呐？如果我们对幂数除2，那么计算量就会大大减少；
递归三步
- 函数头
double pow(double x, int n)
- 函数体
需要注意的就是当幂数为负数时，需要1除以pow方法。如果对2取模后为0就不需要成以2，相反就需要，这里可以用到三目运算符。
- 递归出口
当n == 0 时，返回1，因为2^0 = 1;
编写代码
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;}double temp = myPow(x, n/2);return n%2 == 0 ? temp*temp : temp *temp *x;}
