摘要：整理一下，形成今天的內容算法中的遞歸算法。解決來看一下，最終形態的遞歸方法是什么樣子遞歸運算創建樹結構聲明靜態變量給靜態變量累加值賦值閉合標簽這樣就可以解決了。所以，在之后的遞歸算法中，應該小心謹慎，避免出現問題。

原文是在我自己博客中，小伙伴也可以點閱讀原文進行跳轉查看，還有好聽的背景音樂噢~

????遞歸，在編碼中應該算是一種很常見的算法了。之前在學習C語言的時候，也同樣了解過一些基本的算法，比如斐波那契。在學習的時候，對算法這種編程技巧就有了一種濃濃的敬畏之心，因為覺得會算法的人就很厲害了，可以把很長的代碼塊通過一段簡短的算法解決并得到想要的結果。

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

借用百科的一段話來表述就是：

一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法。

同樣引用百科的一句話，個人覺得非常經典：

用有限的語句來定義對象的無限集合；

這句話什么意思呢，通俗點來理解就是，我程序只有一套，但是我可以通過遞歸（自身調用自身）的特性，不管你有多少個值，我都能妥妥的給你按照特定的程序邏輯處理嘍。（就是這么強勢，嘿嘿！）

自己之前對遞歸的理解就是自己調用自己，通過多次的自己調用自身，通過同一套程序方法，來達到解決問題的目的；這種方法可以明顯的減少代碼量，而且靈活，尤其是在多重循環的時候，可以采用遞歸來替代。但是這種方法也有缺點，就是增加了程序了運行速度，而且有時候可能會因為編碼不當，造成死循環、棧溢出等問題。但是只要用好，解決問題還是不差的；

今天在工作中，遇到一個把無限分類的多維數組轉換成html樹的時候，就遇到了點小麻煩，可能是因為一時馬虎，當局者迷的緣故，自己就像掉進死循環里，一直出不來，后來，也是在請教身邊的朋友后，才得到解決，下面我們來看一下出現了什么問題（其實問題已經提在了SF社區上，問題標題是多維數組分類樹 組合html樹的問題？（遞歸），有興趣的小伙伴可以去看下）：

最初的數組結構是一個無限分類的多維數組：

由上圖可以看到，這個數組的childs下標里面對應的就是子分類，分類可以有無限個。我們要把它組裝成下圖的理想形態：

雖然看著很簡單，但是實際上走了不少彎路，最后卡在了一個點上，始終沒出來。我最開始的遞歸方法是：

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

通過測試得到了下圖的錯誤內容：

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

static $htmlTree;
$htmlTree .= "
";

以及if里的

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

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

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

改為：

creatHtmlTree($value["childs"]);

即可。這樣，他在遞歸運算的時候就可以通過

$htmlTree .= "
";

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

$htmlTree .= "
";

$htmlTree .= "
";

這四行代碼來給$htmlTree累加數值就可以了。

來看一下，最終形態的遞歸方法是什么樣子：

// 遞歸運算創建html樹結構
function creatHtmlTree($tree)
{
    // 聲明靜態變量
    static $htmlTree;
    $htmlTree .= "
";
    foreach ($tree as $key => $value) {
        // 給靜態$htmlTree變量累加值
        $htmlTree .= "
{$value["name"]}  Goes somewhere";
        if (isset($value["childs"]) && is_array($value["childs"])) {
            creatHtmlTree($value["childs"]);
        } 
        $htmlTree .= "
";
    }
    // 賦值ul閉合標簽
    $htmlTree .= "
";
    return $htmlTree;
}

這樣就可以解決了。同樣還有另外一種方式，那就是通過返回值的方式，來進行遞歸運算：

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

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

今天為了測試和解決遞歸算法帶來的問題，特意找了段代碼進行測試，也是我下午一直在實驗的demo，手癢癢的小伙伴，可以立馬copy到本地親自體驗一下：

1,"parentid"=>0,"name"=>"中國"],
    ["id"=>2,"parentid"=>0,"name"=>"美國"],
    ["id"=>3,"parentid"=>0,"name"=>"韓國"],
    ["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"=>"首爾"],
];


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

/**
 * 多維數組樹形結構
 */
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;
}

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


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

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

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

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

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

遞歸需要有邊界條件、遞歸前進段和遞歸返回段

當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回

這大概說的就是遞歸的運行條件吧。
完。