재귀, DFS, 백트래킹

• 재귀는 스스로의 함수 또는 매소드를 호출하는 방식이다.
  • DFS는 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다. 깊이를 우선적으로 탐색하기 때문에 재귀 또는 스택을 이용한다.
  • 백트래킹은 재귀를 통해 알고리즘을 푸는 기법 중 하나로 가지치기를 통해 탐색을 하다가 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 찾는 방법이다.
• DFS와 백트래킹 모두 재귀를 이용하는 하나의 방식으로 이해하면 되며, DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이고, 백트래킹은 불필요한 탐색이라고 판단되면 탐색을 중지하고 다른 노드에 대해 탐색하는 것이다.
  • 상황에 따라서 DFS와 백트래킹 기법을 혼용할 수 있다.

🔹 즉, DFS와 백트래킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지만 두 기법을 혼용하여 사용하는 것이 가능하다. 완전히 다른 개념이 아니라 재귀 호출을 통한 기법 중 하나 이기 때문이다.