다중 재귀 호출

---

재귀 호출은 하나의 작업을 서로 비슷한 두 개의 작은 작업으로

반복적으로 분할해가면서 처리해야 하는 상황에서 특히 유용하다.

예를 들어, 눈금자를 그리는 상황을 생각하자.

두 개의 끝을 먼저 표시 후, 그들의 중간 지점을 찾아 눈금을 표시한다.

동일한 절차를 눈금자의 왼쪽 절반에 대해 수행한다.

오른쪽에도 마찬가지로 수행한다.

눈금 간격을 더욱 세분하려면 현재의 눈금 구획에 대해 동일한 절차를 수행한다.

이러한 재귀적인 접근을 분할과 정복 ( Divide - and - Conquer ) 이라고 한다.

---

다음 예제는 subdivide()라는 재귀 함수를 사용하여 이것을 설명한다.

처음 subdivide() 함수는, 양쪽 끝이 | 문자이고 나머지가 모두 빈칸 문자로 채워진

하나의 문자열을 사용한다.

이 프로그램은 subdivide() 함수를 6번 호출하는 루프를 사용한다.

    //-------------------------[ ProtoType ]-----------------------------------//
    void subdivide(char ar[], int low, int high, int level);
    const int Len{ 66 };
    const int Divs{ 6 };
    
    //-------------------------[   FBody   ]-----------------------------------//
    int main()
    {
        char ruler[Len];
        for (int i{1}; i < Len - 2; i++)
        {
            ruler[i] = ' ';
        }
        ruler[Len - 1] = '\0';
        int max = Len - 2;
        int min{};
    
        ruler[min] = ruler[max] = '|';
        cout << ruler << endl;
        
        for (int i{ 1 }; i <= Divs; i++)
        {
            subdivide(ruler, min, max, i);
            cout << ruler << endl;
            for (int j{ 1 }; j < Len - 2; j++)
            {
                ruler[j] = ' ';
            }
        }
    
        return 0;
    }
    
    //-------------------------[ Func.Def. ]-----------------------------------//
    
    void subdivide(char ar[], int low, int high, int level)
    {
        if (level == 0) return;
    
        int mid = (high + low) / 2;
        ar[mid] = '|';
        subdivide(ar, low, mid, level - 1);
        subdivide(ar, mid, high, level - 1);
    }

😎 프로그램 실행 결과 :

😁 프로그램 분석 :
subdivide() 함수는 재귀 호출 단계를 제어하기 위해 level이란 변수를 사용한다.

함수가 자신을 호출할 때마다 level은 1씩 감소하며 0이 되면 종료된다.

subdivide() 함수는, 자신을 두 번 호출한다.

한 번은 왼쪽 구획을 나누기 위해서, 다른 한번은 오른쪽 구획을 나누기 위해서이다.

최초의 중간 지점은 왼쪽 구획을 나누기 위한 호출에서 오른쪽 끝이 되고,

오른쪽 구획을 나누기 위한 호출에서는 왼쪽 끝이 된다.

재귀 호출의 수는 기하급수적으로 증가하는데, 한 번의 호출이 두 번의 호출을,

두 번의 호출은 네 번의 호출을.. 이런식으로 계속 진행하면

6단계의 호출은 눈금자를 64개의 칸으로 채우게 된다. ( 2^6 = 64 )

---

함수 호출의 수가 계속해서 2배씩 증가하기 때문에,

재귀 호출이 많이 요구되는 경우에 이와 같은 재귀는 잘못된 선택이다.

하지만, 필요한 재귀 호출의 단계가 적을 경우, 이것은 우아하고 간단한 선택이다.

---

출처 : C++ 기초 플러스 6판 / 성안당

---