그림 6-25를 보면 현재 정점은 0입니다. 먼저 방문하고 visited[0]=True로 합니다. adj[0]을 구하면 adj[0]={1}입니다. 그런데 정점 1은 이미 방문한 상태입니다. 현재 정점 0에서 더 이상 갈 수 있는 곳이 없습니다. 그렇다면 정점 0으로 오기 전 정점으로 돌아가야 합니다. 정점 0에서 정점 1로 어떻게 돌아갈 수 있을까요? 간단합니다. 현재 스택 프레임의 바로 밑에 매개변수 1을 가진 스택 프레임이 있지요. 그 스택 프레임으로 돌아간다는 것은 현재 정점 0에서 정점 1로 돌아간다는 것입니다. for 문이 끝나는 동안 아직 방문하지 않은 정점을 발견하지 못했다면 __dfs_recursion(0)은 종료됩니다. 함수가 종료되면 스택 프레임도 사라집니다. 그래서 바로 아래의 스택 프레임인 정점 1로 돌아올 수 있는 것입니다.

▲ 그림 6-25 DFS 3