秒懂php递归算法

来源：网络文章列表 2019-05-14 8

本文傻瓜式的讲解了php的递归算法。php递归算法在项目中用到比较多的地方是获取商品分类或者其他的分类，以及邀请人等等~还有一些比如阶乘，斐波那契数列，汉诺塔也用到了递归算法。所以递归的用途还是很广的，递归另一个令人印象深刻的就是简单事情重复做。

小白自学php一段时间后，今天我们讲下php递归算法，php递归总结下说的最多的一句话就是：递归就是自己调用自己！没错，这么理解递归是没什么问题的，但是递归的一些特性和细节需要注意下，否则单纯的自己调用自己兴趣你就走到死循环里了。

php递归算法在项目中用到比较多的地方是获取商品分类或者其他的分类，以及邀请人等等~还有一些比如阶乘，斐波那契数列，汉诺塔也用到了递归算法，php递归实现面包屑导航等等。所以递归的用途还是很广的，递归另一个令人印象深刻的就是简单事情重复做。

下面我们开始说道说道递归

举个递归小例子，比如，

张三去和李四借钱，李四说你等一下，我去找王五借给你，

然后李四去找王五借钱，王五说你等一下，我去找赵六借给你，

最后王五找赵六借钱，赵六借给了王五。（这里就是递归出口）

这样的故事是不是在做很多重复的事情，像这样的情况下就可以使用递归，递归需要几个条件：

1，递归必须要有边界条件，也就是递归出口（退出递归）

2，递归前进段和递归返回段，也就是最后得到的值

3，当边界条件（递归出口）不满足时，递归前进；当边界条件（递归出口）满足时，递归返回。

傻瓜式理解递归，就是忘记递归，假设它的子问题已经解决，从上面的例子说就是假设李四已经有钱。

php递归场景 - 斐波那契数列

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

已知前两项的和，求第三项的和，因为重复用到这个方法，所以用到递归去解：

斐波那契数列的规律是当前项等于前两项的和，得到的公式是f(n)=f(n-1)+f(n-2);这里的n表示第几项

递归代码实现：

这里假设子问题已经解决，加入求第10项的值公式为：f(10)=f(9)+f(8)故而出现上面的公式

function f($n){
    if($n==1 || $n==2){
        return 1; // 递归出口，
    }
    return f($n-1)+f($n-2); // 假设子问题已经解决（假设李四已经有钱）
}

用迭代的方法求斐波那契数列：

function f($n){
    $a = 1;
    $b = 1;
　　　　 $v = 1;<br>
    for($i=3;$i<=$n;++$i){
        $v = $a+$b;
        $b = $a;
        $a = $v;
    }
    return $v;
}

递归实现无限极分类

<?php
$items = array(
=> array('id' => 1, 'pid' => 0, 'name' => '江西省'),
=> array('id' => 2, 'pid' => 0, 'name' => '黑龙江省'),
=> array('id' => 3, 'pid' => 1, 'name' => '南昌市'),
=> array('id' => 4, 'pid' => 2, 'name' => '哈尔滨市'),
=> array('id' => 5, 'pid' => 2, 'name' => '鸡西市'),
=> array('id' => 6, 'pid' => 4, 'name' => '香坊区'),
=> array('id' => 7, 'pid' => 4, 'name' => '南岗区'),
=> array('id' => 8, 'pid' => 6, 'name' => '和兴路'),
=> array('id' => 9, 'pid' => 7, 'name' => '西大直街'),
=> array('id' => 10, 'pid' => 8, 'name' => '东北林业大学'),
=> array('id' => 11, 'pid' => 9, 'name' => '哈尔滨工业大学'),
=> array('id' => 12, 'pid' => 8, 'name' => '哈尔滨师范大学'),
=> array('id' => 13, 'pid' => 1, 'name' => '赣州市'),
=> array('id' => 14, 'pid' => 13, 'name' => '赣县'),
=> array('id' => 15, 'pid' => 13, 'name' => '于都县'),
=> array('id' => 16, 'pid' => 14, 'name' => '茅店镇'),
=> array('id' => 17, 'pid' => 14, 'name' => '大田乡'),
=> array('id' => 18, 'pid' => 16, 'name' => '义源村'),
=> array('id' => 19, 'pid' => 16, 'name' => '上坝村'),
);?>

常见递归方法：

function getTree($data, $pId) {
  $html = '';
  foreach($data as $k => $v) {
    if ($v['pid'] == $pId) {        //父亲找到儿子
      $html .= "<li>".$v['name'];
      $html .= getTree($data, $v['id']);
      $html = $html."</li>";
    }
  }
  return $html ? '<ul>'.$html.'</ul>' : $html ;
}
print_r(getTree($items, 0));

运行结果图：