首页 > 其他分享 >2023-03-13 递归详解

2023-03-13 递归详解

时间：2023-03-13 23:46:25浏览次数：69  
标签：03 13 val 递归 int head 2023 NULL arr

1.递归基础和递归的宏观语意

本质上，将原来的问题，转化为更小的同一问题

举例

递归举例之数组求和

代码

public class ArrSum {
    private int res = 0;

    public int sum(int[] arr) {
        return sum(arr, 0);
    }

    /**
     * 计算从arr[i]到arr[n-1]的和
     *
     * @param arr 数组
     * @param i   当前遍历到的索引
     * @return arr[i]到arr[n-1]的和
     */
    private int sum(int[] arr, int i) {
        if (i == arr.length) {
            // 遍历完数组，返回0
            return 0;
        }
        return arr[i] + sum(arr, i + 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(new ArrSum().sum(arr));
    }
}

递归解析

递归是a->a->a即相同函数的互相调用，实际与a->b->c即不同函数之间的调用没啥区别不断取内层调用函数的返回值给上一层即可我们只要想清楚内层函数的逻辑即可~~

  • 1.求解最基本问题(也即递归的退出条件)
  • 2.把原问题转换为更小的问题(也即递归的具体逻辑)
    递归代码解析

递归就像老师说的那样，将原有问题变成一个更小的问题，然后在更小的问题基础上再变成更更小的问题，一直到不能再变小为止，当不能再变更小的时候，这个时候这个问题的答案就变得显而易见了，然后再通过这个答案反其道而行之，以这个答案为基础向上推导出原问题的答案。

2.链表的天然递归结构性质

链表递归的终止条件：访问到为NULL的节点

直到最后可以理解为空本身也是一个链表。null就是那个最基础的、最平凡的链表，即递归退出条件
链表递归的终止条件

递归解决LeetCode203号问题：删除链表中等于指定值的所有元素

链表删除（递归写法）：

  • 1.注意宏观语义
  • 2.删除掉一个节点后得到小问题的解
  • 3.考虑怎么用小问题的解构建原问题的解
  • 4.分情况讨论
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);
        // head节点要删除就直接跳过head节点，否则就返回原来的
        return head.val == val ? head.next : head;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 6, 3, 4, 5, 6};
        ListNode head = new ListNode(nums);
        System.out.println(head);
        ListNode result = (new Solution()).removeElements(head, 6);
        System.out.println(result);
    }
}

3. 递归的微观解读

递归的调用和普通的子函数链式调用没区别，只不过名字是自己而已。

递归调用与普通调用的对比
递归调用与普通调用

递归相当于隐式的系统调用栈
普通函数调用

递归过程详细分析举例1：数组求和

public class ArrSum {
    private int res = 0;

    public int sum(int[] arr) {
        return sum(arr, 0);
    }

    /**
     * 计算从arr[i]到arr[n-1]的和
     *
     * @param arr 数组
     * @param i   当前遍历到的索引
     * @return arr[i]到arr[n-1]的和
     */
    private int sum(int[] arr, int i) {
        if (i == arr.length) {
            // 遍历完数组，返回0
            return 0;
        }
        return arr[i] + sum(arr, i + 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(new ArrSum().sum(arr));
    }
}

本题中递归函数为int sum(int[] arr, int i)，arr.length=5

  • 第1层递归：i=0<5，arr[i]=arr[0]=1，进入第2层递归i+1=1
  • 第2层递归：i=1<5，arr[i]=arr[1]=2，进入第3层递归i+1=2
  • 第3层递归：i=2<5，arr[i]=arr[2]=3，进入第4层递归i+1=3
  • 第4层递归：i=3<5，arr[i]=arr[3]=4，进入第5层递归i+1=4
  • 第5层递归：i=4<5，arr[i]=arr[4]=5，进入第6层递归i+1=5
  • 第6层递归：i=5=5，把0返回到上一层递归
  • 第5层递归：把arr[4]+0返回到上一层递归
  • 第4层递归：把arr[3]+arr[4]+0返回到上一层递归
  • 第3层递归：把arr[2]+arr[3]+arr[4]+0返回到上一层递归
  • 第2层递归：把arr[1]+arr[2]+arr[3]+arr[4]+0返回到上一层递归
  • 第1层递归：把arr[0]+arr[1]+arr[2]+arr[3]+arr[4]+0返回到上一层递归
  • 没有上一层递归了，函数执行完毕，把求和结果返回即为数组的值

递归过程详细分析举例2：删除链表中等于指定值的所有元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);
        // head节点要删除就直接跳过head节点，否则就返回原来的
        return head.val == val ? head.next : head;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 6, 3, 4, 5, 6};
        ListNode head = new ListNode(nums);
        System.out.println(head);
        ListNode result = (new Solution()).removeElements(head, 6);
        System.out.println(result);
    }
}

本题中初始链表结构为1->2->6->3->4->5->6->NULL，递归函数为ListNode removeElements(ListNode head, int val),我们可以认为每个链表的最后一个节点都是NULL，方便作为递归的终止条件

  • 第1层递归：head.val=1，head->next=2->6->3->4->5->6->NULL，head=1-2->6->3->4->5->6->NULL!=null，所以进入下一层递归
  • 第2层递归：head.val=2，head->next=6->3->4->5->6->NULL，head=2->6->3->4->5->6->NULL!=null，所以进入下一层递归
  • 第3层递归：head.val=6，head->next=3->4->5->6->NULL，head=6->3->4->5->6->NULL!=null，所以进入下一层递归
  • 第4层递归：head.val=3，head->next=4->5->6->NULL，head=3->4->5->6->NULL!=null，所以进入下一层递归
  • 第5层递归：head.val=4，head->next=5->6->NULL，head=4->5->6->NULL!=null，所以进入下一层递归
  • 第6层递归：head.val=5，head->next=6->NULL，head=5->6->NULL!=null，所以进入下一层递归
  • 第7层递归：head.val=6，head->next=NULL，head=6->NULL!=null，所以进入下一层递归
  • 第8层递归：head=null，满足递归回退条件条件，把NULL返回给上一层
  • 第7层递归：赋值head.next=null，head=6->NULL，head.val=6为真，所以递归返回head.next即NULL给上一层递归
  • 第6层递归：赋值head.next=null，head变了，head=5->NULL，head.val=5!=6，所以递归返回head即5->NULL给上一层递归
  • 第5层递归：赋值head.next=5->NULL，head变了，head=4->5->NULL，head.val=4!=6，所以递归返回head即4->5->NULL给上一层递归
  • 第4层递归：赋值head.next=4->5->NULL，head变了，head=3->4->5->NULL，head.val=4!=6，所以递归返回head即3->4->5->NULL给上一层递归
  • 第3层递归：赋值head.next=3->4->5->NULL，head变了，head=6->3->4->5->NULL，head.val=6=6，所以递归返回head.next即3->4->5->NULL给上一层递归
  • 第2层递归：赋值head.next=3->4->5->NULL，head变了，head=2->3->4->5->NULL，head.val=2!=6，所以递归返回head即2->3->4->5->NULL给上一层递归
  • 第1层递归：赋值head.next=2->3->4->5->NULL，head变了，head=1->2->3->4->5->NULL，head.val=1!=6，所以递归返回head即1->2->3->4->5->NULL给上一层递归
  • 已经没有上一层递归了，所以整个递归调用过程完毕，取出值为6的节点后的链表为1->2->3->4->5->NULL

4. 递归调试

使用IDE来单步追踪

IDEA调试递归函数

通过depth参数打印--来显示递归深度，方便看递归过程。在递归进入新层和递归退出当前层的时候都打印下深度字符串

可以看到下面的分析过程和我们手动分析地完全一样，代码地址

/***********************************************************
 * @Description : 虚拟头结点可以大大简化代码
 * @author      : 梁山广(Laing Shan Guang)
 * @date        : 2019/12/29 14:18
 * @email       : [email protected]
 ***********************************************************/
package Chapter05Recursion.Section4LeetCode203Recursion;

import Chapter05Recursion.Section1To2LeetCode203.ListNode;

class SolutionDebug {
    /**
     * 删除链表中值为val的所有元素
     *
     * @param head  链表的头结点
     * @param val   要删除的节点的值
     * @param depth 递归的深度
     * @return
     */
    public ListNode removeElements(ListNode head, int val, int depth) {
        // 下面两行是递归进入新层
        System.out.print(generateRecursionDepthStr(depth));
        System.out.println("第" + depth + "层递归：head=" + head + "，要找的值为节点值为：" + val);
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val, depth + 1);
        // 下面两行是递归退出当前层
        System.out.print(generateRecursionDepthStr(depth));
        System.out.println("第" + depth + "层递归：head=" + head + "，要找的值为节点值为：" + val);
        // head节点要删除就直接跳过head节点，否则就返回原来的
        return head.val == val ? head.next : head;
    }

    /**
     * 生成递归深度的字符串
     *
     * @param depth 递归层数
     * @return depth*2个"--"
     */
    private String generateRecursionDepthStr(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 6, 3, 4, 5, 6};
        ListNode head = new ListNode(nums);
        ListNode result = (new SolutionDebug()).removeElements(head, 6, 1);
        System.out.println();
        System.out.println("递归结束，结果为：：" + result);
    }
}
/**
 * --第1层递归：head=1->2->6->3->4->5->6->NULL，要找的值为节点值为：6
 * ----第2层递归：head=2->6->3->4->5->6->NULL，要找的值为节点值为：6
 * ------第3层递归：head=6->3->4->5->6->NULL，要找的值为节点值为：6
 * --------第4层递归：head=3->4->5->6->NULL，要找的值为节点值为：6
 * ----------第5层递归：head=4->5->6->NULL，要找的值为节点值为：6
 * ------------第6层递归：head=5->6->NULL，要找的值为节点值为：6
 * --------------第7层递归：head=6->NULL，要找的值为节点值为：6
 * ----------------第8层递归：head=null，要找的值为节点值为：6
 * --------------第7层递归：head=6->NULL，要找的值为节点值为：6
 * ------------第6层递归：head=5->NULL，要找的值为节点值为：6
 * ----------第5层递归：head=4->5->NULL，要找的值为节点值为：6
 * --------第4层递归：head=3->4->5->NULL，要找的值为节点值为：6
 * ------第3层递归：head=6->3->4->5->NULL，要找的值为节点值为：6
 * ----第2层递归：head=2->3->4->5->NULL，要找的值为节点值为：6
 * --第1层递归：head=1->2->3->4->5->NULL，要找的值为节点值为：6
 *
 * 递归结束，结果为：：1->2->3->4->5->NULL
 */

5. 更多和链表相关的问题

标签：03,13,val,递归,int,head,2023,NULL,arr
From： https://www.cnblogs.com/lsgwr/p/17213391.html

相关文章

  • 解决：MISCONF Redis is configured to save RDB snapshots, but it's currently unable
    问题：解决：1.输入命令 redis-cli2.阻止redis尝试保存快照：configsetstop-writes-on-bgsave-errorno解决问题。 ......
  • day13 （2023.3.13）
    1.Object[][]二维数组存储表格数据 运行结果: 2.使用javabean和数组保存表格数据  运行结果: 3.Comparable接口(定义比较策略)  运行结果: 4.......
  • 2023春训练7
    训练地址：vjudgeC.PullYourLuck官方题解：TutorialF.ABCString我的代码：qiansui_code怎么说，我的代码想的还是太简单了。多说无益，看看官方题解吧。官方题解：Tutorial......
  • 13 响应重定向
    ​  响应重定向生活案例:张三向李四借钱1000元,李四说”我也没有,要不你去王五哪里看看?”,然后张三根据李四的指示,去找王五借钱响应重定向是通过HttpServletRespo......
  • 牛客 2022年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛 签到
    序题号标题已通过代码通过率我的状态AA+BProblem点击查看1705/4843通过，（贪心）BKomorebi的数学课点击查看1372/5349通过（快速幂）C次佛锅点击查看1070/5160......
  • 3.13每日总结——地铁查询系统1.0（第一次合作）
           思路首先是数据库存储：（1）采用List集合来存储线路上的站点信息。public static List lines = new ArrayList<>();（2）采用List集合来存储相邻站点信......
  • 每日总结-23.3.13
    课上内容地铁系统中的前两个查询部分//线路号查询,Stringname=线路名称publicPdchaxunxianlu(Stringname)throwsSQLException{Stringsql="s......
  • 3.13总结（结组）
    1，建立MySQL数据库并建立连接，再针对每一条线路以及换乘信息车站分别建立表。2，查询：制作查询界面，查询站点或线路的信息，并将其输出，并针对错误的输入报错。3，对于起点终点的查询，......
  • 3.13
    将北京地铁线路信息等用一个文本文件以subway.txt的形式保存起来，保存的信息包括地铁线路名称和拥有的站数、对应线路下的站点名称以及相邻站的距离，使得可以通过读取这个文......
  • Column 'gmt_create' cannot be null创建时间不允许为空[Mybatis-plus自动填充]
    首先确认各项代码部分无误1、创建包handler，创建自动填充类MyMetaObjectHandler：2、在实体类中添加注解3、Controller方法定义以上代码都没问题，目的是为了在不填时间......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99