재귀 함수

재귀 함수는 프로그래밍에서 강력하고 유용한 도구입니다. 특히 DFS(깊이 우선 탐색)와 같은 알고리즘에서 재귀를 사용하여 문제를 해결할 수 있습니다. 이번 포스트에서는 재귀 함수의 기본 개념과 사용 시 주의사항, 그리고 실제 활용 예제를 소개하겠습니다.

재귀 함수란?

재귀 함수는 함수가 자신을 호출하는 함수입니다. 함수가 자신의 문제를 해결하기 위해 동일한 방식으로 자신을 호출함으로써 문제를 점진적으로 해결합니다. 재귀 함수는 주로 다음과 같은 두 가지 조건을 충족해야 합니다:

1. 기저 조건(Base Case): 함수가 더 이상 자기 자신을 호출하지 않고 직접 결과를 반환하는 조건입니다. 이를 통해 무한 호출을 방지합니다.
2. 재귀 조건(Recursive Case): 함수가 자신을 호출하여 문제를 더 작은 단위로 나누어 해결합니다.

재귀 함수 사용 시 주의사항

1. 기저 조건 설정:
   • 재귀 함수는 반드시 종료 조건을 명확하게 설정해야 합니다. 기저 조건이 없다면 함수는 무한히 호출되어 스택 오버플로우를 발생시킬 수 있습니다.
2. 스택 오버플로우:
   • 재귀 호출이 너무 깊어지면 프로그램의 호출 스택이 가득 차서 스택 오버플로우가 발생할 수 있습니다. 재귀 깊이가 너무 깊어질 것 같다면 반복문으로 대체할 수도 있습니다.
3. 디버깅:
   • 디버깅 모드에서 호출 스택을 확인하여 함수 호출의 흐름을 파악하는 것이 좋습니다. 이로 인해 재귀 함수의 상태와 호출 경로를 쉽게 추적할 수 있습니다.
4. 재귀의 층(레벨) 이해:
   • 재귀 호출이 발생할 때마다 호출 스택에 쌓이는 레벨을 이해하고, 각 호출이 어떤 역할을 하는지 파악해야 합니다.
5. 브랜치와 연결:
   • 재귀 함수의 호출은 트리 구조로 표현될 수 있습니다. 각 호출은 분기(branch)를 형성하며, 이 분기들은 서로 연결됩니다.
6. 재귀와 스택의 차이:
   • 스택을 직접 사용하여 문제를 해결하는 방법과 재귀를 사용하는 방법 모두 호출 스택을 활용하지만, 재귀는 함수 호출 자체로 스택 관리를 자동화합니다. 반면, 스택을 명시적으로 사용하면 호출 스택을 직접 관리해야 합니다.

재귀 함수 활용 예제

1. 팩토리얼 계산:
   • 재귀를 사용하여 숫자의 팩토리얼을 계산하는 간단한 예제입니다.

   #include <iostream>
   
   int factorial(int n) {
       if (n <= 1) return 1;
       return n * factorial(n - 1);
   }
   
   int main() {
       int num;
       std::cout << "Enter a number: ";
       std::cin >> num;
       std::cout << "Factorial of " << num << " is " << factorial(num) << std::endl;
       return 0;
   }

2. DFS(깊이 우선 탐색):
   • 그래프를 탐색할 때 DFS를 재귀적으로 구현하는 예제입니다. 이 예제에서는 2차원 배열을 사용하여 상하좌우로 이동하는 DFS를 구현합니다.

   #include <iostream>
   #include <vector>
   
   const int ROWS = 4;
   const int COLS = 4;
   
   void dfs(int x, int y, std::vector<std::vector<bool>>& visited, const std::vector<std::vector<int>>& grid) {
       if (x < 0 || x >= ROWS || y < 0 || y >= COLS || visited[x][y] || grid[x][y] == 0) {
           return;
       }
   
       visited[x][y] = true;
       std::cout << "Visiting (" << x << ", " << y << ")" << std::endl;
   
       // 상하좌우로 이동
       dfs(x + 1, y, visited, grid);
       dfs(x - 1, y, visited, grid);
       dfs(x, y + 1, visited, grid);
       dfs(x, y - 1, visited, grid);
   }
   
   int main() {
       std::vector<std::vector<int>> grid = {
           {1, 1, 0, 0},
           {1, 1, 0, 0},
           {0, 0, 1, 1},
           {0, 0, 1, 1}
       };
       std::vector<std::vector<bool>> visited(ROWS, std::vector<bool>(COLS, false));
   
       // DFS 시작
       dfs(0, 0, visited, grid);
   
       return 0;
   }

   • 예제 설명:
     • dfs 함수는 주어진 좌표에서 상하좌우로 이동하면서 방문하지 않은 지점을 재귀적으로 탐색합니다. visited 배열을 사용하여 이미 방문한 지점을 다시 방문하지 않도록 합니다.

결론

재귀 함수는 문제를 해결하는 강력한 도구이지만, 사용 시 주의사항을 충분히 고려해야 합니다. 기저 조건을 명확하게 설정하고, 디버깅 도구를 사용하여 호출 스택을 추적하는 것이 중요합니다. 재귀는 DFS와 같은 문제 해결에서 유용하게 사용되며, 트리 구조나 그래프 탐색에서도 그 효용을 발휘합니다. 재귀와 스택의 차이를 이해하고 적절한 경우에 재귀를 사용하는 것이 프로그램의 효율성을 높이는 데 도움이 됩니다.