Java递归程序两Bug修复求助：无限循环与度数计算错误

问题1：直接连接时未正确输出0度分隔 #

原代码的getDegreeSeparation方法没有先检查当前用户是否直接连接目标用户，而是直接进入递归，导致直接连接场景返回-1而非0。修复时需在递归前先判断当前用户的连接列表是否包含目标用户，若是则直接返回0（符合题目“不计初始和目标用户”的度数定义）。

问题2：循环连接导致无限递归 #

按照教授提示，添加一个已访问用户集合来避免重复递归同一用户。每次递归前检查当前用户是否已被访问，若已访问则直接返回-1；否则将其加入集合后再遍历连接。同时要注意路径回溯——当某个连接的递归未找到路径时，需将该连接从路径列表中移除，避免错误累积路径节点。

额外逻辑问题修复 #

• 原process方法存在重复打印度数的问题，需合并为一次条件判断输出
• 提前判断登录用户与目标用户是否为同一人，避免无效计算
• showPath方法补充目标用户输出，确保路径完整

修改后的完整代码 #

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class DegreeOfSeparationAction implements MenuAction {

    @Override
    public boolean process(Scanner scanner, UserRepository userRepository, LinkedInUser loggedInUser) {
        System.out.println("Enter the username of the user you want to find the degree of separation with:");
        String enteredUsername = scanner.nextLine();
        LinkedInUser targetUser = userRepository.retrieve(enteredUsername);

        // 先判断是否为当前用户
        if (loggedInUser.equals(targetUser)) {
            System.out.println("The target user cannot be the logged in user.");
            return true;
        }

        List<LinkedInUser> path = new ArrayList<>();
        Set<LinkedInUser> visited = new HashSet<>();
        long degrees = getDegreeSeparation(loggedInUser, targetUser, path, visited);

        if (degrees == -1) {
            System.out.println("No connection path found between you and " + enteredUsername);
        } else {
            System.out.println("There are " + degrees + " degrees of separation between you and " + enteredUsername);
            showPath(loggedInUser, targetUser, path);
        }

        return true;
    }

    private long getDegreeSeparation(LinkedInUser currentUser, LinkedInUser targetUser, List<LinkedInUser> path, Set<LinkedInUser> visited) {
        // 避免重复访问同一用户，防止循环递归
        if (visited.contains(currentUser)) {
            return -1;
        }
        visited.add(currentUser);

        // 检查当前用户是否直接连接目标用户，是则返回0度
        if (currentUser.getConnections().contains(targetUser)) {
            path.add(targetUser);
            return 0;
        }

        for (LinkedInUser connection : currentUser.getConnections()) {
            path.add(connection);
            long subDegree = getDegreeSeparation(connection, targetUser, path, visited);
            if (subDegree != -1) {
                return subDegree + 1;
            }
            // 回溯：当前连接未找到路径，从路径中移除
            path.remove(path.size() - 1);
        }

        return -1;
    }

    private void showPath(LinkedInUser loggedInUser, LinkedInUser targetUser, List<LinkedInUser> path) {
        System.out.print(loggedInUser.getUsername());
        for (LinkedInUser user : path) {
            System.out.print(" -> " + user.getUsername());
        }
        System.out.println(); // 换行优化输出
    }
}

关键修改说明 #

1. 直接连接判断：在getDegreeSeparation开头添加目标用户检查，直接返回0，解决第一个Bug。
2. 已访问集合：新增Set<LinkedInUser> visited参数，递归前检查并标记已访问用户，彻底避免循环递归。
3. 路径回溯：在递归返回-1时，移除当前添加的连接节点，保证路径的准确性。
4. 逻辑优化：调整process方法的判断顺序，修复重复打印问题，增加无路径时的提示。

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