C#递归算法为何不总是返回值且有时陷入无限循环？

问题背景 #

假设有一个圆形二维房间，边界上分布着多种类型的连接器，需要判断是否能将这些连接器用线缆配对且无交叉。实现的递归逻辑为：以第一个连接器为基准，遍历剩余连接器，找到同类型的连接器后，递归检查分割后的子列表是否能完成无交叉配对。

现有递归代码 #

static bool IsPossible(List<string> connectors)              
{
    int index = 1;
    string firstConnector = connectors[0];
    bool possible = false;

    if (connectors.Count % 2 == 1)       // 确保元素数量为偶数，才能配对
    {
        return false;
    }

    while ((!possible) && (index <= connectors.Count - 1))
    {
        if (connectors[index] == firstConnector)
        {
            if ((index == 1) && (index == connectors.Count - 1))   // 相邻且是最后一个元素（仅两个元素的情况）
            {
                possible = true;
            }
            else if ((index == 1) && (index != connectors.Count - 1))      // 相邻但不是最后一个元素
            {
                possible = IsPossible(connectors.GetRange(2, connectors.Count - 2));
            }
            else if (index != connectors.Count - 1)      // 既不相邻也不是最后一个元素
            {
                List<string> leftSublist = connectors.GetRange(1, index - 1);
                List<string> rightSublist = connectors.GetRange(index + 1, connectors.Count - index - 1);

                possible = IsPossible(leftSublist) && IsPossible(rightSublist);
            }
            else if (index == connectors.Count - 1)        // 是最后一个元素但不相邻
            {
                possible = IsPossible(connectors.GetRange(1, index - 1));
            }
        }
                
        index += 2;   // 每次跳2步，试图保证子列表元素为偶数
    }

    return possible;
}

触发问题的测试用例 #

该测试用例是大量重复的SATA与USB-B对，所有SATA位于偶数索引位置：

List<string> example = new List<string> { "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B", "SATA", "USB - B" };

原因分析 #

1. 索引遍历逻辑完全错误
   代码中index += 2的设定，导致程序只能遍历奇数索引的元素，但测试用例中与第一个SATA同类型的连接器全部位于偶数索引（0、2、4...）位置。因此整个循环中，connectors[index] == firstConnector的判断永远不会触发，possible始终为false，循环会持续遍历所有奇数索引。

2. 超长列表导致的假“无限循环”
   测试用例包含近百个元素，循环需要遍历从1到Count-1的所有奇数索引，这个过程耗时极长，会让用户误以为程序陷入了无限循环，但实际上这是一个有限但效率极低的遍历过程，最终会返回false。

3. 递归逻辑的隐性缺陷
   即使代码能找到同类型元素（比如调整索引遍历逻辑后），分割出的左子列表可能为奇数长度（例如配对索引2时，左子列表仅包含1个USB-B），此时递归会直接返回false，程序仍会继续遍历后续索引，进一步拉长执行时间。

内容的提问来源于stack exchange，提问作者Terezie Kladivová