CS50 Tideman作业lock_pairs函数逻辑缺陷排查求助

Let's break down your problem step by step, starting with the core bug in your cycle detection logic, then moving to the recursion vs iteration question.

The Critical Bug in lock_pairs & iscycle #

Looking at your code, the biggest issue is how you're calling iscycle in lock_pairs:

if (iscycle(i, visited)) {

Here, i is the index of the current pair in the pairs array—not the index of a candidate. But your iscycle function expects a candidate index (since it uses locked[index][i], which references the candidate adjacency matrix). That's why your cycle check is completely off, leading to the failed Check50 test.

Additionally, your iscycle function is checking for any cycle starting at a candidate, but what we actually need for Tideman is to check if adding the current winner -> loser edge creates a cycle specifically between the loser and winner. In other words: if there's already a path from the loser back to the winner, adding this edge will form a cycle, so we shouldn't lock it.

Fixed Code for Cycle Detection & lock_pairs #

First, let's rewrite the cycle-checking function to verify if a path exists from a start candidate to a target candidate:

// Check if there's a path from start to target in the locked graph
bool has_path(int start, int target, bool visited[]) {
    // Base case: we've reached the target
    if (start == target) {
        return true;
    }
    // If we've already visited this node, no new path here
    if (visited[start]) {
        return false;
    }
    visited[start] = true;
    // Explore all outgoing edges from start
    for (int i = 0; i < candidate_count; i++) {
        if (locked[start][i] && has_path(i, target, visited)) {
            return true;
        }
    }
    // No path found from start to target
    return false;
}

Now fix the lock_pairs function to use this correctly:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void) {
    for (int i = 0; i < pair_count; i++) {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;
        // Temporarily lock the pair
        locked[winner][loser] = true;
        
        // Initialize visited array to track traversal
        bool visited[candidate_count];
        for (int j = 0; j < candidate_count; j++) {
            visited[j] = false;
        }
        
        // Check if adding this edge creates a cycle (path from loser to winner)
        if (has_path(loser, winner, visited)) {
            // Undo the lock if a cycle is created
            locked[winner][loser] = false;
        }
    }
    return;
}

This change ensures we're checking the right thing: after adding the edge, can the loser eventually beat the winner via other locked edges? If yes, we skip locking this pair to avoid cycles.

Recursion vs Iteration: Efficiency & Use Cases #

Let's break down when to use each approach:

Efficiency #

• Recursion: Has overhead from function calls (stack frame setup/teardown, context saving). For problems with very deep recursion (e.g., traversing a million-node linked list recursively), this can lead to a stack overflow. In small to moderately deep cases, the overhead is negligible, but it's less efficient than iteration for large-scale tasks.
• Iteration: No function call overhead—you control the stack/queue manually using loops. It's more memory-efficient for deep traversals, as you avoid filling the program's call stack. Iteration is generally faster for performance-critical code.

Code Design & Use Cases #

• Use Recursion When:

  • The problem naturally breaks into smaller, identical subproblems (e.g., divide-and-conquer algorithms like merge sort, tree traversals). Recursion makes the code concise and easier to read/maintain.
  • You're working with structures that have a recursive nature (e.g., trees, nested data).
  • Recursion depth is limited (e.g., a balanced tree with depth < 1000—well within the default call stack limit).

• Use Iteration When:

  • Recursion depth could be very large (e.g., long linked lists, deep unbalanced trees) to avoid stack overflow.
  • You need maximum performance (e.g., high-throughput data processing).
  • The recursive solution is hard to debug or leads to excessive overhead.

In your original iscycle function, recursion is a perfectly reasonable choice—cycle detection via DFS is intuitive with recursion. An iterative DFS would work too, but recursion makes the code shorter and easier to follow for this use case.

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