递归步进算法调试求助：PowerShell循环路径查找问题

问题背景与需求 #

现有一份包含Item1/Item2/Item3及对应成本的数据表，需实现以下功能：

• 对每一行数据，以其Item1为起点，匹配全表中Item2等于该Item1的行
• 以匹配到的行的Item1继续重复匹配，直到找到能循环回起点的路径（如Row1 > Row5 > Row3 > Row1）
• 路径跳数需受限制（如最多5跳）
• 后续需扩展支持Item1与Item3的匹配，并按路径总成本排序

测试数据生成代码：

$max = 10
$testdata = for($i=1; $i -le $max; $i++) {
    $item1 = "item{0:D2}" -f (Get-Random -Minimum 1 -Maximum $max)
    $item2 = do { "item{0:D2}" -f (Get-Random -Minimum 1 -Maximum $max) } until ($_ -ne $item1)
    $item3 = do { "item{0:D2}" -f (Get-Random -Minimum 1 -Maximum $max) } until ($_ -ne $item1 -and $_ -ne $item2) # 修正原逻辑错误：原or应改为and

    [PSCustomObject]@{
        Row   = "Row{0:D2}" -f $i
        Item1 = $item1
        Cost1 = Get-Random -Minimum 20 -Maximum 800
        Item2 = $item2
        Cost2 = Get-Random -Minimum 80 -Maximum 400
        Item3 = $item3
        Cost3 = Get-Random -Minimum 60 -Maximum 600
    }
}

原实现的问题 #

原递归函数Get-LoopingPath存在以下核心问题：

• 未传递当前路径状态，MatchList仅在当前作用域赋值，递归调用时无法累积有效路径
• 未检查是否回到起点，无法识别符合要求的循环路径
• 跳数限制逻辑失效，未在达到限制时终止无效遍历
• 未过滤路径中的重复节点，易陷入死循环
• 返回结果混乱，出现不符合匹配规则、超出跳数的内容

优化后的递归函数 #

优化后的函数会跟踪当前路径、起点节点，严格检查循环条件，并限制跳数，同时预留扩展接口：

function Get-LoopingPath {
    Param(
        [Parameter(Mandatory)]$CurrentNode,
        [Parameter(Mandatory)]$StartNode,
        [Parameter(Mandatory)][array]$CurrentPath,
        [int]$MaxHops = 5,
        [string]$MatchColumn = "Item2" # 支持后续切换Item3匹配
    )

    # 跳数超限，终止递归
    if ($CurrentPath.Count -ge $MaxHops) {
        return $null
    }

    # 检查是否回到起点，且路径长度至少为2（避免直接自循环）
    if ($CurrentNode.Item1 -eq $StartNode.Item2 -and $CurrentPath.Count -ge 1) {
        return $CurrentPath + $CurrentNode
    }

    # 避免路径中出现重复节点，防止死循环
    if ($CurrentPath.Row -contains $CurrentNode.Row) {
        return $null
    }

    # 获取下一批匹配节点：指定列（如Item2）等于当前节点的Item1
    $nextNodes = $script:testdata | Where-Object { $_.$MatchColumn -eq $CurrentNode.Item1 }

    $validPaths = @()
    foreach ($nextNode in $nextNodes) {
        $newPath = $CurrentPath + $CurrentNode
        $result = Get-LoopingPath -CurrentNode $nextNode -StartNode $StartNode -CurrentPath $newPath -MaxHops $MaxHops -MatchColumn $MatchColumn
        if ($result) {
            $validPaths += ,$result # 保留数组结构，避免扁平化
        }
    }

    return $validPaths
}

调用示例 #

调用优化后的函数，获取符合要求的循环路径：

for ($i=0; $i -lt 4; $i++) {
    $startNode = $testdata[$i]
    $paths = Get-LoopingPath -CurrentNode $startNode -StartNode $startNode -CurrentPath @() -MaxHops 5

    if ($paths.Count -gt 0) {
        # 格式化输出完整循环路径（追加起点）
        foreach ($path in $paths) {
            $fullPath = ($path.Row + $startNode.Row) -join " > "
            Write-Host ("[{0}] 有效循环路径: {1}" -f $i, $fullPath)
        }
    } else {
        Write-Host ("[{0}] 未找到符合要求的循环路径" -f $i)
    }
}

后续扩展建议 #

• 支持Item3匹配：调用时指定-MatchColumn "Item3"即可切换匹配规则
• 成本计算与排序：在路径返回后，累加每一步对应成本（如Item2匹配用Cost2，Item3匹配用Cost3），再按总成本排序
• 非递归实现：若递归深度过大，可改用队列实现广度优先搜索（BFS），更易调试且避免栈溢出
• 去重处理：对找到的循环路径去重（如Row1>Row5>Row3>Row1与Row5>Row3>Row1>Row5视为同一循环）

内容的提问来源于stack exchange，提问作者Joe S