递归函数在循环中使用触发执行超时错误的原因排查

问题背景 #

我有一个存储用户推荐关系的数据库，结构如下：

| user_id | referrer_id |
| 3       | 2           |
| 4       | 3           |
| 5       | 3           |
| 6       | 4           |
| 7       | 4           |
| 8       | 5           |
| 9       | 5           |
| 10      | 6           |
| 11      | 10          |
| 12      | 10          |

我希望将指定用户的推荐网络（包括该用户、其直接推荐的用户以及间接推荐的用户）整理为数组，目前编写了如下递归函数代码：

// 获取直接下线的函数
function get_downlines($upline_id) {
    // 初始化UsersMatrix模型
    $um_model = model('UsersMatrix');
    $um_model->select('user_id')->where('upline_id', $upline_id);
    $downlines_check = $um_model->findAll(5);
    $downlines = [];
    if ( ! empty($downlines_check) ) {
        foreach($downlines_check as $check) {
            $downlines[] = $check->user_id;
        }
    }

    return $downlines;
}

// 目标用户
$user = 3;

// 初始化推荐网络数组
$network_array['user_network'][0] = [
    'id' => $user,
    'text' => "user-$user"
];

// 递归获取完整推荐网络
function get_network($referrer, $network_array){
    // 调用get_downlines获取当前用户的直接下线
    $downlines = get_downlines($referrer);
    if (count($downlines) > 0){
        // 遍历每个直接下线
        foreach($downlines as $downline){
            // 将下线添加到网络数组
            array_push($network_array['user_network'], [
                'id' => $downline,
                'text' => "user-$downline",
            ]);

            // 递归获取该下线的推荐网络
            get_network($downline, $network_array);
        }
    }

    // 返回更新后的网络数组
    return $network_array;
}

预期调用get_network(3, $network_array);时得到如下数组：

Array
(
    [user_network] => Array
        (
            [0] => Array
                (
                    [id] => 3
                    [text] => user-3
                ),
            [1] => Array
                (
                    [id] => 4
                    [text] => user-4
                ),
            [2] => Array
                (
                    [id] => 5
                    [text] => user-5
                ),
            [3] => Array
                (
                    [id] => 6
                    [text] => user-6
                ),
            [4] => Array
                (
                    [id] => 7
                    [text] => user-7
                ),
            [5] => Array
                (
                    [id] => 8
                    [text] => user-8
                ),
            [6] => Array
                (
                    [id] => 9
                    [text] => user-9
                ),
            [7] => Array
                (
                    [id] => 10
                    [text] => user-10
                )

        )

)

但实际页面触发了最大执行时间错误，仅无间接推荐的用户（如ID为10的用户）能正常运行，请问问题出在哪里？

问题原因分析 #

1. 数组传值方式错误：PHP中数组默认是值传递，每次调用get_network时都会复制一份$network_array。递归过程中，子函数对数组的修改不会同步到父函数，导致父函数无法感知已添加的用户，进而重复触发递归查询，最终陷入大量重复操作，耗尽执行时间。
2. 数据库查询次数过多：每一层递归都要发起一次数据库查询，推荐链越深，查询次数越多，进一步拖慢执行速度。

修复方案 #

方案1：使用引用传递数组 #

修改get_network函数的参数为引用传递，让所有递归调用操作同一个数组，避免重复复制和无效递归：

// 将数组参数改为引用传递
function get_network($referrer, &$network_array){
    $downlines = get_downlines($referrer);
    if (count($downlines) > 0){
        foreach($downlines as $downline){
            array_push($network_array['user_network'], [
                'id' => $downline,
                'text' => "user-$downline",
            ]);
            // 递归调用时依然传递引用
            get_network($downline, $network_array);
        }
    }
    // 引用传递直接修改原数组，无需返回
}

// 调用方式（不需要接收返回值）
get_network(3, $network_array);

方案2：批量查询减少数据库请求 #

先一次性拉取所有推荐关系到内存，再递归遍历，避免频繁的数据库查询：

// 先获取所有推荐关系数据
$um_model = model('UsersMatrix');
$all_referrals = $um_model->select('user_id, referrer_id')->findAll();
// 转换成映射数组：referrer_id => [user_id列表]
$referral_map = [];
foreach($all_referrals as $item) {
    $referral_map[$item->referrer_id][] = $item->user_id;
}

// 递归函数使用内存映射，避免重复查询
function get_network($referrer, &$network_array, $referral_map){
    if (isset($referral_map[$referrer])) {
        foreach($referral_map[$referrer] as $downline){
            array_push($network_array['user_network'], [
                'id' => $downline,
                'text' => "user-$downline",
            ]);
            get_network($downline, $network_array, $referral_map);
        }
    }
}

// 初始化数组
$user = 3;
$network_array['user_network'] = [
    [
        'id' => $user,
        'text' => "user-$user"
    ]
];

// 调用函数
get_network($user, $network_array, $referral_map);

额外优化：防止推荐环导致无限递归 #

如果数据库存在推荐环（如A推荐B，B又推荐A），会引发无限递归。可以添加已访问集合跳过已处理用户：

function get_network($referrer, &$network_array, $referral_map, &$visited){
    if (isset($visited[$referrer])) return;
    $visited[$referrer] = true;
    
    if (isset($referral_map[$referrer])) {
        foreach($referral_map[$referrer] as $downline){
            array_push($network_array['user_network'], [
                'id' => $downline,
                'text' => "user-$downline",
            ]);
            get_network($downline, $network_array, $referral_map, $visited);
        }
    }
}

// 调用时初始化已访问数组
$visited = [];
get_network($user, $network_array, $referral_map, $visited);

内容的提问来源于stack exchange，提问作者Samuel Asor