前言

筆者在最近的項(xiàng)目開(kāi)發(fā)中，遇到了兩個(gè)父子關(guān)系緊密相關(guān)的場(chǎng)景：評(píng)論樹(shù)結(jié)構(gòu)、部門樹(shù)結(jié)構(gòu)。具體的需求如：找出某條評(píng)論下的所有子評(píng)論id集合，找出某個(gè)部門下所有的子部門id集合。

在之前的項(xiàng)目開(kāi)發(fā)經(jīng)驗(yàn)中，遞歸使用得是較少的，但作為一個(gè)在數(shù)據(jù)結(jié)構(gòu)操作中遍歷樹(shù)節(jié)點(diǎn)的解決方案，我還是拿出來(lái)作為技術(shù)積累進(jìn)行記錄以及分享。

一、什么是遞歸

1.1基本概念

這里就有必要簡(jiǎn)單介紹一下關(guān)于遞歸的基本概念了。

在 Java 中，遞歸是指在方法的定義中調(diào)用自身的過(guò)程，遞歸是基于方法調(diào)用棧的原理實(shí)現(xiàn)的：當(dāng)一個(gè)方法被調(diào)用時(shí)，會(huì)在調(diào)用棧中創(chuàng)建一個(gè)對(duì)應(yīng)的棧幀，包含方法的參數(shù)、局部變量和返回地址等信息。在遞歸中，方法會(huì)在自身的定義中調(diào)用自身，這會(huì)導(dǎo)致多個(gè)相同方法的棧幀依次入棧。當(dāng)滿足終止條件時(shí)，遞歸開(kāi)始回溯，棧幀依次出棧，方法得以執(zhí)行完畢。

遞歸的關(guān)鍵是定義好遞歸的終止條件和遞歸調(diào)用的條件。如果沒(méi)有適當(dāng)?shù)慕K止條件或遞歸調(diào)用的條件不滿足，遞歸可能會(huì)陷入無(wú)限循環(huán)，導(dǎo)致棧內(nèi)存溢出。

1.2優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 簡(jiǎn)化問(wèn)題：遞歸能夠?qū)?fù)雜問(wèn)題分解成更小規(guī)模的子問(wèn)題，簡(jiǎn)化了問(wèn)題的解決過(guò)程；
• 實(shí)現(xiàn)高效算法：遞歸在某些算法中能夠?qū)崿F(xiàn)高效的解決方法，如數(shù)據(jù)結(jié)構(gòu)操作中遍歷樹(shù)節(jié)點(diǎn)等。

缺點(diǎn)：

• 棧溢出風(fēng)險(xiǎn)：遞歸可能導(dǎo)致方法調(diào)用棧過(guò)深，造成棧內(nèi)存溢出；
• 性能損耗：遞歸調(diào)用需要?jiǎng)?chuàng)建多個(gè)棧幀，對(duì)系統(tǒng)資源有一定的消耗；
• 可讀性不高：遞歸的使用需要謹(jǐn)慎，不合理地使用可能造成代碼難以理解和調(diào)試。

1.3與迭代的區(qū)別

• 迭代（Iteration）

  迭代常見(jiàn)于 for 循環(huán)中：比如有一個(gè)集合 A，對(duì) A 進(jìn)行 foreach，在內(nèi)部設(shè)置條件，符合條件后將集合中某個(gè)元素的值替換成別的值。

迭代示例簡(jiǎn)圖

    @Test
    public void iterationTest(){
        ArrayList<String> list = new ArrayList<>();
        list.add("計(jì)算機(jī)技術(shù)");
        list.add("土木工程");
        list.add("市場(chǎng)營(yíng)銷");
        list.forEach(val -> {
            if (val.contains("計(jì)算機(jī)")){
                log.info("迭代前的的專業(yè)名稱：{}", val);
                String str = val.replace(val, "計(jì)算機(jī)科學(xué)與技術(shù)");
                log.info("迭代后的的專業(yè)名稱：{}", str);
            }
        });
    }

結(jié)果為：

迭代結(jié)果簡(jiǎn)圖

遞歸（Recursion）

遞歸的例子會(huì)在下一小節(jié)詳細(xì)給出。

二、實(shí)際案例

下面筆者以遞歸獲取某個(gè)評(píng)論id下面所有的子級(jí)評(píng)論id為例子，向大家介紹這個(gè)遞歸的過(guò)程。

首先，這里給出一個(gè)簡(jiǎn)單的數(shù)據(jù)庫(kù)評(píng)論表的 demo，id 是主鍵id 也是評(píng)論唯一 id，parent_id 是該條評(píng)論的父評(píng)論 id，status 為1表示審核通過(guò)的狀態(tài)。

其中，我們可以簡(jiǎn)單發(fā)現(xiàn)：這里21為第一層，28和29為第二層、31和32為第三層，草圖如下所示：

評(píng)論id簡(jiǎn)單層級(jí)示意圖

那么，我們?nèi)绾螌?1、28、29、31、32都放進(jìn)一個(gè)集合里返回呢？下面的代碼示例可以給你一個(gè)參考。

但是，在看代碼之前，有個(gè)問(wèn)題請(qǐng)你思考一下：

從21開(kāi)始后，遍歷的路線是21-28-29？還是21-28-31？還是21-29-32？或者是21-28-31-29-32？

下面是經(jīng)過(guò)脫敏處理后的參看代碼示例，注釋都寫得比較清楚了：

    /**
     * 這里可以看作是外部接口的調(diào)用，會(huì)得到遞歸的結(jié)果
     * @param id
     */
    private List<Integer> getIdListMethod(Integer id){
        ArrayList<Integer> idList = new ArrayList<>();
        this.getAllIdByRecursion(id, idList);
        log.info("遞歸后得到的id集合：{}", idList);
        return idList;
    }
    /**
     * 這里是遞歸的過(guò)程
     * @param id
     * @param idList
     */
    private void getAllIdByRecursion(Integer id, List<Integer> idList){
        LambdaQueryWrapper<Comment> wrapper = new LambdaQueryWrapper<>();
        //先把該id下所有的第一級(jí)子id找到
        wrapper.eq(Comment::getParentId, id).eq(Comment::getStatus, NumberUtils.INTEGER_ONE);
        List<Comment> commentList = this.list(wrapper);
        for (Comment children : commentList){
            this.getAllIdByRecursion(children.getId(), idList);
        }
        log.info("放入集合的id為：{}", id);
        idList.add(id);
    }

上面問(wèn)題的答案是：遞歸后得到的id集合：[21,28,31,29,32]，原因就是：迭代會(huì)從一棵樹(shù)開(kāi)始遍歷到底，沒(méi)有元素了再?gòu)念^開(kāi)始遍歷，依次迭代，類似于深度優(yōu)先遍歷。

比如：21下面有兩個(gè)子id：28和29，那么會(huì)先走21-28-31這棵樹(shù)，到底了后接著按照29-32遍歷。

三、改進(jìn)方案

我根據(jù)自己的開(kāi)發(fā)經(jīng)驗(yàn)，可以從控制遞歸層數(shù)和改用 Stream 這兩種辦法來(lái)對(duì)遞歸進(jìn)行改進(jìn)。

3.1控制遞歸層數(shù)

JVM 默認(rèn)控制的遞歸最大深度限制在 1000 層，可以通過(guò)設(shè)置 JVM 參數(shù)來(lái)控制其深度，如：

java -Xss5m #表示將每個(gè)線程的棧內(nèi)存大小設(shè)置為5MB，已經(jīng)是比較大了

或者在代碼層面對(duì)遞歸的層數(shù)進(jìn)行控制：

        int depth = 0;
        //遞歸方法調(diào)用
        for (int i = 0; i < 20; i++) {
            depth++;
        }
        if (depth > 100){
            //其它操作
        }

3.1用 Stream 遍歷

核心思路是：先數(shù)據(jù)庫(kù)全量查詢（10萬(wàn)條以內(nèi)），內(nèi)存中使用 Stream 流操作、Lambda 表達(dá)式、Java 地址引用進(jìn)行篩選。

適用于數(shù)據(jù)總量不多的情況，如：部門樹(shù)，部門數(shù)量一般情況是比較固定的，一個(gè)組織或者公司最多也就幾百上千個(gè)部門。

詳情可以看我這篇文章：https://www.cnblogs.com/CodeBlogMan/p/17965824

四、文章小結(jié)

筆者確實(shí)不推薦在項(xiàng)目中過(guò)度使用遞歸，但是合理使用的話也能成為解決特定問(wèn)題的一個(gè)利器，至于怎么拿捏這個(gè)度，那就要看大家的具體情況了。

Java 項(xiàng)目中對(duì)使用遞歸的理解分享到這里就結(jié)束了，文章如有不足和錯(cuò)誤，或者你有更好的解決思路，歡迎大家的指正和交流！

到此這篇關(guān)于Java 項(xiàng)目中對(duì)使用遞歸的理解分享的文章就介紹到這了,更多相關(guān)Java 項(xiàng)目中對(duì)使用遞歸的理解分享內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論