lastnamesong

재귀함수 사용법 (Recursive function, 재귀함수 C++, DFS, 팩토리얼) 본문

Algorithm

재귀함수 사용법 (Recursive function, 재귀함수 C++, DFS, 팩토리얼)

응솩이 2025. 6. 20. 22:22
반응형

DFS에 대해 소개하는 글도 쓰고 예제도 많이 풀었지만, 이를 구현하는 방법에서 가장 핵심적인 요소인 재귀함수에 대해 정리했던 적은 없는 것 같다. 재귀함수의 원리는 알고 있고, 코드를 보면 이해하는 데에는 무리가 없지만, 배경이 없는 상태에서 재귀함수를 구현하려고 하면 원하지 않는 출력이 나오거나, 함수가 끝나지 않아서 런타임 에러가 나는 이슈가 종종 있다.

 

이번 글에서는 C++ 예제와 함께 재귀함수가 무엇인지, 어떻게 사용하는지, 그리고 주의할 점은 무엇인지에 대해 하나하나 짚어보려 한다.


재귀함수(recursive function)는 함수 내부에서 자기 자신을 다시 호출하는 함수를 의미한다.

재귀는 문제를 더 작은 문제로 쪼갤 수 있을 때 특히 강력하다. 반복문으로도 해결 가능한 문제를 더 간결하고 논리적으로 표현할 수 있기 때문이다. 하지만 개념을 정확히 이해하지 못하면, 무한 반복이나 메모리 초과와 같은 오류를 겪기 쉽다.

재귀함수의 구성 요소

재귀함수를 구현할 때 반드시 고려해야 할 3가지 핵심 요소가 있다. 이 세 가지가 빠지면 코드가 무한 반복되거나, 프로그램이 멈추는 등의 문제가 발생한다.

1. 기저 조건 (Base Case)

기저 조건은 재귀 호출을 멈추는 조건이다. 일종의 ‘탈출구’이며, 더 이상 자기 자신을 호출하지 않도록 만드는 역할을 한다.
재귀 함수는 함수 내부에서 자기 자신을 계속 호출하는 구조이기 때문에, 멈추는 조건이 없다면 무한히 호출된다. 이로 인해 프로그램이 비정상 종료되거나 스택 오버플로우(stack overflow)가 발생할 수 있다.

 

팩토리얼 함수를 예로 들면,

if (n == 0) return 1;

 

이 조건이 없으면 factorial(n)은 끝없이 factorial(n-1)을 호출하게 된다.

2. 자기 자신을 호출하는 부분 (Recursive Case)

기본적으로 재귀는 자기 자신을 다시 부르는 구조이다. 이 부분은 문제를 점점 더 작게 쪼개는 역할을 한다.
주어진 문제를 단순한 형태로 바꾸어 나가다 보면 결국 기저 조건에 도달하게 된다. 이 과정을 통해 문제를 해결할 수 있다.

팩토리얼 함수에서,

return n * factorial(n - 1);

 

여기서 factorial(n - 1)이 바로 자기 자신을 다시 호출하는 부분이다.

3. 작아지는 문제 (진행 조건)

재귀함수를 사용할 때마다 문제가 조금씩 단순해져야 한다. 즉, 기저 조건에 가까워지도록 매번 문제를 줄여나가야 한다.
재귀 호출을 반복해도 계속 같은 문제를 호출하면 기저 조건에 도달하지 못한다. 따라서 매 호출마다 입력이 조금씩 달라져야 하고, 결국 종료 조건에 도달해야 한다.

 

팩토리얼 함수에서,

factorial(n - 1)

 

n이 매번 1씩 작아지므로 결국 n == 0에 도달한다.

다양한 재귀함수 예시

가장 처음으로 나오는 예시는 이전 글에서 많이 공부했던 DFS이다.

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";

    for (int next : graph[node]) {
        if (!visited[next]) dfs(next);
    }
}

명시적으로 if (node == ...) return;와 같이 특정 조건이 되면 끝나는 내용은 없지만, visited[next]true이면 조건문을 탈출하므로 기저조건에 해당한다.

if (!visited[next]) dfs(next);

즉, 이미 방문한 노드는 다시 방문하지 않도록 하여 재귀의 깊이가 무한히 깊어지는 것을 방지하고 있다.

또한 dfs(next);를 통해 재귀적인 부분을 만족하고 있으며, visited[node] = true;를 통해 재귀가 기저 조건으로 수렴할 수 있도록 한다.

팩토리얼 외에도 피보나치 수열을 구하는 문제를 재귀적으로 풀 수 있다.

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

배열의 합도 재귀적으로 구할 수 있다.

int sum(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sum(arr, n - 1);
}

재귀함수를 사용할 때에는 스택 오버플로우, 기저 조건과 같은 부분을 놓치지 않도록 조심해야할 것이다. 특히 DFS나 백트래킹 문제에서는 거의 필수적으로 등장하며, 복잡한 반복문보다 더 깔끔한 코드를 작성할 수 있게 도와준다.

 

결국 이 모든 것들을 잘 학습하는 법은 그냥 많이 해보는 것이리라..

반응형