[ps 팁] 재귀는 마치 누군가가 종이에 숫자를 쓰고, 그 종이를 다음 사람에게 넘겨주는 방식과 같다

아래의 코드를 보면 DFS여서 매번 재귀할 때마다 함수 첫 번째 줄부터 다시 시작하는데

저렇게 int cnt = 1;

해 버리면 카운트를 하다가도 계속 1로 초기화되는 거 아닌가..?

 

처음엔 그렇게 보일 수도 있지만, 재귀 함수에서는 각 함수 호출마다 자신만의 지역변수 스코프(scope)를 가지기 때문에

int cnt = 1;

이거는 그 호출된 함수 하나에만 국한되는 초기화다

private static int dfs(int V) {
    visited[V] = true;
    int cnt = 1; // 자기 자신 포함

    for (int next : graph[V]) {
        if (!visited[next]) {
            cnt += dfs(next); // 재귀 호출 결과 누적
        }
    }

    return cnt;
}

 

이 재귀 함수는 마치 사람들이 종이에 숫자를 적고, 다음 사람에게 넘기고, 다시 받아오는 것과 같다. 자세히 보자!

1. dfs(1)이 호출되면, 자기 전용 종이를 꺼내고 cnt = 1 이라고 적는다
2. dfs(1)은 연결된 노드가 있어서 dfs(2)를 호출한다
3. dfs(2)도 자기만의 새 종이를 꺼내고 cnt = 1 이라고 적는다
4. 계속 연결된 노드가 있으면 이 과정이 반복된다. 각 사람이 자기만의 종이를 갖고 계산을 수행한다!
5. 마지막 노드까지 도달한 뒤에는 더 이상 갈 데가 없으니, 그 종이를 들고 이전 사람에게 값을 전달한다
6. 이전 사람은 그 값을 자기 종이에 적힌 cnt에 더한다 (예: cnt += dfs(next))
7. 그렇게 하나씩 위로 돌아오면서, 최종적으로 dfs(1)까지 모든 감염 가능한 노드 수가 누적된다

즉, 종이는 계속 새로 생기고, 계산이 끝나면 값을 들고 되돌아오는 구조라고 생각하면 된다 (:

 

 

 

"재귀는 마치 누군가가 종이에 숫자를 쓰고, 그 종이를 다음 사람에게 넘겨주는 방식과 같다"