php 递归函数的三种实现方式-实现无限分类

无限分类的两种常用方式

    //递归获取某个分类的所有子分类1
    public function getSubs($categorys, $catId = 0, $level = 1) {
        $max = 5; //最大分类级数
        $subs = array();
        foreach ($categorys as $item) {
            if ($item['parent_id'] == $catId) {
                $item['level'] = $level;
                $subs[] = $item;
                if ($level < $max) {
                    $subs = array_merge($subs, $this->getSubs($categorys, $item['id'], $level + 1));
                }

            }

        }
        return $subs;
    }
    //递归获取某个分类的所有子分类2 ，每循环一条记录就把它放入该数组并unset该记录
    public function cateSort($data, $pid = 0, $count = 1) {
        static $arr = array(); //静态初始化
        $max = 5; //最大分类级数
        foreach ($data as $k => $v) {
            if ($v['parent_id'] == $pid) {
                $v['count'] = $count;
                $arr[] = $v;
                unset($data[$k]); //去掉不再使用的
                if ($count < $max) {
                    $this->cateSort($data, $v['id'], $count + 1);
                }
            }
        }
        return $arr;
    }

//获取某个分类的所有父分类 
//方法一，递归 
function getParents($categorys,$catId){ 
  $tree=array(); 
  foreach($categorys as $item){ 
    if($item['categoryId']==$catId){ 
      if($item['parentId']>0) 
        $tree=array_merge($tree,getParents($categorys,$item['parentId'])); 
      $tree[]=$item;  
      break;  
    } 
  } 
  return $tree; 
} 
  
//方法二,迭代 
function getParents2($categorys,$catId){ 
  $tree=array(); 
  while($catId != 0){ 
    foreach($categorys as $item){ 
      if($item['categoryId']==$catId){ 
        $tree[]=$item; 
        $catId=$item['parentId']; 
        break;  
      } 
    } 
  } 
  return $tree; 
}

递归函数是我们常用到的一类函数，最基本的特点是函数自身调用自身，但必须在调用自身前有条件判断，否则无限无限调用下去。实现递归函数可以采取什么方式呢？本文列出了三种基本方式。理解其原来需要一定的基础知识水品，包括对全局变量，引用，静态变量的理解，也需对他们的作用范围有所理解。递归函数也是解决无限级分类的一个很好地技巧。如果对无限级分类感兴趣，请参照php利用递归函数实现无限级分类。我习惯套用通俗的话解释复杂的道理，您确实不明白请参见手册。

　　利用引用做参数

先不管引用做不做参数，必须先明白引用到底是什么？引用不过是指两个不同名的变量指向同一块存储地址。本来每个变量有各自的存储地址，赋值删除各行其道。现在可好，两个变量共享一块存储地址。 a=&b; 。实际上指的是 a 不管不顾自己原来的存储地址，非要和b 共享一室了。因而任何对存储地址数值的改变都会影响两个值。

函数之间本来也是各行其是，即便是同名函数。递归函数是考虑将引用作为参数，成为一个桥梁，形成两个函数间的数据共享。虽然两个函数见貌似操作的是不同地址，但是实际上操作的是一块儿内存地址。

function test($a=0,&$result=array()){
$a++;
if ($a<10) {
    $result[]=$a;
    test($a,$result);
}
echo $a;
return $result;

}

上面的例子非常简答，以a<10作为判断条件，条件成立，则把a赋给result[];将result的引用传入函数，会将每一次递归产生的a添加到结果数组result。因而本例生成的$result数组是 Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 [8] => 9 ) 。

本例比较有意思的是echo a的值。相信很多人认为是12345678910吧，其实不然，是1098765432。为什么呢？因为函数还没执行echoa前就进行了下一次的函数递归。真正执行echo a是当a<10条件不满足的时候，echo a,返回result,对于上一层而言，执行完递归函数，开始执行本层的echo $a,依次类推。

利用全局变量

利用全局变量完成递归函数，请确保你确实理解什么是全局变量。global在函数内申明变量不过是外部变量的同名引用。变量的作用范围仍然在本函数范围内。改变这些变量的值，外部同名变量的值自然也改变了。但一旦用了&，同名变量不再是同名引用。利用全局变量实现递归函数没必要理解到这么深的一层，还保持原有对全局变量的看法就可以顺理成章理解递归函数。

　　利用全局变量

利用全局变量完成递归函数，请确保你确实理解什么是全局变量。global在函数内申明变量不过是外部变量的同名引用。变量的作用范围仍然在本函数范围内。改变这些变量的值，外部同名变量的值自然也改变了。但一旦用了&，同名变量不再是同名引用。利用全局变量实现递归函数没必要理解到这么深的一层，还保持原有对全局变量的看法就可以顺理成章理解递归函数。

function test($a=0,$result=array()){
 global $result; 
$a++; 
if ($a<10) { $result[]=$a;
        test($a,$result);
    } return $result;
}

利用静态变量

我们常常在类中见到static,今天我们把它利用到递归函数中。请记住static的作用：仅在第一次调用函数的时候对变量进行初始化，并且保留变量值。

举个栗子：

function test(){ 
static $count=0; 
echo $count; 
$count++;
}
test();
test();
test();
test();
test();

请问这一段代码的执行结果是多少？是00000么？必然不是。是01234。首先第一次调用test(),static对 count 进行初始化，其后每一次执行完都会保留count 的值,不再进行初始化，相当于直接忽略了 static$count=0; 这一句。

因而将static应用到递归函数作用可想而知。在将需要作为递归函数间作为“桥梁"的变量利用static进行初始化，每一次递归都会保留"桥梁变量"的值。

function test($a=0){ static $result=array(); $a++; if ($a<10) { $result[]=$a;
        test($a);
    } return $result;
}

总结

所谓递归函数，重点是如何处理函数调用自身是如何保证所需要的结果得以在函数间合理"传递"，当然也有不需要函数之间传值得递归函数，例如：

function test($a=0){ $a++; if ($a<10) { echo $a;
        test($a);
    }
}</pre>

面对这样的函数，我们就不必大伤脑筋了。顺便说一句，深入理解变量引用相关知识对解决这类问题大有裨益。

我们再来看一个实例--无限菜单分类：

首先建立分类信息表：

CREATE TABLE IF NOT EXISTS `category` ( 
 `categoryId` smallint(5) unsigned NOT NULL AUTO_INCREMENT, 
 `parentId` smallint(5) unsigned NOT NULL DEFAULT '0', 
 `categoryName` varchar(50) NOT NULL, 
 PRIMARY KEY (`categoryId`) 
) ;

插入数据

INSERT INTO `category` (`categoryId`, `parentId`, `categoryName`) VALUES
(1, 0, 'php'), 
(2, 0, 'java'), 
(3, 0, 'c/c++'), 
(4, 1, 'php基础'), 
(5, 1, 'php开源资料'), 
(6, 1, 'php框架'), 
(7, 2, 'java Se'), 
(8, 2, 'java EE'), 
(9, 2, 'java Me'), 
(10, 3, 'c/c++基础编程'), 
(11, 3, 'c/c++系统开发'), 
(12, 3, 'c嵌入式编程'), 
(13, 3, 'c++应用开发'), 
(14, 13, 'c++桌面应用开发'), 
(15, 13, 'c++游戏开发');

下面是php代码

<?php 
/* 
php无限极分类 
*/
  
//获取某分类的直接子分类 
function getSons($categorys,$catId=0){ 
  $sons=array(); 
  foreach($categorys as $item){ 
    if($item['parentId']==$catId) 
      $sons[]=$item; 
  } 
  return $sons; 
} 
  
//获取某个分类的所有子分类 
function getSubs($categorys,$catId=0,$level=1){ 
  $subs=array(); 
  foreach($categorys as $item){ 
    if($item['parentId']==$catId){ 
      $item['level']=$level; 
      $subs[]=$item; 
      $subs=array_merge($subs,getSubs($categorys,$item['categoryId'],$level+1)); 
        
    } 
        
  } 
  return $subs; 
} 
  
//获取某个分类的所有父分类 
//方法一，递归 
function getParents($categorys,$catId){ 
  $tree=array(); 
  foreach($categorys as $item){ 
    if($item['categoryId']==$catId){ 
      if($item['parentId']>0) 
        $tree=array_merge($tree,getParents($categorys,$item['parentId'])); 
      $tree[]=$item;  
      break;  
    } 
  } 
  return $tree; 
} 
  
//方法二,迭代 
function getParents2($categorys,$catId){ 
  $tree=array(); 
  while($catId != 0){ 
    foreach($categorys as $item){ 
      if($item['categoryId']==$catId){ 
        $tree[]=$item; 
        $catId=$item['parentId']; 
        break;  
      } 
    } 
  } 
  return $tree; 
} 
 
//测试 部分 
$pdo=new PDO('mysql:host=localhost;dbname=test','root','8888'); 
$stmt=$pdo->query("select * from category order by categoryId"); 
$categorys=$stmt->fetchAll(PDO::FETCH_ASSOC); 
  
$result=getSons($categorys,1); 
foreach($result as $item) 
  echo $item['categoryName'].'<br>'; 
echo '<hr>'; 
  
$result=getSubs($categorys,0); 
foreach($result as $item) 
  echo str_repeat(' ',$item['level']).$item['categoryName'].'<br>'; 
echo '<hr>'; 
  
$result=getParents($categorys,7); 
foreach($result as $item) 
  echo $item['categoryName'].' >> '; 
echo '<hr>'; 
  
$result=getParents2($categorys,15); 
foreach($result as $item) 
  echo $item['categoryName'].' >> '; 
?>
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 210,978评论 6赞 490
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 89,954评论 2赞 384
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 156,623评论 0赞 345
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,324评论 1赞 282
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,390评论 5赞 384
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,741评论 1赞 289
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,892评论 3赞 405
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,655评论 0赞 266
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,104评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,451评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,569评论 1赞 340
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,254评论 4赞 328
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,834评论 3赞 312
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,725评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,950评论 1赞 264
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,260评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,446评论 2赞 348