C++ 재귀(Recursion) 총정리

1. 재귀(Recursion)함수의 개념

C++에서의 재귀는 주어진 조건이 만족될 때까지 함수가 반복적으로 자신을 호출하는 기술이다. 즉, 재귀는 문제를 더 작고 간단한 하위 문제로 분해하여 해결하는 과정이라 할 수 있다. 우리의 노가다 같은 수고를 덜어주는 기술인 것이다.

 

구문:

return_type recursive_func {
    ....
       // Base Condition
       // Recursive Case
       ....
}

 

이제 여기서, 자기 자신을 호출하는 함수를 재귀 함수라고 한다. 재귀 함수가 호출되면 명령어 집합을 실행한 다음, 자기 자신을 호출하여 더 작은 입력으로 동일한 명령어 집합을 실행한다. 이 과정은 재귀를 멈추고 값을 반환하는 조건인 베이스 케이스에 도달할 때까지 계속된다.

 

기저 조건(Base Case): 기저 조건은 재귀를 종료하는 데 사용되는 조건이다. 재귀 함수는 기저 조건이 만족될 때까지 계속해서 자신을 호출할 것이다.

 

재귀 조건(Recursive case): 이것은 함수에 재귀적 호출이 존재하는 방식이다. 재귀적인 경우는 여러 개의 재귀적 호출을 포함하거나, 마지막에 기본 조건이 충족되고 재귀가 종료되도록 다른 매개 변수를 포함할 수 있다.

 

예시:

// C++ Program to calculate the sum of first N natural
// numbers using recursion
#include <iostream>
using namespace std;

int nSum(int n)
{
    // base condition to terminate the recursion when N = 0
    if (n == 0) {
        return 0;
    }

    // recursive case / recursive call
    int res = n + nSum(n - 1);

    return res;
}

int main()
{
    int n = 5;

    // calling the function
    int sum = nSum(n);

    cout << "Sum = " << sum;
    return 0;
}

 

출력:

Sum = 15

 

위 프로그램에서 nSum()이 재귀 함수다.
Recursive Case는 int res = n + nSum(n – 1) 식이다.
Base Case는 (n == 0) { return 0;}이다.

2. C++에서 재귀 작업

위 프로그램을 토대로 재귀가 이뤄지는 작업에 대해 자세히 이해하도록 한다.

 

① nSum() 함수에서 Recursion Case는 다음과 같다.

int res = n + nSum(n - 1);

 

② n=5 이므로, nSum(5)에 따라 다음과 같은 결과를 얻는다.

int res = 5 + nSum(4);

③ nSum(4) ~ nSum(1) 에서는 다음과 같은 결과를 얻는다. 일단 nSum(0) 이상은 다루지 않는다.

int res = 4 + nSum(3);

int res = 3 + nSum(2);
int res = 2 + nSum(1);
int res = 1 + nSum(0);

 

④ 이제 nSum() 함수의 리턴 값은 res라고 하는 정수에 있음을 기억한다. 따라서 함수 대신에 이들 함수에 의해 반환되는 값을 넣을 수 있다. nSum(5)의 경우는 다음과 같다.

int res = 5 + 4 + nSum(3);

 

⑤ 마찬가지로, 모든 n에 대해 nSum()의 반환 값을 대입하면 다음과 같은 결과를 얻는다.

int res = 5 + 4 + 3 + 2 + 1 + nSum(0);

 

⑥ nSum() 함수에서 base case는 아래와 같다.

if (n == 0) {
    return 0;
}

 

⑦ 즉, nSum(0)이 0을 반환할 때, 이 값을 nSum(5)의 Recursive Case에 대입하면 아래와 같다.

int res = 5 + 4 + 3 + 2 + 1 + 0;
           = 15

 

⑧ 이 시점에서 Recursive Case에는 함수 호출이 남지 않음을 알 수 있다. 따라서 재귀는 여기서 멈추고 함수에 의해 반환되는 최종 값은 처음 5개의 자연수를 합한 15가 되는 것이다.

3. 재귀에서의 메모리 관리

다른 모든 함수들과 마찬가지로 재귀 함수의 데이터는 스택 프레임의 형태로 스택 메모리에 저장된다. 함수가 어느 정도의 값을 반환하면, 이 스택 프레임은 삭제된다. 재귀에서는 아래와 같은 포인트가 있다.

① 함수 호출은 값을 반환하기 전에 수행되므로, 점진적 재귀 호출을 위한 스택 프레임은 스택 메모리의 기존 스택 프레임 위에 저장된다.
② 최상위 함수 복사본이 일부 값을 반환하면 해당 스택 프레임이 파괴되고, 상위 복사본에 대한 재귀 호출이 수행된 지점 바로 뒤에 컨트롤이 해당 특정 복사본 바로 앞에 있는 함수로 이동한다.
③ 컴파일러는 함수 실행 후 반환할 위치를 추적하기 위해 명령 포인터를 유지한다.

 

그러면 앞에서 다룬 예시인 nSum(5) 함수의 메모리 관리에 대해 알아보도록 하자.

 

1단계: nSum()이 인수로 5인 main() 함수에서 호출되면 nSum(5)에 대한 스택 프레임이 생성된다.

 

2단계: nSum(5)을 실행하는 동안, 재귀 호출이 nSum(4)로 발생한다. 컴파일러는 이제 nSum(5)의 스택 프레임 위에 새로운 스택 프레임을 생성하고, nSum(4)이 발생한 문에 명령 포인터를 유지한다.

 

3단계: nSum(4)의 실행이 시작되지만, 이전 함수와 마찬가지로 nSum(3)과 같은 재귀 호출이 발생한다. 컴파일러는 다시 동일한 단계를 따라 nSum(3)에 대한 다른 명령 포인터 및 스택 프레임을 유지한다.

 

4단계: 이후 nSum(3), nSum(2) 및 nSum(1)의 실행에서도 위에서와 동일한 과정이 발생한다.

 

5단계: 그러나 nSum(0)이 되면 조건(n == 0)이 true가 되고 문 반환 0이 실행된다.

 

6단계: 값이 nSum(0)에 의해 반환되면, nSum(0)에 대한 스택 프레임이 파괴되고, 명령 포인터를 사용하여 프로그램 컨트롤이 nSum(1) 함수로 돌아가고, nSum(0) 호출이 값 0으로 대체된다.

7단계: 이제 nSum(1)에서 int res = 1 + 0을 평가하고 return res를 실행한다. 프로그램 컨트롤은 명령 포인터를 사용하여 nSum(2)로 이동한다.

8단계: nSum(2)에서 nSum(1) 호출은 반환된 값인 1로 대체된다. 따라서 int res = 2 + 1을 평가한 후 3은 nSum(3)으로 반환된다. 제어 장치가 다시 nSum(5)에 도달할 때까지 동일한 과정이 계속 발생한다.

 

9단계: 컨트롤이 nSum(5)에 도달하면 int res = 5 + nSum(4)라는 표현은 int res = 5 + 10처럼 보이고, 마지막으로 이 값은 main () 함수로 되돌아가고 nSum() 함수의 실행은 중지된다.

 

※ 스택 오버플로우

스택 오버플로우는 함수가 스스로를 너무 많이 호출할 때 발생하는 재귀와 관련된 가장 일반적인 오류 중 하나다. 우리는 각 재귀 호출이 제한된 스택 메모리에서 별도의 공간을 필요로 한다는 것을 알고 있다. 많은 재귀 호출이 있거나, 재귀가 무한대로 계속된다면, 이 스택 메모리는 소진되어 프로그램의 종료로 이어지는 더 많은 데이터를 저장하지 못할 수 있다.

4. 재귀의 유형

C++에서 재귀는 2가지 유형이 존재한다. 직접 재귀(Direct Recursion)와 간접 재귀(Indirect Recursion)가 그 2가지다.

 

① 직접 재귀(Direct Recursion)

직접 재귀에서 함수는 자기 자신에 대한 하나 이상의 재귀적 호출을 포함한다. 함수는 직접 재귀에서 자기 자신을 직접 호출하며, 중간 함수는 없다. 직접 재귀는 함수의 본체에 얼마나 많은 재귀적 호출이 존재하는지에 따라 세 가지 유형으로 분류할 수도 있다.

⑴ 머리 재귀(Head Recursion): 머리 재귀에서 재귀 호출은 함수의 시작 부분에 존재한다. 이것은 단일 재귀 호출만 사용되는 일종의 선형 재귀다.

⑵ 꼬리 재귀(Tail Recursion): 꼬리 재귀는 함수의 끝에 하나의 재귀 호출만 존재하는 선형 재귀다. 재귀 호출은 일반적으로 함수의 마지막 문장이다. 꼬리 재귀의 중요성은 꼬리 호출 최적화를 사용하여 메모리 소비를 줄일 수 있다는 것이다.

⑶ 트리 재귀(Tree Recursion): 트리 재귀에서는 함수의 본문에 여러 재귀 호출이 존재한다. 트리 재귀를 추적하는 동안, 여러 재귀 호출이 한 함수에서 분기하는 트리와 같은 구조를 얻는다.

 

② 간접 재귀(Indirect Recursion)

간접 재귀에서는 함수가 직접 호출하지 않고 대신 다른 함수를 호출하여, 결국 첫 번째 함수를 호출하여 함수 호출 주기를 만든다.

5. C++에서 재귀의 예시

피보나치 수열 예시:

// C++ Program to find fibonacci series using recursion
#include <iostream>
using namespace std;

// Function for fibonacci
int fib(int n)
{
    // Stop condition
    if (n == 0)
        return 0;
    // Stop condition
    if (n == 1 || n == 2)
        return 1;
    // Recursion function
    else
        return (fib(n - 1) + fib(n - 2));
}

// Driver Code
int main()
{
    // Initialize variable n.
    int n = 5;
    cout << "Fibonacci series of 5 numbers is: ";
    // for loop to print the fibonacci series.
    for (int i = 0; i < n; i++) {
        cout << fib(i) << " ";
    }
    return 0;
}

 

출력:

Fibonacci series of 5 numbers is: 0 1 1 2 3 

 

재귀를 사용한 배열의 역순 프린트 예시:

// C++ Program to print array using
// recursion
#include <iostream>
using namespace std;

// recursive function to print array
void pArray(int* arr, int n)
{
    // base condition
    if (n == 0) {
        return;
    }
    // recursive call
    cout << arr[n - 1] << ' ';
    pArray(arr, n - 1);  
}

int main()
{
    // declaring array
    int arr[5] = { 1, 2, 3, 4, 5 };
    // calling function
    pArray(arr, 5);
    return 0;
}

 

출력:

5 4 3 2 1

6. 재귀 사용 전 주의사항

① 성능: 재귀 알고리즘은 특히 데이터 구조가 크거나 재귀가 너무 깊을 경우, 반복 알고리즘보다 효율성이 떨어질 수 있다.
② 메모리 사용량: 재귀 알고리즘은 특히 재귀가 너무 깊거나 데이터 구조가 큰 경우 많은 메모리를 사용할 수 있다. 각 재귀 호출은 호출 스택에 새로운 스택 프레임을 생성하고, 이는 곧 메모리 사용량을 크게 늘릴 수 있을 것이다.
③ 코드 복잡도: 재귀 알고리즘은 반복 알고리즘보다 더 복잡할 수 있다.
④ 디버깅: 재귀 알고리즘은 반복 알고리즘보다 디버그하기가 더 어려울 수 있다. 특히 재귀가 너무 깊거나 프로그램이 여러 재귀 호출을 사용하는 경우 더 그렇다.
⑤ 스택 오버플로우: 재귀가 너무 깊이 들어가면 스택 오버플로우 오류가 발생하여 프로그램이 다운될 수 있다.