递归出现死循环，怎么解决

Question

数组：
Array ( [0] => Array ( [id] => 1 [fid] => 12227 ) [1] => Array ( [id] => 4 [fid] => 1 ) [2] => Array ( [id] => 18 [fid] => 1 ) [3] => Array ( [id] => 21 [fid] => 18 ) [4] => Array ( [id] => 22 [fid] => 1 ) [5] => Array ( [id] => 23 [fid] => 135 ) [6] => Array ( [id] => 24 [fid] => 18 ) [7] => Array ( [id] => 29 [fid] => 22 ) [8] => Array ( [id] => 30 [fid] => 22 ) [9] => Array ( [id] => 31 [fid] => 22 ) [10] => Array ( [id] => 32 [fid] => 22 ) [11] => Array ( [id] => 33 [fid] => 32767 ) [12] => Array ( [id] => 34 [fid] => 22 ) [13] => Array ( [id] => 35 [fid] => 135 ) [14] => Array ( [id] => 36 [fid] => 22 ) [15] => Array ( [id] => 135 [fid] => 22 ) [16] => Array ( [id] => 138 [fid] => 32 ) [17] => Array ( [id] => 139 [fid] => 135 ) [18] => Array ( [id] => 140 [fid] => 32 ) [19] => Array ( [id] => 273 [fid] => 22 ) [20] => Array ( [id] => 274 [fid] => 135 ) [21] => Array ( [id] => 275 [fid] => 22 ) [22] => Array ( [id] => 276 [fid] => 32767 ) [23] => Array ( [id] => 277 [fid] => 273 ) [24] => Array ( [id] => 443 [fid] => 18 ) [25] => Array ( [id] => 621 [fid] => 18 ) [26] => Array ( [id] => 665 [fid] => 848 ) [27] => Array ( [id] => 760 [fid] => 22 ) [28] => Array ( [id] => 762 [fid] => 1 ) [29] => Array ( [id] => 846 [fid] => 29 ) [30] => Array ( [id] => 848 [fid] => 22 ) [31] => Array ( [id] => 1217 [fid] => 1 ) [32] => Array ( [id] => 3190 [fid] => 1 ) [33] => Array ( [id] => 3208 [fid] => 22 ) [34] => Array ( [id] => 3238 [fid] => 1 ) [35] => Array ( [id] => 3241 [fid] => 3238 ) [36] => Array ( [id] => 3242 [fid] => 3232 ) [37] => Array ( [id] => 3244 [fid] => 3238 ) [38] => Array ( [id] => 3245 [fid] => 30 ) [39] => Array ( [id] => 3258 [fid] => 36 ) [40] => Array ( [id] => 3259 [fid] => 18 ) [41] => Array ( [id] => 3276 [fid] => 1 ) [42] => Array ( [id] => 3625 [fid] => 22 ) [43] => Array ( [id] => 3683 [fid] => 18 ) [44] => Array ( [id] => 3723 [fid] => 1 ) [45] => Array ( [id] => 4550 [fid] => 12227 ) [46] => Array ( [id] => 4559 [fid] => 1 ) [47] => Array ( [id] => 4685 [fid] => 12174 ) [48] => Array ( [id] => 4781 [fid] => 22 ) [49] => Array ( [id] => 4782 [fid] => 135 ) [50] => Array ( [id] => 4811 [fid] => 135 ) [51] => Array ( [id] => 4852 [fid] => 762 ) [52] => Array ( [id] => 4973 [fid] => 22 ) [53] => Array ( [id] => 5204 [fid] => 22 ) [54] => Array ( [id] => 5528 [fid] => 21 ) [55] => Array ( [id] => 5613 [fid] => 762 ) [56] => Array ( [id] => 5729 [fid] => 135 ) [57] => Array ( [id] => 11095 [fid] => 3208 ) [58] => Array ( [id] => 11335 [fid] => 22 ) [59] => Array ( [id] => 12174 [fid] => 1 ) [60] => Array ( [id] => 12227 [fid] => 1 ) [61] => Array ( [id] => 12264 [fid] => 12174 ) [62] => Array ( [id] => 12265 [fid] => 12174 ) [63] => Array ( [id] => 12266 [fid] => 22 ) [64] => Array ( [id] => 12267 [fid] => 22 ) [65] => Array ( [id] => 12268 [fid] => 1 ) [66] => Array ( [id] => 12269 [fid] => 1 ) [67] => Array ( [id] => 12270 [fid] => 1 ) [68] => Array ( [id] => 12271 [fid] => 1 ) ) 
=================================================================
递归函数：
function child($id, $ar)
{
global $pathint;
foreach($ar as $k => $v)
{
if ($v['fid'] == $id)
{
$pathint .= ','.$v['id'];
child($v['id'], $ar);
}
}
return $pathint;
}
=======================================
数组是从数据库查询生成的，一调用递归就成了死循环，检查了很久都没有找到原因，

Answer 1

楼主你的代码死循环一点都不奇怪，因为在if的时候判断$v['fid'] == $id如果成立那么又将原来的东西传回去了就相当于第一次执行一个效果，楼主明白了吗，打个比方：路人甲向前走路撞到墙上了，如果路人甲继续向前走那么他和上次一样会撞到墙(一直装下去)，只有你换个方向才会避免撞墙，楼主明白了吗？

Answer 2

看看你的数据，当id等于1时，其中一条执行child(12227, $ar);
当id等于12227时，其中一条执行child(1, $ar);
这本身就是一个死循环！

Answer 3

初始传上值是1
传入的数据
Array ( [id] => 1 [fid] => 12227 ) 
Array ( [id] => 12227 [fid] => 1 )
就是这里出现了死循环，如何在递归里判断死循环并跳出

Answer 4

你的数据有问题！如
    [0] => Array
        (
            [id] => 1
            [fid] => 12227
        )
    [60] => Array
        (
            [id] => 12227
            [fid] => 1
        )
这两组数据冲突了

Answer 5

这个问题是不需要递归的，你是从下往上找。给你个函数
function find_parent($ar, $id='id', $pid='pid') { 
  foreach($ar as $v) $t[$v[$id]] = $v;
  foreach ($t as $k => $item){
    if( $item[$pid] ){
      if( ! isset($t[$item[$pid]]['parent'][$item[$pid]]) )
         $t[$item[$id]]['parent'][$item[$pid]] =& $t[$item[$pid]];
    }
  } 
  return $t;
}
对你这个题目的用法：$p = find_parent($ar, 'id', 'fid');
获取 id 为 1 的路径
print_r($p[1]);
得
Array
(
    [id] => 1
    [fid] => 12227
    [parent] => Array
        (
            [12227] => Array
                (
                    [id] => 12227
                    [fid] => 1
                    [parent] => Array
                        (
                            [1] => Array
                                (
                                    [id] => 1
                                    [fid] => 12227
                                    [parent] => Array
 *RECURSION*                                )                        )                )        ))
这就表示有冲突了

Answer 6

设置最多深入的层次。超过就退出。不然出现stack overflow。

Answer 7

if ($v['fid'] == $id)有问题吧？