[JavaScript知识库] JavaScript - js进阶

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> JavaScript知识库 -> JavaScript - js进阶 - 递归 -> 正文阅读

[JavaScript知识库]JavaScript - js进阶 - 递归

递归思想

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>递归思想</title>
    </head>
    <body>
        <!-- 
        递归: recursive, 用相同的代码去解决类似的问题

        本质概念: 有一个大问题要解决, 解决的过程中发现里面有小问题: 特点是与大问题性质一样,但是规模变小, 找到这种最小的问题(最优子结构), 给出解决方案: 可以慢慢的从最小的解决到最大, 最终解决所有问题

        编程中的递归: 写一个函数解决大问题, 在函数的内部调用自己去解决碰到的小问题: 函数内部调用自己

        递归解决问题的方案: 用空间换时间
        1. 空间: 同时运行很多自己这个函数, 占用足够内存( 有可能会崩)
        2. 时间: 运行的时间

        递归注意事项
        1. 递归点: 何时调用自己, 遇到性质相同的问题, 但是规模较小
        2. 递归出口: 何时不再调用自己(一直调用自己: 导致内存崩溃)

     -->
    </body>
</html>

非递归解决问题

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>递归思想 - 非递归解决问题</title>
    </head>
    <body></body>
    <script>
        const cities = [
            {
                name: "广东",
                children: [
                    {
                        name: "广州",
                        children: [
                            {
                                name: "越秀",
                            },
                            {
                                name: "天河",
                                children: [
                                    {
                                        name: "吉山",
                                    },
                                ],
                            },
                        ],
                    },
                    {
                        name: "深圳",
                        children: [
                            {
                                name: "南山",
                            },
                        ],
                    },
                ],
            },
        ];

        // 需求: 将省市信息 用div显示出来

        // 遍历数组: 取出对象, 取出对象里面的name属性, 用div装起来
        cities.forEach((item) => {
            document.body.innerHTML += `<div>${item.name}</div>`;

            // 判定对象是否存在children属性: children跟cities长相一样, 只是小一点
            if (item.children) {
                // item.children是一个数组
                item.children.forEach((item) => {
                    document.body.innerHTML += `<div>${item.name}</div>`;

                    if (item.children) {
                        // item.children是一个数组
                        item.children.forEach((item) => {
                            document.body.innerHTML += `<div>${item.name}</div>`;

                            if (item.children) {
                                // item.children是一个数组
                                item.children.forEach((item) => {
                                    document.body.innerHTML += `<div>${item.name}</div>`;

                                    if (item.children) {
                                        // item.children是一个数组
                                        item.children.forEach((item) => {
                                            document.body.innerHTML += `<div>${item.name}</div>`;
                                        });
                                    }
                                });
                            }
                        });
                    }
                });
            }
        });

        // 总结效果
        // 1. 代码重复度很高: 4层if条件判定
        // 2. 如果数据发生了改变: 代码要跟着改变
    </script>
</html>

递归思想 - 递归解决 - 实现遍历

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>递归思想 - 实现遍历</title>
    </head>
    <body></body>
    <script>
        const cities = [
            {
                name: "广东",
                children: [
                    {
                        name: "广州",
                        children: [
                            {
                                name: "越秀",
                            },
                            {
                                name: "天河",
                                children: [
                                    {
                                        name: "吉山",
                                        children: [
                                            {
                                                name: "张三",
                                            },
                                        ],
                                    },
                                ],
                            },
                        ],
                    },
                    {
                        name: "深圳",
                        children: [
                            {
                                name: "南山",
                            },
                        ],
                    },
                ],
            },
        ];

        // 递归: 函数内部调用自己

        // 1. 先定义一个函数: 通常都需要接收参数(至少1个)
        // 2. 写好代码: 解决最大的问题(当前是最外层数组遍历,取出对象中的name属性显示出来)
        // 3. 寻找递归出口: 数组遍历结束, 里面没有了对象: 隐式出口
        // 4. 寻找递归点: 与要解决的问题性质一样,规模较小: 只要有children属性, 就与data(cities)性质一样,只是规模较小: 递归调用自己
        function setHtml(data) {
            // data是一个数组
            data.forEach((item) => {
                document.body.innerHTML += `<div>${item.name}</div>`;

                // 递归点: item.children是存在的
                if (item.children) setHtml(item.children);
            });
        }

        setHtml(cities);
    </script>
</html>

递归思想 - 显示出口

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>递归思想 - 显示出口</title>
    </head>
    <body></body>
    <script>
        // 需求: 有一组数字,规则如下
        // 1   1   2   3   5   8   13  21   ...
        // 规则: 当前数字 = 前两个之和(从第3个开始)
        // 分波那契数列

        // 问题: 请求出, 任意位置的 对应的数字的值
        // 如第1个: 1
        // 第2个: 1
        // 第3个: 2
        // ...

        // 递归实现: n代表位置,从1开始
        function fbnq(n) {
            // 寻找递归出口: 不要再自己调用自己
            // 如果n为1或者2: 直接返回1
            if (n <= 2) return 1;

            // 递归点
            return fbnq(n - 1) + fbnq(n - 2);
        }

        // 测试代码执行的时间
        console.time("随便"); // 开始时间: 用 随便 做记号

        console.log(fbnq(50));

        console.timeEnd("随便"); // 结束时间: 用 随便 对应开始时间
    </script>
</html>