호출 흐름을 어떻게 따라가나? - 재귀와 백트래킹

처음 배운 사람의 정리

---

3줄 요약

• 호출 흐름을 저장하려면 트리 구조가 필요하다
• 트리를 만들 때는 재귀 함수가 자연스럽다
• 순환 참조 방지의 핵심: add()만 하면 버그, remove()도 해야 정상

---

1. 들어가며: 레거시 코드 분석, 이런 경험 있지 않나요?

"이 API가 어떤 Service를 호출하고, 그 Service가 어떤 DAO를 호출하는지..."
IDE에서 Ctrl+클릭으로 하나씩 따라가다 보면 어느새 10개 파일을 열어놓고 있다.

신규 프로젝트 투입 첫날, 선임이 "이 API 분석해봐"라고 하면 시작되는 노가다.
파일 하나 열고, 호출되는 메서드 찾고, 또 그 파일 열고...

이걸 자동화하고 싶었다.

이전 글에서 JavaParser로 메서드 호출을 찾는 방법을 정리했다.

// JavaParser로 찾은 메서드 호출
userService.selectUserList();

여기까지는 됐다.

근데 이제 뭘 해야 하지?

userService.selectUserList() 안에서 또 뭔가를 호출하고, 그 안에서 또 호출하고...

이 전체 흐름을 어떻게 저장하고 표현할까?

---

2. 문제: 호출 흐름을 어떻게 저장하지?

실제 코드 예시

우리 프로젝트의 샘플 코드를 보자.

UserController.java

@GetMapping("/detail.do")
public String selectUser(@RequestParam("userId") String userId, ModelMap model) {
    UserVO user = userService.selectUser(userId);

    if (user != null) {
        String deptName = userService.selectDeptName(user.getDeptId());
        user.setDeptName(deptName);
    }

    model.addAttribute("user", user);
    return "user/userDetail";
}

이 하나의 Controller 메서드에서:

1. userService.selectUser() 호출
2. userService.selectDeptName() 호출

그리고 각각의 Service 메서드 안에서 또 DAO를 호출한다.

UserServiceImpl.java

public UserVO selectUser(String userId) {
    return userDAO.selectUser(userId);  // DAO 호출
}

public String selectDeptName(String deptId) {
    DeptVO dept = deptDAO.selectDept(deptId);  // 다른 DAO 호출
    return dept != null ? dept.getDeptName() : "";
}

전체 흐름을 그려보면

UserController.selectUser()
│
├── userService.selectUser()
│   └── userDAO.selectUser()
│
└── userService.selectDeptName()
    └── deptDAO.selectDept()

이런 구조다.

• 하나의 메서드가 여러 개를 호출할 수 있다 (selectUser, selectDeptName)
• 호출이 깊어진다 (Controller → Service → DAO)

이걸 어떻게 저장하지?

---

3. 해결: 트리 구조

왜 트리인가? - 다른 선택지는 없었을까?

처음에는 단순하게 생각했다. 리스트로 순서대로 저장하면 안 될까?

// 시도 1: 단순 리스트
List<String> flow = Arrays.asList(
    "Controller.selectUser",
    "Service.selectUser",
    "DAO.selectUser",
    "Service.selectDeptName",
    "DAO.selectDept"
);

문제는 이 방식으로는 "누가 누구를 호출했는지" 관계를 알 수 없다.
Service.selectDeptName()이 Controller에서 호출된 건지, 다른 Service에서 호출된 건지 구분이 안 된다.

Map은 어떨까?

// 시도 2: Map
Map<String, List<String>> calls = {
    "Controller.selectUser" → ["Service.selectUser", "Service.selectDeptName"],
    "Service.selectUser" → ["DAO.selectUser"]
};

가능은 한데... 깊이가 깊어지면 따라가기 복잡하다.
"Controller에서 시작해서 DAO까지"를 한눈에 보기 어렵다.

다시 그림을 보자.

        [Controller]
             │
        selectUser()
        ┌────┴────┐
   [Service]    [Service]
  selectUser   selectDeptName
       │            │
    [DAO]         [DAO]
  selectUser    selectDept

이건 트리(Tree) 구조다!

자료구조	호출 관계 표현	깊이 표현	한눈에 보기	선택
리스트	❌	❌	❌	-
맵	△	△	❌	-
그래프	✅	✅	△	오버스펙
트리	✅	✅	✅	✅

결론: 호출 관계는 부모-자식 관계이므로 트리가 가장 자연스럽다.

트리의 특징

• 부모-자식 관계: Controller가 Service를 호출하면, Service는 Controller의 "자식"
• 1:N 관계: 하나의 부모가 여러 자식을 가질 수 있음
• 깊이(Depth): 얼마나 깊이 들어갔는지 표현

FlowNode 클래스

프로그래밍에서 트리는 "각 노드가 자식 노드들의 목록을 가진다"로 표현한다.
그래서 FlowNode라는 클래스를 만들었다.

public class FlowNode {
    private String className;      // 예: "UserController"
    private String methodName;     // 예: "selectUser"
    private ClassType classType;   // 예: CONTROLLER, SERVICE, DAO

    // 핵심: 자식 노드들의 목록
    private List<FlowNode> children = new ArrayList<>();

    // 자식 추가
    public void addChild(FlowNode child) {
        children.add(child);
    }
}

핵심 포인트:

• children: 이 메서드가 호출하는 다른 메서드들
• addChild(): 호출 관계를 연결

예를 들어:

FlowNode controller = new FlowNode("UserController", "selectUser", ClassType.CONTROLLER);
FlowNode service1 = new FlowNode("UserServiceImpl", "selectUser", ClassType.SERVICE);
FlowNode service2 = new FlowNode("UserServiceImpl", "selectDeptName", ClassType.SERVICE);

controller.addChild(service1);  // selectUser가 service1을 호출
controller.addChild(service2);  // selectUser가 service2도 호출

ClassType은 해당 클래스가 Controller인지, Service인지, DAO인지를 나타내는 enum이다.

---

4. 트리 만들기: 재귀적 탐색

재귀란?

*함수가 자기 자신을 호출하는 것
*

처음 들으면 어렵다. 비유로 설명해보자.

비유: 족보 조사

할아버지의 족보를 조사한다고 해보자.

1. 할아버지 정보 기록
2. 할아버지의 자녀들 확인
3. 각 자녀에 대해서도 똑같이 조사 (→ 1번으로 돌아감!)
4. 그 자녀의 자녀에 대해서도...

"정보 기록 → 자녀 확인 → 자녀도 똑같이 조사"

이 패턴이 재귀다.

코드로 표현하면

void 족보조사(사람 person) {
    System.out.println(person.이름);  // 1. 정보 기록

    for (사람 child : person.자녀들) {  // 2. 자녀들 확인
        족보조사(child);  // 3. 자녀도 똑같이 조사! (자기 자신 호출)
    }
}

족보조사() 함수 안에서 족보조사()를 다시 호출한다.

왜 재귀인가? - 반복문으로도 가능하지 않나?

맞다. 반복문(while + Stack)으로도 구현할 수 있다.

// 반복문 방식 (Stack 사용)
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    Node current = stack.pop();
    // 현재 노드 처리...
    for (Node child : current.getChildren()) {
        stack.push(child);
    }
}

// 재귀 방식
void traverse(Node current) {
    // 현재 노드 처리...
    for (Node child : current.getChildren()) {
        traverse(child);  // 자연스럽게 깊이 우선 탐색
    }
}

기준	반복문 + Stack	재귀
코드 직관성	복잡	간결
스택 관리	직접 해야 함	자동 (콜스택)
깊은 트리	안전	StackOverflow 가능성
상태 복원	직접 관리	자연스러움

이 프로젝트에서 재귀를 선택한 이유:

1. 호출 깊이가 보통 5단계 이내 (Controller → Service → DAO)
2. 코드가 "현재 처리 → 자식도 똑같이" 패턴과 일치
3. 백트래킹(visited 관리)이 재귀에서 더 자연스러움

호출 흐름 추적도 똑같다

이 개념을 의사 코드(pseudocode)로 표현해보자:

함수 흐름추적(클래스, 메서드):
    1. 현재 노드 생성 (클래스명, 메서드명, 클래스타입)

    2. 이 메서드가 호출하는 것들 확인
       각 호출에 대해:
           자식 = 흐름추적(호출대상 클래스, 호출대상 메서드)  ← 자기 자신 호출!
           현재노드.자식추가(자식)

    3. 현재 노드 반환

족보 조사와 똑같은 패턴이다:

• "현재 정보 기록 → 자식들 확인 → 자식도 똑같이 처리"

---

5. 실제 코드: buildFlowTree

위의 개념을 실제 코드로 구현한 것이 buildFlowTree()다.

private FlowNode buildFlowTree(ParsedClass clazz, ParsedMethod method, int depth) {
    // 1. 현재 노드 생성
    FlowNode node = new FlowNode(
        clazz.getClassName(),    // "UserController"
        method.getMethodName(),  // "selectUser"
        clazz.getClassType()     // CONTROLLER
    );
    node.setDepth(depth);  // 몇 번째 깊이인지 (0, 1, 2...)

    // 2. 이 메서드 안의 호출들을 찾는다
    for (MethodCall call : method.getMethodCalls()) {

        // 3. 각 호출을 추적해서 자식 노드 생성
        FlowNode childNode = traceMethodCall(call, depth + 1);

        if (childNode != null) {
            node.addChild(childNode);  // 트리에 연결
        }
    }

    return node;
}

traceMethodCall은 뭘 하는 함수인가?

buildFlowTree()에서 traceMethodCall()을 호출하는데, 이 함수가 하는 일을 보자.

먼저 코드에서 사용하는 용어를 정리하면:

용어	설명	예시
scope	메서드를 호출하는 객체(변수명)	userService.selectUser()에서 userService
classIndex	클래스명으로 클래스 정보를 찾는 Map	"UserServiceImpl" → 해당 클래스 정보
isServiceOrDaoCall()	Service나 DAO 호출인지 판별	log.info()는 false, userService.xxx()는 true

private FlowNode traceMethodCall(MethodCall call, int depth) {
    // 1. Service/DAO 호출이 아니면 스킵
    //    → log.info(), StringUtils.isEmpty() 같은 건 추적 안 함
    if (!call.isServiceOrDaoCall()) {
        return null;
    }

    // scope = 호출 대상 변수명 (예: "userService")
    String scope = call.getScope();
    String methodName = call.getMethodName();  // 예: "selectUser"

    // 2. 변수명 → 클래스명 변환 (이전 글에서 설명)
      //    네이밍 컨벤션 + implements 분석으로 해결
    String className = resolveClassName(scope);
    if (className == null) {
        return null;  // 못 찾으면 스킵
    }

    // 3. classIndex에서 해당 클래스 정보 가져오기
    //    classIndex = 파싱할 때 만들어둔 { 클래스명 → 클래스정보 } Map
    ParsedClass targetClass = classIndex.get(className);
    if (targetClass == null) {
        return null;
    }

    // 4. 그 클래스에서 해당 메서드 찾기
    ParsedMethod targetMethod = findMethod(targetClass, methodName);
    if (targetMethod == null) {
        return null;
    }

    // 5. 재귀! 찾은 클래스와 메서드로 다시 buildFlowTree 호출
    return buildFlowTree(targetClass, targetMethod, depth);
}

핵심 포인트:

• buildFlowTree() → traceMethodCall() → buildFlowTree() 순환 구조
• traceMethodCall()은 "변수명에서 클래스를 찾는" 중간 다리 역할

buildFlowTree(UserController, selectUser)
  │
  └── traceMethodCall("userService.selectUser")
        │
        ├── resolveClassName("userService") → "UserServiceImpl"
        │
        └── buildFlowTree(UserServiceImpl, selectUser)  ← 재귀!

동작 과정을 따라가보자

UserController.selectUser()를 분석한다고 하면:

1. buildFlowTree(UserController, selectUser, depth=0)
   → FlowNode("UserController", "selectUser", CONTROLLER) 생성

2. selectUser 안의 호출 찾기
   → userService.selectUser() 발견!
   → userService.selectDeptName() 발견!

3. 첫 번째 호출 추적
   → buildFlowTree(UserServiceImpl, selectUser, depth=1)  ← 재귀!
   → 그 안에서 userDAO.selectUser() 발견
   → buildFlowTree(UserDAO, selectUser, depth=2)  ← 또 재귀!

4. 두 번째 호출 추적
   → buildFlowTree(UserServiceImpl, selectDeptName, depth=1)  ← 재귀!
   → 그 안에서 deptDAO.selectDept() 발견
   → buildFlowTree(DeptDAO, selectDept, depth=2)  ← 또 재귀!

결과적으로 트리가 완성된다:

[depth=0] UserController.selectUser
├── [depth=1] UserServiceImpl.selectUser
│   └── [depth=2] UserDAO.selectUser
└── [depth=1] UserServiceImpl.selectDeptName
    └── [depth=2] DeptDAO.selectDept

---

6. 순환 참조 방지 - 가장 중요!

문제: 무한 루프

만약 A가 B를 호출하고, B가 다시 A를 호출하면?

class A {
    void methodA() {
        b.methodB();  // A → B
    }
}

class B {
    void methodB() {
        a.methodA();  // B → A
    }
}

우리 코드가 이걸 분석하면:

A.methodA()
└── B.methodB()
    └── A.methodA()
        └── B.methodB()
            └── A.methodA()
                └── ... (무한 반복!)

프로그램이 멈추지 않는다!

첫 번째 시도: 방문 체크

"한 번 갔던 곳은 다시 가지 말자"

여기서 visitedMethods라는 변수가 등장한다:

// visitedMethods: 이미 방문한 메서드를 기록하는 Set
// 예: { "UserController.selectUser", "UserServiceImpl.findAll" }
private Set<String> visitedMethods = new HashSet<>();

• Set: 중복을 허용하지 않는 집합 자료구조
• HashSet: 빠른 조회(O(1))를 위해 사용
• signature: "클래스명.메서드명" 형태의 문자열 (예: "UserController.selectUser")

private FlowNode buildFlowTree(...) {
    String signature = className + "." + methodName;

    // 이미 방문했으면 스킵
    if (visitedMethods.contains(signature)) {
        return null;  // 순환 참조!
    }

    visitedMethods.add(signature);  // 방문 표시

    // ... 자식 탐색 ...

    return node;
}

문제 발생!

이 코드에 버그가 있었다.

UserController.selectUser()
├── userService.selectUser()
│   └── userDAO.selectUser()   ← visitedMethods에 추가됨
│
└── userService.checkDuplicate()
    └── userDAO.selectUser()   ← 이미 있어서 스킵됨!

같은 userDAO.selectUser()를 다른 경로에서 호출했는데, "이미 방문했다"고 스킵해버렸다.

이건 순환 참조가 아니다! 그냥 같은 메서드를 두 번 쓴 것뿐이다.

진짜 순환 참조 vs 아닌 것

[진짜 순환 참조 - 막아야 함]
A → B → A → B → ...  (같은 경로에서 반복)

[순환 아님 - 정상 동작해야 함]
A → B → C
A → D → C  (다른 경로에서 C를 또 호출)

해결: 백트래킹

핵심 아이디어:

"현재 가고 있는 경로"만 체크하고, 경로를 벗어나면 체크 해제

private FlowNode buildFlowTree(...) {
    String signature = className + "." + methodName;

    // 현재 경로에 이미 있으면 = 진짜 순환!
    if (visitedMethods.contains(signature)) {
        return node;  // 더 이상 안 들어감
    }

    visitedMethods.add(signature);     // 현재 경로에 추가

    // ... 자식 탐색 ...

    visitedMethods.remove(signature);  // 탐색 끝나면 제거!

    return node;
}

remove()가 핵심이다!

왜 이게 동작하는가?

단계별로 따라가보자.

시작: visitedMethods = { }

1. UserController.selectUser 탐색 시작
   visitedMethods = { UserController.selectUser }

2. → userService.selectUser 탐색
   visitedMethods = { UserController.selectUser, UserServiceImpl.selectUser }

3. → → userDAO.selectUser 탐색
   visitedMethods = { ..., UserDAO.selectUser }

4. userDAO.selectUser 탐색 완료 → remove!
   visitedMethods = { UserController.selectUser, UserServiceImpl.selectUser }

5. userService.selectUser 탐색 완료 → remove!
   visitedMethods = { UserController.selectUser }

6. → userService.checkDuplicate 탐색
   visitedMethods = { UserController.selectUser, UserServiceImpl.checkDuplicate }

7. → → userDAO.selectUser 탐색
   visitedMethods에 없으므로 정상 탐색!  ← 이제 가능!

visitedMethods가 "전체 방문 기록"이 아니라 "현재 경로" 역할을 한다.

이 버그에서 깨달은 것

처음에는 "방문 체크니까 Set에 add만 하면 되지"라고 생각했다.
하지만 이건 "전체 방문 기록"과 "현재 경로"를 혼동한 것이었다.

❌ 잘못된 생각: "한 번 본 메서드는 다시 안 봐도 돼"
✅ 올바른 생각: "지금 가고 있는 길에서 다시 나오면 안 돼"

핵심 교훈:

재귀에서 상태를 관리할 때는 "탐색 완료 후 복원"이 필요할 수 있다.
이것이 백트래킹의 본질이다.

---

7. 전체 그림: 모든 것을 연결하면

여기까지 배운 내용을 정리하면:

• FlowNode: 호출 정보를 담는 트리 노드
• buildFlowTree(): 재귀로 트리를 만드는 함수
• traceMethodCall(): 변수명에서 클래스를 찾아 연결하는 함수
• visitedMethods: 순환 참조를 방지하는 Set

이제 이것들이 실제로 어떻게 연결되어 동작하는지 보자.

분석 시작점: analyze()

// FlowAnalyzer.java

// parsedClasses: JavaParser로 파싱한 클래스들의 목록
//   예: [UserController, UserServiceImpl, UserDAO, ...]
// FlowResult: 분석 결과를 담는 객체 (FlowNode들의 목록)

public FlowResult analyze(Path projectPath, List<ParsedClass> parsedClasses) {
    FlowResult result = new FlowResult(projectPath.toString());

    // 1. 클래스 인덱싱 (classIndex, scopeToClassName 생성)
    indexClasses(parsedClasses);

    // 2. 인터페이스 → 구현체 매핑 (interfaceToImpl 생성)
    buildInterfaceMapping(parsedClasses);

    // 3. Controller에서 시작해서 분석
    for (ParsedClass clazz : parsedClasses) {
        if (clazz.getClassType() == ClassType.CONTROLLER) {
            analyzeController(result, clazz);
        }
    }

    return result;
}

Controller 분석: analyzeController()

private void analyzeController(FlowResult result, ParsedClass controller) {
    for (ParsedMethod method : controller.getMethods()) {
        // @GetMapping, @PostMapping 등이 붙은 메서드만
        if (method.isEndpoint()) {
            // 여기서 buildFlowTree 호출!
            FlowNode flowNode = buildFlowTree(controller, method, 0);
            result.addFlow(flowNode);  // 결과에 추가
        }
    }
}

전체 흐름 한눈에

1. analyze() 호출
   ├── indexClasses()         → classIndex, scopeToClassName 생성
   ├── buildInterfaceMapping() → interfaceToImpl 생성
   │
   └── 각 Controller에 대해:
         └── analyzeController()
               └── 각 엔드포인트에 대해:
                     └── buildFlowTree()  ← 여기서 트리 생성!
                           └── traceMethodCall()
                                 └── resolveClassName()
                                 └── buildFlowTree() ← 재귀!

2. 결과: FlowResult에 FlowNode 트리들이 저장됨

3. 출력: 콘솔이나 Excel로 트리 출력

---

8. 최종 결과

Code Flow Tracer로 분석한 실제 결과:

[GET] /user/detail.do
└── [Controller] UserController.selectUser()
    │
    ├── [Service] UserServiceImpl.selectUser()
    │   └── [DAO] UserDAO.selectUser()
    │       └── SQL: userDAO.selectUser
    │
    └── [Service] UserServiceImpl.selectDeptName()
        └── [DAO] DeptDAO.selectDept()
            └── SQL: deptDAO.selectDept

• Controller에서 시작해서 SQL까지 전체 흐름 추적
• 두 갈래로 분기하는 것도 정확히 표현
• 각 레이어(Controller, Service, DAO) 구분

---

9. 마치며

정리

1. 호출 흐름은 트리 구조
   • 하나가 여러 개를 호출할 수 있음 (1:N)
   • 점점 깊어짐 (depth)
   • 리스트나 맵보다 트리가 적합
2. 트리는 재귀로 만든다
   • "현재 노드 생성 → 자식 탐색 → 자식도 똑같이" 반복
   • buildFlowTree()가 자기 자신을 호출
   • 반복문보다 코드가 직관적
3. 순환 참조 방지는 백트래킹
   • add()만 하면 다른 경로에서 같은 메서드 접근 불가
   • remove()로 "현재 경로"만 체크
   • "전체 방문"과 "현재 경로"는 다르다!

이 글을 쓰며 배운 것

기술적으로:

• 자료구조 선택의 이유를 다른 선택지와 비교하며 설명하는 것의 중요성
• 재귀와 백트래킹의 차이를 명확히 이해

개발 습관으로:

• 버그를 만났을 때 "왜 이렇게 동작하지?"를 깊이 파고드는 것의 가치
• 단순히 "고쳤다"가 아니라 원리를 이해하고 문서화하는 습관

다음 글 예고

이제 호출 흐름을 추적할 수 있게 되었다.
다음 글에서는 DAO에서 호출하는 SQL을 어떻게 찾아서 연결하는지 (iBatis XML 파싱)를 다룬다.

---

참고 자료

• FlowAnalyzer.java - GitHub
• 이전 글: JavaParser로 Java 코드 분석하기

---

이 글은 Code Flow Tracer 프로젝트를 만들면서 배운 내용입니다.