Lian
文章目录 站点概览

Lian

make thing better and simpler.

98 文章
64 标签

编程新手知识集1-递归

发布于 2024-11-21 | 标签: javascript 、 python | 11分钟 | 2300字数

一. 前言

递归, 通常可以被视为编程新手遇到的第一道坎.

递归算法( recursive algorithm [4], recursion algorithm [5]) 在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法. 递归式方法可以被用于解决很多的计算机科学问题, 因此它是计算机科学中十分重要的一个概念. 绝大多数编程语言支持函数的自调用, 在这些语言中函数可以通过调用自身来进行递归. 计算理论可以证明递归的作用可以完全取代循环, 因此在很多函数编程语言( 如Scheme) 中习惯用递归来实现循环.

递归算法_百度百科

递归应用的最典型例子: 汉诺塔游戏

img

递归函数 - Python教程 - 廖雪峰的官方网站

相关的概念这里就不一一赘述,下面主要是一些递归使用的细节和在不同语言之下的使用.

1.1 为什么需要递归?

假如写过大型爬虫的, 都会遇到这个问题, 如何将整个站点的页面全部爬下来, 而整个站点的页面url数量是非常惊人的.

即, 访问a页面, 获得a页面的所有链接, 然后选其中的一个链接访问, 然后获得该页面的所有的链接, 继续往复循环, 记录下访问过的链接, 直到所有能够获得的链接都被访问一遍.

# 伪代码

visited_list = []
def spider(url):
    visited_list.append(url)
    r= request.get(url)
    urls = get_all_url(r.response)
    for l in urls:
        if l not in visited_list:
            spider(url)

假如上面的逻辑理解还是太困难, 那么累加或者累乘更容易理解递归的好处.

∑i=1ni\sum_{i=1}^{n} i

分别使用JavaScript, python, vba, mysql四种语言实现累加.

// js

const total_sum = (num) => num > 0 ? num + total_sum(num - 1) : 0;
console.log(total_sum(5));

# python

def total_sum(num): return num + total_sum(num - 1) if num > 0 else 0

print(total_sum(5))

' vba

Function total_sum(num)
    If num > 0 Then
        total_sum = num + total_sum(num - 1)
    Else
        total_sum = 0
    End If
End Function

Sub test()
    Debug.Print total_sum(5)
End Sub

(vba作为古老且不更新的语言, 所以代码不怎么"优雅"(无法实现一行代码))

# mysql

WITH RECURSIVE numbers AS (
    SELECT 1 AS number, 1 AS cumulative_sum
    UNION ALL
    SELECT number + 1, cumulative_sum + (number + 1)
    FROM numbers
    WHERE number < 10
)
SELECT cumulative_sum
FROM numbers
ORDER BY number DESC
LIMIT 1;

mysql8之后引入的新特性, 不需要创建额外变量来实现上述的累加.

+----------------+
| cumulative_sum |
+----------------+
|             55 |
+----------------+
1 row in set (0.01 sec)

可以看到递归可以很好地处理不断重复自身动作的问题(老和尚给小和尚讲山里故事的问题).

1.2 尾递归

详解什么是尾递归( 通俗易懂, 示例讲解) -CSDN博客

尾调用优化 - 阮一峰的网络日志

尾递归, 顾名思义, 在代码的末端(最后一步)调用自身.

尾递归优化, 即相关的语言对于尾递归进行了底层的优化, 使得递归中一些常见的问题得到优化, 如(比较容易)堆栈溢出, 性能等.

img

需要注意的是python并没有原生支持尾递归优化, 同时需要注意python对于递归深度的限制.

Python 3.11.7 | packaged by Anaconda, Inc. | (main, Dec 15 2023, 18:05:47) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getrecursionlimit()
1000

默认状态下, python的递归深度限制.

sys.setrecursionlimit(5000)

python手动修改递归深度限制.

def test(n):
    try:
        test(n+1)
    except:
        print(n)

test(0)

# 996

注意, 堆栈溢出, 可能更早发生, 假如运行过程中内存的占用快速增长.

const test =  n =>  {
    try {
        test(n + 1)
    } catch{
        console.log(n)
    }
}
test(0);

// 9878

上述的js代码, 运行到9878时, 出现错误

const test = n => n > 0 && test(n - 1);
test(10000)

但是改成这个形式, 10000也没有出现错误.

Sub test()
    Debug.Print max_r(0) ' 1278
    ' max_t 1000
End Sub

Private Function max_r(n) As Long
    On Error GoTo errhandle:

    max_r = max_r(n + 1)
    Exit Function
errhandle:
    max_r = n
End Function

' 改成1000, 都还是出现错误, 反而递归深度减少了
Private Function max_t(n)
    If n > 0 Then max_t n - 1
End Function

64位excel2021, 最大的递归深度为1278.

1.3 缺点

特性 递归实现 循环实现
可读性 通常更简洁, 易于理解问题的结构 可能较冗长, 但在简单情况下更直观
性能 可能导致栈溢出, 尤其在深度递归时 通常更高效, 避免了函数调用的开销
终止条件 明确的基本情况, 通常是一个简单的条件 循环条件, 通常是一个范围或计数器
一般规律 通过递归关系定义问题, 通常简洁明了 通过迭代逻辑处理问题, 可能需要更多的代码行

最全面的递归算法详解, 一篇足矣( 高手必备) -CSDN博客

虽然递归在各种算法中也应用非常广泛, 但是其也容易遇到一些问题, 如: 速度.

以斐波那契数列_百度百科为例:

import time

# 递归
def fib(num):
    if num < 3:
        return 1
    else:
        return fib(num - 1) + fib(num - 2)

s = time.time()
print(fib(20))
e = time.time()
print(e - s)

0.0009999275207519531

# 迭代
def fib_yield(n):
    a, b = 0, 1
    yield a
    for _ in range(n):
        a, b = b, a + b
        yield a

s = time.time()
print(list(fib_yield(100)))
e = time.time()
print(e - s)

[Running] python -u "d:\Code\python_workspace\test.py"

0.0

递归计算, 仅仅是计算数列的前20位, 消耗的时间就完全超过普通迭代的方式计算前100位需要的时间.

二. 问题

这里使用递归来解决两个对象的数据合并问题, 按照左边对象的模板获取右侧对象同键名的数据

例如:

{
    owner: {
        mid: 0,
            name: '',
                face: ''
    }
}

不管同名键是否处于相同层级, 只需要键名相同即可

img

{
    const a = {
        id: 0,
        bvid: '',
        cid: 0,
        goto: '',
        uri: '',
        pic: '',
        pic_4_3: '',
        title: '',
        duration: 0,
        pubdate: 0,
        owner: { mid: 0, name: '', face: '' },
        stat: { view: 0, like: 0, danmaku: 0, vt: 0 },
        av_feature: null,
        is_followed: 0,
        rcmd_reason: { reason_type: 0 },
        show_info: 0,
        track_id: '',
        pos: 0,
        room_info: null,
        ogv_info: null,
        business_info: null,
        is_stock: 0,
        enable_vt: 0,
        vt_display: '',
        dislike_switch: 0,
        dislike_switch_pc: 0
    };
    const b = {
        "aid": 36660774,
        "videos": 1,
        "tid": 21,
        "tname": "日常",
        "copyright": 2,
        "pic": "http://i0.hdslb.com/bfs/archive/9059dad274d598ae3c5efd0ba814c573458a6569.jpg",
        "title": "超甜! 李诞和女朋友黑尾酱的日常[4_5] 【1080P】",
        "pubdate": 1543059962,
        "ctime": 1543059962,
        "desc": "YouTube",
        "state": 0,
        "duration": 572,
        "rights": {
            "bp": 0,
            "elec": 0,
            "download": 0,
            "movie": 0,
            "pay": 0,
            "hd5": 0,
            "no_reprint": 0,
            "autoplay": 1,
            "ugc_pay": 0,
            "is_cooperation": 0,
            "ugc_pay_preview": 0,
            "no_background": 0,
            "arc_pay": 0,
            "pay_free_watch": 0
        },
        "owner": {
            "mid": 7296171,
            "name": "熊肚兜",
            "face": "https://i0.hdslb.com/bfs/face/cba183748bdc5fc9628d41d3172ea4a89ec740ee.png"
        },
        "stat": {
            "aid": 36660774,
            "view": 2571,
            "danmaku": 2,
            "reply": 0,
            "favorite": 27,
            "coin": 3,
            "share": 7,
            "now_rank": 0,
            "his_rank": 0,
            "like": 12,
            "dislike": 0,
            "vt": 0,
            "vv": 2571
        },
        "dynamic": "#生活记录##李诞##美女#",
        "cid": 64378335,
        "dimension": {
            "width": 1920,
            "height": 1080,
            "rotate": 0
        },
        "short_link_v2": "https://b23.tv/BV1it411y7wR",
        "cover43": "",
        "bvid": "BV1it411y7wR",
        "season_type": 0,
        "is_ogv": false,
        "ogv_info": null,
        "rcmd_reason": "",
        "enable_vt": 0,
        "ai_rcmd": {
            "id": 36660774,
            "goto": "av",
            "trackid": "web_related_0.router-related-1821887-6f9bc77648-z4fch.1731814326677.785",
            "uniq_id": ""
        }
    };
    const get_data = (key, obj) => {
        const d = obj[key];
        if (d === undefined) {
            for (const k in obj) {
                const tmp = obj[k];
                if (tmp && tmp.constructor === Object) {
                    const m = get_data(key, tmp);
                    if (m === undefined) continue;
                    return m; // 当获得数据后, 跳出循环遍历
                }
            }
        } else {
            return d;
        }
        return undefined;
    };
    const get_key = (data) => {
        // 递归调用, 遍历清空各层级的内容, 不涉及数组
        if (data && data.constructor === Object) {
            for (const key in data) {
                const tmp = data[key];
                const vtype = typeof tmp;
                if (vtype === 'string') data[key] = get_data(key, b) ?? ''; // ??, 空值判断符
                else if (vtype === 'number') data[key] = get_data(key, b) ?? 0;
                else if (tmp) get_key(tmp);
            }
        }
    };
    get_key(a);
    console.log(a);
}

三. 小结

第一次接触到递归是在刚接触vba的时候, 作为一个菜鸟, 就想写个文档管理的程序, 涉及到使用vbs的fso(文件管理系统)对文件夹进行遍历, 花了大概一个星期才完全理解这个概念.

' 代码为文心一言缩写

Sub TraverseFiles()
    Dim fso As FileSystemObject
    Dim folder As folder
    Dim subFolder As folder
    Dim file As file
    Dim rootPath As String

    ' 初始化文件系统对象
    Set fso = New FileSystemObject

    ' 指定要遍历的文件夹路径
    rootPath = "D:\test" ' 修改为你的文件夹路径

    ' 获取根文件夹
    Set folder = fso.GetFolder(rootPath)

    ' 调用递归函数遍历文件夹及其子文件夹
    TraverseFolder folder

    ' 清理对象
    Set fso = Nothing
End Sub

Private Sub TraverseFolder(ByVal folder As folder)
    Dim subFolder As folder
    Dim file As file

    ' 遍历当前文件夹中的所有文件
    For Each file In folder.Files
        Debug.Print "File: " & file.Path
    Next file

    ' 遍历当前文件夹中的所有子文件夹
    For Each subFolder In folder.SubFolders
        Debug.Print "SubFolder: " & subFolder.Path
        ' 递归调用遍历子文件夹
        TraverseFolder subFolder
    Next subFolder
End Sub
# javascript # python
IndexedDB使用摘要 下一篇
已运行:
浏览数: 次 | 访客数: 人
Powered by Kyouichirou