Recursive Function

재귀 함수는 앞으로 다룰 Tree, Heap, Graph에서 사용할 뿐만 아니라,

메모리공간을 많이 사용할 지언정, stack으로 구현해야할 코드의 길이를 획기적으로 단축 시켜줄

고급 스킬 이기 때문에 짚어보고 넘어가겠다.

 

예로들어 -1234와 같은 입력이 들어오면 이를 세로로 출력하는 프로그램을 구현한다고 해보자.

평범한 발상으로는 -, 1, 2, 3, 4를 순서대로 출력한다고 생각할 것이다.

하지만, 재귀적인 발상은 -123을 출력한 뒤 4를 출력한다고 생각하는 것이다.

즉, 함수에서 할 일을 작게 나누어, 큰 일은 미래의 자신(함수)에게 떠넘기고, 본인은 작은 일을 처리한다는 발상이다.

 

재귀 함수를 달성하려면, stopping case와 일의 분할을 명확하게 해야한다.

일을 분할하고, 분할된 일이 작다면 이를 stopping case에 걸리게끔 설계해야 한다.

위에서 언급한 프로그램의 구현을 보며 자세히 알아보자.

 

void write_vertical(int number) {
    if (number < 0) { 
        cout << ‘-’ << endl;
        write_vertical(abs(number)); 
    }
    else if (number < 10)
        cout << number << endl;
    else { 
        write_vertical(number / 10);
        cout << number % 10 << endl;
    }
}

음수라면 우선 -을 출력하고, 양수로 변환한 뒤 본인 자신을 다시 호출한다.

만약 숫자가 10보다 작다, 즉 1의 자리 수라면 출력하고, 그렇지 않다면 10으로 나눈 몫을 인자로 본인 자신을 다시 호출한다.

이후 10의 나머지 값을 출력한다.

 

-123을 예로 들면

첫 번째 호출 스택에서는 -가 출력되고, 1234을 인자로 호출된다.

두 번째 호출 스택에서는 1234/10 = 123를 인자로 호출된다.

세 번째 호출 스택에서는 123/10 = 12이 인자로 호출된다.

네 번째 호출 스택에서는 12/10 = 1이 인자로 호출된다.

다섯 번째 호출 스택에서는 1이 출력된다. 그리고 호출 스택에서 제거된다(리턴된다).

리턴 후 네 번째 호출 스택에서 12%10 = 2가 출력된 후 호출 스택에서 제거된다(리턴된다).

리턴 후 세 번째 호출 스택에서 123%10 = 3이 출력된 후 호출 스택에서 제거된다(리턴된다).

리턴 후 두 번째 호출 스택에서 1234%10 = 4가 출력된 후 호출 스택에서 제거된다(리턴된다).

리턴 후 첫 번째 호출 스택에서 아무런 동작을 수행하지 않고 호출 스택에서 제거된다(리턴된다).

 

 

위의 예시로는 재귀함수 내에서 본인을 한 번만 호출하는 경우를 살펴봐서 이해하기에는 편했을 것이다.

하지만 이런 경우에는 그냥 stack으로 구현하는 경우와 코드의 길이가 크게 달라지지 않는다.

정말 재귀함수가 필요한 부분은 재귀함수 내에서 2개 이상의 재귀함수가 호출되는 경우이다.

void random_fractal(double left_height, double right_height, double width, double epsilon) {
    double mid_height;
    assert(width > 0);
    assert(epsilon > 0);
    if (width <= epsilon)
        display(right_height); //or left_height
    else {
        mid_height = (left_height + right_height) / 2;
        mid_height += random_real(-width, width);
        random_fractal(left_height, mid_height, width / 2, epsilon);
        random_fractal(mid_height, right_height, width / 2, epsilon);
    }
}

위 함수는 위/아래로 지그재그 요동치는 그래프를 그리는 함수로 epsilon이 stopping case를 위해 사용되었다.

호출스택이 증가할수록, width의 길이가 반으로 줄어들며

이 길이가 epsilon만큼 짧아질 때 까지 본인을 두 번씩 호출하는 재귀함수이다.

처음에는 왼쪽/오른쪽의 높이값을 인자로 넣어주지만, 재귀 호출시

왼쪽/가운데, 가운데/오른쪽의 높이값을 인자로 넣어주어 점점 쪼개어가며 그래프를 그린다.

 

분석은 여러분 개인의 몫..!