알고리즘 2-1이 이미 있는 상태에서 왜 알고리즘 2-4를 개발했는지 의아할 수도 있다. 실제 재귀 함수가 어떻게 작동하는지를 파악할 수 있게 암묵적 재귀 함수는 컴퓨터가 재귀 호출을 할 때마다 함수의 모든 메모리 상태를 스택에 넣어둔다. 그래서 그림 2-25의 단순한 숫자들보다 (함수 호출만을 보여준) 그림 2-24의 스택에 더 많은 것을 전달한다. 실제 명시적 스택으로 구현한 알고리즘은 같은 기능의 재귀 알고리즘보다 경제적이다.

깊이 우선 탐색을 마무리하며 알고리즘 2-1로 돌아가 알고리즘의 복잡도를 검토해 보자. 알고리즘 2-3과 2-4의 복잡도는 전반적인 탐색 전략이 아닌 재귀 메커니즘만을 변경한 구현이므로 알고리즘 2-1의 복잡도와 동일하다. 4행은 정점마다 한 번씩 수행하여 |V|번 수행된다. 3행의 조건은 모든 인접 리스트의 간선마다 정확히 한 번 호출된다(즉, |E|번). 모두 합하면 깊이 우선 탐색의 복잡도는 (|V|+|E|)가 된다. 우리는 그래프의 크기에 비례하여 그래프를 탐색할 수 있으며, 이것은 수용할 만하다.