如何将邻接矩阵环检测的迭代函数转为C语言递归函数？

我目前难以理解递归思维，在Stack Overflow上查的内容大多看不太懂。现在我需要基于二维数组邻接矩阵检测有向图中的环，graph[i][j]为true表示存在从i到j的边。我写了check_cycles函数用来检测从j到i的路径，但现在是硬编码了图的大小，而且多层for循环在图大小变化时完全不实用。现有代码能正确返回true，但我想知道怎么改成递归方案？递归函数的终止条件是什么？我用的是支持bool返回值的CS50库，也可以改成返回void。

现有硬编码代码 #

#include <stdio.h>
#include <cs50.h>
//hard coding the size of the graph
int size = 5;
//set up an adjecency matrix
bool graph[5][5];
//functions
bool check_cycles(int index1, int index2);
int main(void) {
    //setting the graph values to false
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            graph[i][j] = false;
        }
    }
    //hard coding a cycle into the graph
    graph[0][1] = true;
    graph[1][2] = true;
    graph[2][3] = true;
    graph[3][0] = true;
    //check for cycles
    printf(check_cycles(2,3)? "Cycle detected\n" : "No cycles\n");
}
bool check_cycles(int index1, int index2) {
    for (int i = 0; i < size; i++) {
        //check for adjacent edge
        if (graph[index2][i] == true) {
            //check if edge points to initial node
            if (graph[i][index1] == true) {
                return true;
            } else {
                for (int j = 0; j < size; j++) {
                    if (graph[i][j] == true) {
                        if (graph[j][index1] == true) {
                            return true;
                        } else {
                            for (int k = 0; k < size; k++) {
                                if (graph[j][k] == true) {
                                    if (graph[k][index1] == true) {
                                        return true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return false;
}

递归实现的核心思路 #

你的硬编码循环本质是在做深度优先搜索（DFS）：从index2出发，一层一层找能到index1的路径。递归就是把这种“重复遍历邻接节点、检查是否到达目标”的逻辑封装起来，不用手动写多层循环。

递归函数的关键要素 #

1. 参数：需要三个核心参数

   • current：当前正在遍历的节点
   • target：我们要到达的目标节点（也就是你的index1）
   • visited：一个布尔数组，记录已经访问过的节点——这是为了避免在环里无限递归（比如你的测试图里3→0→1→2→3，如果不标记访问，递归会一直绕圈）

2. 终止条件：

   • 终止条件1：current == target——说明我们找到了从起点到目标的路径，直接返回true
   • 终止条件2：当前节点的所有邻接节点都已经遍历过，且没有找到目标——返回false

3. 递归逻辑：

   • 标记当前节点为已访问（防止重复遍历）
   • 遍历当前节点的所有邻接节点（即graph[current][i] == true的i）
   • 对每个未访问的邻接节点，递归调用检测函数：如果这个邻接节点能到达目标，就返回true
   • 遍历完所有邻接节点都没找到路径，返回false

完整递归代码实现 #

我们可以把原来的check_cycles拆成两个函数：一个对外的入口函数（负责初始化访问数组），一个内部的递归DFS函数。这样调用方式和你原来的代码保持一致：

#include <stdio.h>
#include <cs50.h>

int size = 5;
bool graph[5][5];

// 内部递归DFS函数：检测从current到target是否有路径
bool dfs(int current, int target, bool visited[]) {
    // 终止条件1：找到目标节点
    if (current == target) {
        return true;
    }

    // 标记当前节点为已访问，避免重复遍历
    visited[current] = true;

    // 遍历当前节点的所有邻接节点
    for (int i = 0; i < size; i++) {
        if (graph[current][i] == true && !visited[i]) {
            // 递归检查邻接节点能否到达目标
            if (dfs(i, target, visited)) {
                return true;
            }
        }
    }

    // 回溯：取消当前节点的访问标记（适配多路径检测场景，非必须但为标准写法）
    visited[current] = false;
    return false;
}

// 对外入口函数：初始化访问数组，调用DFS
bool check_cycles(int index1, int index2) {
    // 初始化访问数组，所有节点都未访问
    bool visited[size];
    for (int i = 0; i < size; i++) {
        visited[i] = false;
    }

    // 从index2出发，检测能否到达index1
    return dfs(index2, index1, visited);
}

int main(void) {
    // 初始化图为全false
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            graph[i][j] = false;
        }
    }

    // 构建带环的图
    graph[0][1] = true;
    graph[1][2] = true;
    graph[2][3] = true;
    graph[3][0] = true;

    // 检测：从3出发能否到2？能，因为3→0→1→2，所以存在环
    printf(check_cycles(2, 3) ? "Cycle detected\n" : "No cycles\n");
    return 0;
}

代码解释 #

• 访问数组visited：这是递归里很重要的一点，没有它的话，遇到环的时候递归会无限调用（比如3→0→1→2→3→0...），导致栈溢出。标记已访问的节点后，我们就不会重复处理同一个节点。
• 回溯取消标记：在DFS结束后把visited[current]设回false，这是为了如果有其他路径可以到达当前节点时，还能继续检测（不过在你的场景里，只要找到一条路径就返回，所以这个回溯不是必须，但这是DFS的标准写法，能适应更复杂的场景）。
• 灵活性：现在不管图的size改成多少，递归代码都能自动适应，不用手动加多层for循环了。

补充：如果要检测整个图是否存在环 #

你的当前代码是检测从index2到index1是否有路径（从而判断index1→index2这条边加上路径是否形成环）。如果要检测整个图有没有环，只需要对每个节点做DFS，检查是否存在从该节点出发能回到自己的路径即可，逻辑类似。

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