【Java算法】递归

 🔥个人主页： 中草药 

 🔥专栏：【算法工作坊】算法实战揭秘

 🍇一.递归

概念

递归是一种解决问题的方法，其中函数通过调用自身来求解问题。这种方法的关键在于识别问题是否可以被分解为若干个相似但规模更小的子问题。递归函数有两个主要组成部分：

1. 基本情况（Base Case）：这是递归调用的终止条件。每个递归函数都必须有一个或多个明确的基本情况，否则递归将无限进行下去。
2. 递归步骤（Recursive Step）：这是函数调用自身的部分。在此步骤中，问题被分解为更小的子问题，然后递归地求解这些子问题。

递归的本质可以理解为 可以把一个主问题拆分成若干个相同的子问题

宏观的理解递归

        递归其实是比较抽象的一种算法，完全熟练的运用它，需要时间的积累与深入的理解，因此我们可以学会宏观的去看待递归，帮助我们去解决算法问题

1.不必过分关注递归的细节展开图

2.把递归的函数看做一个黑盒（不去深究）

3.相信这个黑盒一定能完成这个任务

用法 

如何写好一个递归

1. 先找到相同的子问题--->函数头的设计
2. 只关心某一个子问题是如何解决的--->函数体的书写
3. 注意一下递归函数的出口

应用场景

递归非常适合处理以下类型的问题：

• 分治法：问题可以被分解为独立且较小的子问题。
• 树形结构：例如文件系统的目录树、DOM树等。
• 回溯算法：如八皇后问题、迷宫寻路等。

 🍈二. 面试题 08.06. 汉诺塔问题

题目链接：面试题 08.06. 汉诺塔问题

​

代码

public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
       dfs(A,B,C,A.size());
       return;
    }

    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);
    }

算法原理 

汉诺塔问题是递归问题的一个经典问题，和常规问题一样，拆分成细小的步骤

汉诺塔问题通常有三个柱子A、B、C，以及n个不同大小的圆盘，初始时所有的圆盘都堆叠在柱子A上，要求将它们全部移动到柱子C上，但在移动过程中必须遵守以下规则：

1. 每次只能移动一个圆盘。
2. 在任何时刻，一个较大圆盘都不能放在较小圆盘上面

代码详解

• hanota 方法是主入口点，它接受三个列表作为参数，分别代表三个柱子A、B、C。
• dfs 方法是一个递归函数，它接受四个参数：柱子A、B、C以及当前要移动的圆盘数量n。
• 当n == 1时，这是递归的基本情况，直接将A上的最后一个圆盘移动到C。
• 对于n > 1的情况，首先递归地将n-1个圆盘从A借助B移动到C；然后将A上的最后一个圆盘直接移动到C；最后再递归地将n-1个圆盘从B借助A移动到C。

🍉 三. 21.合并两个有序链表

题目链接：21.合并两个有序链表

​

代码

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //不能用else
        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;
        }
    }

算法原理

1. 特殊情况处理：首先检查输入的两个链表list1和list2是否为空。
   • 如果list1为空，则直接返回list2。
   • 如果list2为空，则直接返回list1。
2. 递归合并：如果两个链表都不为空，则比较当前节点的值。
   • 如果list1的当前节点值小于等于list2的当前节点值，那么将list1的next指向list1.next和list2的合并结果，并返回list1。
   • 否则，将list2的next指向list1和list2.next的合并结果，并返回list2。

这段代码使用了递归的方式来合并两个有序链表。其基本思想是：

• 基本情况：如果其中一个链表为空，那么合并的结果就是另一个链表。
• 递归步骤：如果两个链表都不为空，则比较当前节点的值。
  • 如果list1的当前节点值小于等于list2的当前节点值，那么list1将成为合并后链表的一部分，然后递归地去合并list1的下一个节点和list2。
  • 如果list2的当前节点值小于list1的当前节点值，那么list2将成为合并后链表的一部分，然后递归地去合并list1和list2的下一个节点。

🍊四. 206.反转链表

代码

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;
    }

算法原理

这里可以比较这道题的 迭代代码 加深理解

public ListNode reverseList1(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curn=cur.next;
            cur.next=head;
            head=cur;
            cur=curn;
        }
        return head;
    }

1. 基本情况：如果当前节点head为空或者当前节点是链表的最后一个节点（即head.next == null），那么直接返回head。这是因为如果链表为空或者只剩一个节点，就不需要反转了，直接返回即可。

2. 递归步骤：如果当前节点不是最后一个节点，递归地反转head.next，即反转当前节点之后的所有节点。这里newHead将是反转后的新头节点，即原来链表的最后一个节点成为了新的头节点。 

3. 链接反转：在递归调用返回后，将当前节点head连接到新头节点newHead后面。这一步是通过将head.next.next = head;来实现的，即将head插入到新反转链表的头部。

   • 注意，这里的head.next是原来链表中的下一个节点，现在它已经是反转链表的头节点了，所以我们通过head.next.next来访问原来链表的下下个节点，现在变成了反转链表的第二个节点。

4. 断开连接：将head的next设为null，这样原来的链表就被切断了，从而完成了反转。

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

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

代码

 public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode tmp=swapPairs(head.next.next);
        ListNode ret=head.next;
        ret.next=head;
        head.next=tmp;

        return ret;
    }

算法原理

此代码，建议先用一个小链表模拟实现以下该过程，帮助理解这个递归

基本情况：如果当前节点head为空或head.next为空（即链表为空或只有一个节点），则直接返回head。这是因为单个节点或空链表无需交换。

递归步骤：

• 首先递归地调用swapPairs(head.next.next)，这意味着我们假设head.next.next之后的部分已经被正确地交换好了。递归的目的是处理当前节点之后的所有节点。
• tmp变量存储了从head.next.next开始的交换好的链表部分。
• ret变量存储了head.next，即当前节点的下一个节点，它将成为新的头节点。
• 接下来，将ret.next设置为head，这样就实现了head和head.next这两个节点的交换。
• 最后，将head.next设置为tmp，这样就将剩余部分的链表正确地连接到了交换后的两个节点之后。

 🍌六.  50.Pow(x,n)

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

代码

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;
            //相当于x的0次方幂
        }
        double tmp=pow(x,n/2);
        //若为奇数，还需要在 * 上一个x
        return n%2==0?tmp*tmp:tmp*tmp*x;
    }

算法原理 

当拿到这道题，大多数人首先会想到循环，但问题是常规的这种循环会超时，因此我们应该将问题用递归的方式去简化，拆分成相同的子问题

这个算法采用了分治的思想，通过递归地将问题规模减半来快速计算幂。

1. 基本情况：当n为0时，任何数的0次幂都是1。
2. 递归步骤：
   • 如果n是偶数，那么x^n可以表示为(x^(n/2))^2。
   • 如果n是奇数，那么x^n可以表示为x * (x^(n-1))。

通过递归地计算x^(n/2)，我们可以将问题规模减半，从而大大减少了计算次数。这种方法的时间复杂度大约是O(log n)，相比直接循环相乘的O(n)复杂度要高效得多。