摘要：整理一下，形成今天的內(nèi)容算法中的遞歸算法。解決來(lái)看一下，最終形態(tài)的遞歸方法是什么樣子遞歸運(yùn)算創(chuàng)建樹(shù)結(jié)構(gòu)聲明靜態(tài)變量給靜態(tài)變量累加值賦值閉合標(biāo)簽這樣就可以解決了。所以，在之后的遞歸算法中，應(yīng)該小心謹(jǐn)慎，避免出現(xiàn)問(wèn)題。

原文是在我自己博客中，小伙伴也可以點(diǎn)閱讀原文進(jìn)行跳轉(zhuǎn)查看，還有好聽(tīng)的背景音樂(lè)噢~

????遞歸，在編碼中應(yīng)該算是一種很常見(jiàn)的算法了。之前在學(xué)習(xí)C語(yǔ)言的時(shí)候，也同樣了解過(guò)一些基本的算法，比如斐波那契。在學(xué)習(xí)的時(shí)候，對(duì)算法這種編程技巧就有了一種濃濃的敬畏之心，因?yàn)橛X(jué)得會(huì)算法的人就很厲害了，可以把很長(zhǎng)的代碼塊通過(guò)一段簡(jiǎn)短的算法解決并得到想要的結(jié)果。

今天在實(shí)際工作中也遇到了算法中一些問(wèn)題。整理一下，形成今天的內(nèi)容【算法中的遞歸算法】。

借用百科的一段話來(lái)表述就是：

一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法。

同樣引用百科的一句話，個(gè)人覺(jué)得非常經(jīng)典：

用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合；

這句話什么意思呢，通俗點(diǎn)來(lái)理解就是，我程序只有一套，但是我可以通過(guò)遞歸（自身調(diào)用自身）的特性，不管你有多少個(gè)值，我都能妥妥的給你按照特定的程序邏輯處理嘍。（就是這么強(qiáng)勢(shì)，嘿嘿?。?/p>

自己之前對(duì)遞歸的理解就是自己調(diào)用自己，通過(guò)多次的自己調(diào)用自身，通過(guò)同一套程序方法，來(lái)達(dá)到解決問(wèn)題的目的；這種方法可以明顯的減少代碼量，而且靈活，尤其是在多重循環(huán)的時(shí)候，可以采用遞歸來(lái)替代。但是這種方法也有缺點(diǎn)，就是增加了程序了運(yùn)行速度，而且有時(shí)候可能會(huì)因?yàn)榫幋a不當(dāng)，造成死循環(huán)、棧溢出等問(wèn)題。但是只要用好，解決問(wèn)題還是不差的；

今天在工作中，遇到一個(gè)把無(wú)限分類的多維數(shù)組轉(zhuǎn)換成html樹(shù)的時(shí)候，就遇到了點(diǎn)小麻煩，可能是因?yàn)橐粫r(shí)馬虎，當(dāng)局者迷的緣故，自己就像掉進(jìn)死循環(huán)里，一直出不來(lái)，后來(lái)，也是在請(qǐng)教身邊的朋友后，才得到解決，下面我們來(lái)看一下出現(xiàn)了什么問(wèn)題（其實(shí)問(wèn)題已經(jīng)提在了SF社區(qū)上，問(wèn)題標(biāo)題是多維數(shù)組分類樹(shù) 組合html樹(shù)的問(wèn)題？（遞歸），有興趣的小伙伴可以去看下）：

最初的數(shù)組結(jié)構(gòu)是一個(gè)無(wú)限分類的多維數(shù)組：

由上圖可以看到，這個(gè)數(shù)組的childs下標(biāo)里面對(duì)應(yīng)的就是子分類，分類可以有無(wú)限個(gè)。我們要把它組裝成下圖的理想形態(tài)：

雖然看著很簡(jiǎn)單，但是實(shí)際上走了不少?gòu)澛?，最后卡在了一個(gè)點(diǎn)上，始終沒(méi)出來(lái)。我最開(kāi)始的遞歸方法是：

function creatHtmlTree($tree)
{
    // 生命一個(gè)靜態(tài)變量
    static $htmlTree;
    $htmlTree .= "
";
    foreach ($tree as $key => $value) {
        $htmlTree .= "
{$value["name"]}  Goes somewhere";
        if (isset($value["childs"]) && is_array($value["childs"])) {
            // 每次的結(jié)果累加到靜態(tài)變量上
            $html = creatHtmlTree($value["childs"]);
            $htmlTree .= $html;
        } 
        $htmlTree .= "
";
    }
    $htmlTree .= "
";
    return $htmlTree;
}

通過(guò)測(cè)試得到了下圖的錯(cuò)誤內(nèi)容：

我們可以看到，它給$htmlTree這個(gè)變量給了多余的值，通過(guò)求教才明白，我的代碼中

static $htmlTree;
$htmlTree .= "
";

以及if里的

$html = creatHtmlTree($value["childs"]);
$htmlTree .= $html;

代碼邏輯寫的有問(wèn)題，問(wèn)題在于，既然設(shè)定了$htmlTree為靜態(tài)變量，那么在遞歸中的每一次計(jì)算中，都默認(rèn)已經(jīng)給$htmlTree賦予了最后的計(jì)算結(jié)果，我在if里又把結(jié)果加了一次，所以才造成了輸出出現(xiàn)問(wèn)題的情況，那么如何改成呢？只需把：

$html = creatHtmlTree($value["childs"]);
$htmlTree .= $html;

改為：

creatHtmlTree($value["childs"]);

即可。這樣，他在遞歸運(yùn)算的時(shí)候就可以通過(guò)

$htmlTree .= "
";

$htmlTree .= "
{$value["name"]}  Goes somewhere";

$htmlTree .= "
";

$htmlTree .= "
";

這四行代碼來(lái)給$htmlTree累加數(shù)值就可以了。

來(lái)看一下，最終形態(tài)的遞歸方法是什么樣子：

// 遞歸運(yùn)算創(chuàng)建html樹(shù)結(jié)構(gòu)
function creatHtmlTree($tree)
{
    // 聲明靜態(tài)變量
    static $htmlTree;
    $htmlTree .= "
";
    foreach ($tree as $key => $value) {
        // 給靜態(tài)$htmlTree變量累加值
        $htmlTree .= "
{$value["name"]}  Goes somewhere";
        if (isset($value["childs"]) && is_array($value["childs"])) {
            creatHtmlTree($value["childs"]);
        } 
        $htmlTree .= "
";
    }
    // 賦值ul閉合標(biāo)簽
    $htmlTree .= "
";
    return $htmlTree;
}

這樣就可以解決了。同樣還有另外一種方式，那就是通過(guò)返回值的方式，來(lái)進(jìn)行遞歸運(yùn)算：

// 遞歸運(yùn)算創(chuàng)建html樹(shù)結(jié)構(gòu)
function creatHtmlTree($tree)
{
    // $htmlTree為普通局部變量;
    $htmlTree .= "
";
    
    foreach ($tree as $key => $value) {
        // 給變量$htmlTree累加值
        $htmlTree .= "
{$value["name"]}  Goes somewhere";
        if (isset($value["childs"]) && is_array($value["childs"])) {
            // 遞歸中每次的結(jié)果累加到$htmlTree
            $htmlTree .= creatHtmlTree($value["childs"]);
        } 
        $htmlTree .= "
";
    }
    // 賦值ul閉合標(biāo)簽
    $htmlTree .= "
";
    return $htmlTree;
}

通過(guò)這種返回值累加的算法，也同樣可以得到想要的結(jié)果。

今天為了測(cè)試和解決遞歸算法帶來(lái)的問(wèn)題，特意找了段代碼進(jìn)行測(cè)試，也是我下午一直在實(shí)驗(yàn)的demo，手癢癢的小伙伴，可以立馬copy到本地親自體驗(yàn)一下：

1,"parentid"=>0,"name"=>"中國(guó)"],
    ["id"=>2,"parentid"=>0,"name"=>"美國(guó)"],
    ["id"=>3,"parentid"=>0,"name"=>"韓國(guó)"],
    ["id"=>4,"parentid"=>1,"name"=>"北京"],
    ["id"=>5,"parentid"=>1,"name"=>"上海"],
    ["id"=>6,"parentid"=>1,"name"=>"廣西"],
    ["id"=>7,"parentid"=>6,"name"=>"桂林"],
    ["id"=>8,"parentid"=>6,"name"=>"南寧"],
    ["id"=>9,"parentid"=>6,"name"=>"柳州"],
    ["id"=>10,"parentid"=>2,"name"=>"紐約"],
    ["id"=>11,"parentid"=>2,"name"=>"華盛頓"],
    ["id"=>12,"parentid"=>3,"name"=>"首爾"],
];


 /**格式化數(shù)組輸出**/
function p($arr)
{
    echo "
";
    echo "========================開(kāi)始========================";
    echo "
";
    if( $arr ){
        print_r($arr);
    } else {
        echo "此值為空";
    }
    echo "
";
    echo "========================結(jié)束========================";
    echo "
";
}

/**
 * 多維數(shù)組樹(shù)形結(jié)構(gòu)
 */
function tree($data, $pid = 0)
{
    $children = [];
    foreach ($data as $key => $value) {

        if ($value["parentid"] == $pid) {
            $children[] = $value;
        }
    }
    if (empty($children)) {
        return null;
    }

    foreach ($children as $key => $value) {
        $chid = tree($data, $value["id"]);
        if ($chid != null) {
            $children[$key]["childs"] = $chid;
        }
    }

    return $children;
}

// 遞歸運(yùn)算創(chuàng)建html樹(shù)結(jié)構(gòu)
function creatHtmlTree($tree)
{
    // $htmlTree為普通局部變量;
    $htmlTree .= "
";
    
    foreach ($tree as $key => $value) {
        // 給$htmlTree變量累加值
        $htmlTree .= "
{$value["name"]}  Goes somewhere";
        if (isset($value["childs"]) && is_array($value["childs"])) {
            // 遞歸中每次的結(jié)果累加到$htmlTree
            $htmlTree .= creatHtmlTree($value["childs"]);
        } 
        $htmlTree .= "
";
    }
    // 賦值ul閉合標(biāo)簽
    $htmlTree .= "
";
    return $htmlTree;
}


$tree = tree($data);
$htmlTree = creatHtmlTree($tree);

p($tree);
p($htmlTree);

算法，這門技巧，是我向往的高級(jí)玩意兒。覺(jué)得它挺炫的，在開(kāi)頭我就有提到，可以用極短的代碼解決復(fù)雜的業(yè)務(wù)程序，大大減少的代碼量。但它同樣也像一顆隱形炸彈一樣，也充滿著威脅。所以，在之后的遞歸算法中，應(yīng)該小心謹(jǐn)慎，避免出現(xiàn)問(wèn)題。

好了，今天就分享到這里，以上。

在百科里看到遞歸解釋的兩句話，也同樣經(jīng)典，奉上：

遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段

當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回

這大概說(shuō)的就是遞歸的運(yùn)行條件吧。
完。