【算法】递归入门

阿华代码，不是逆风，就是我疯

你们的点赞收藏是我前进最大的动力！！

希望本文内容能够帮助到你！！

本篇文章主要是提供递归入门的简单算法题，可以帮助刚接触递归的友友们打开思路，打开递归的大局观，题目不难，重在思想

一：汉诺塔问题

心得感悟：汉诺塔问题是递归系列中最经典的一个问题，我们在思考递归问题的时候，尽量从宏观角度去考虑，包括函数体的设计，方法的出口，递归的调用，相信递归

这道题涉及到的集合的操作：.remove()和.add()      移除元素返回值就是该元素

找重复子问题是递归的核心

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));//这里不能写成a.get(0),因为需要移除来在，放进去 // c.add(a.get(0)); dfs(b,a,c,n-1); } } 二：合并两个有序链表

心得感悟：这道题的核心也在于找到重复子问题——选取头结点中val值小的那个作为头结点a，再把剩下的两部分交给递归方法（相信这个方法能把剩下的两部分链表有序连接）合并成一个链表，a.next = 这个递归方法即可，不要深究！！，递归就是理解了问题，代码就会书写就会变得非常优雅。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 递归出口 if(list1 == null) return list2; if(list2 == null) return list1; // 1:选取，头结点中值较小的那个 if (list1.val <= list2.val) { list1.next = mergeTwoLists(list1.next,list2); return list1; }else{ list2.next = mergeTwoLists(list2.next,list1); return list2; } } } 三：反转链表

心得：

1：递归的出口，if条件为什么是head == null 和head.next == null 两个条件要想清楚，在代码注释中已经详细解释，

2：关键点：整体思想，头结点的记录

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode node = reverseList(head.next);//记录一下头结点//这里head可能为null，为null就不递归了 head.next.next = head;//这一步是关键，尽管把head的右边看为了整体，还得用head.next来表示这个整体。这里是head.next可能为null, head.next = null; return node; } } 四：两两交换链表中的节点

心得：

1：大局观写这个代码4行搞定，太爽了

2：重复子问题解决之后，对于指正的记录是非常讲究的，

3：过程一定要想清楚，不然代码中的细节问题非常致命

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){//如果当前节点为null或者只有一个节点，就返回 return head; } //后面整体进行交换，然后用一个指针记录一下头结点 ListNode tmp = swapPairs(head.next.next); // 最后需要返回的节点也要记录一下 ListNode result = head.next; result.next = head; head.next = tmp; return result; } }

迭代版本

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } // 虚拟头结点 ListNode newHead = new ListNode(0); newHead.next = head; // 先搞四个指针 ListNode prev = newHead, cur = prev.next, next = cur.next, nnext = next.next; while (cur != null && next != null) { prev.next = next; next.next = cur; cur.next = nnext; prev = cur; cur = nnext; if (cur != null) { next = cur.next; } if (next != null) { nnext = next.next; } } return newHead.next; } } 五：快速幂

50. Pow(x, n)

当发生溢出情况的时候，可以转化为long，在递归传参的时候，我们可以先除2，然后再强制向下转型，这样就不会溢出了我嘞个乖乖，折磨

溢出版本

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

非溢出版本

class Solution { public double myPow(double x, int n) { return n >= 0 ? pow(x,n) : 1/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 ? Math.pow(tmp, 2) : Math.pow(tmp, 2) * x; // return n % 2 == 0 ? tmp * tmp : tmp * tmp * x; } }