2장 순환

 

 

순환이란?

순환은 자기 자신을 호출함으로써 문제를 해결하는 프로그래밍 기법입니다! 설정한 조건까지 끊임없이 자기 자신을 호출하여 값을 도출해내는 것이 반복문과 비슷한 성질을 가지고 있죠. 실제로도 반복문을 순환적으로 변환시킬 수 있고, 순환 함수를 반복문의 형태로 정의할 수도 있습니다! 

 

순환은 팩토리얼 예제를 통해 보다 더 쉽게 이해할 수 있습니다. 팩토리얼은 1과 자기 자신까지의 정수를 모두 곱한 것을 의미합니다. 

int factorial(int n) {
    if( n <= 1) 
   	return 1;
    else 
        return (n * factorial(n - 1));
}

순환 알고리즘은 순환하는 부분과 순환을 멈추는 부분으로 나뉘게 되는데 이때 순환을 멈추는 부분을 반드시 설정해줘야 됩니다. 순환을 멈추는 부분을 설정해두지 않으면 우리가 흔히 말하는 무한 루프처럼 끝없이 함수를 순환하기 때문이죠! 

 

위 함수에서 순환을 멈추는 부분은 아래와 같습니다. 

if(n<=1)
    return 1;

n이 1보다 작거나 같아지는 순간 1을 반환하는 것을 알 수 있습니다. 순환하는 부분을 자세히 보면 계속해서 n - 1을 호출하는 것을 볼 수 있는데, n이 점점 작아지다 결국 1보다 작거나 같아지는 순간 순환문은 1을 반환하고 종료하게 되는 것입니다.

 

순환이 진행되는 과정은 이렇습니다.

factorial (4) = 4 * factorial(3)

                     = 4 * (3 * factorial(2))

                     = 4 * (3 * (2 * factorial(1))

                     = 4 * (3 * (2 * (1)))

                     = 4 * 3 * 2 * 1 

                     = 4!

 

그렇다면 순환으로 작성된 프로그램을 반복문으로 어떻게 바꾸는지 예제로 알아보겠습니다. 

int factorial (int n){
    total = 1;

    for(int i = 1; i <= n; i++){
        total *= i;
    }
    return total;
}

기존에 순환으로 진행되었던 곱셈 부분을 for문 안에 넣어, 1부터 n까지 차례대로 곱하도록 작성하였습니다. 

 

순환과 반복은 유사하지만 차이점 또한 존재합니다. 

순환이 자기 자신을 호출하는 것은 함수에서 다른 함수를 호출하는 것과 동일합니다. 함수를 호출하게 되면 활성 레코드(Activation Record)에 복귀 주소, 지역변수 등이 저장되는데, 이때 함수의 상태를 기억하는 과정에서 메모리의 공간을 많이 차지할 수도 있습니다. 

따라서 순환을 사용하는 것은 사용자의 이해를 돕는 측면에서는 좋지만, 프로그램의 수행 시간과 공간 활용적인 측면에서 비효율적인 부분도 존재한다는 것입니다! 

용도에 따라 순환과 반복을 적절히 잘 분배해서 사용하는 것이 중요하게 되겠습니다.  

---

다양한 순환 예제

거듭제곱 계산

double power(int n, double x){
    if(n==1)
        return 1;
    else if(n%2==0){
        return power(n/2, x*x)
    }
    else return x * power(n/2, x*x);
}

기존의 거듭제곱을 알고리즘은 반복문으로 1부터 n까지 x를 거듭해서 곱해주는 것이였다면, 순환을 이용한 알고리즘은 작게는 $x^{2}$ 부터 $x^{3}$까지 한번에 곱하면서 빠르게 결과 값 까지 접근이 가능합니다.

 

하노이 탑

상당히 많은 분들이 하노이 탑을 생각하고 구현해내는데 있어서 어려움을 느끼고 있는 것 같습니다. 저 또한 처음 순환 알고리즘을 접할 때 하노이 탑의 구현을 생각해내기가 참 어려웠던 것 같습니다. 

많은 시행 착오를 통해 얻어낸 결론은 "경우의 수가 적을 때를 기준으로 알고리즘을 확실하게 짜 놓는다면 복잡한 순환 알고리즘을 수행해야 할 때에도 정상적으로 작동한다는 것이였습니다." 말이 조금 어렵지만 예제를 하나 씩 풀어가며 설명하겠습니다.

 

하노이 탑 문제는 하나의 막대에 놓여있는 원판들을 다른 하나의 막대로 옮기는 문제입니다. 이 때 절대 작은 원판 위에 큰 원판이 올라가서는 안되며 원판은 한 번에 한 개씩 옮길 수 있습니다. 막대는 총 세 개가 존재하며 세 막대를 오고가며 원판을 다른 막대로 옮겨 놓으면 문제는 해결됩니다. 

 

Hanoi Tower

 

이 문제는 원판의 개수가 많으면 많아질수록 점점 더 복잡해집니다. 함수의 실행 횟수가 $2^{n} -1 $이기 때문입니다. 원판의 개수, 즉 n 값을 크게 잡으면 잡을 수록 알고리즘을 구현하기 힘들기 때문에 저는 n이 2라고 생각하고 문제를 풀어보겠습니다. 

 

원판 두개를 옮기려면 

(i) A에서 B로 옮긴다

(ii) A 에서 C로 옮긴다

(iii) B에서 C로 옮긴다 

 

하노이 탑을 잘 보면 아시겠지만 가장 맨 밑에 있는 것은 항상 중간에 실행됩니다.

맨 밑 원판을 제외한 원판들을 B로 옮기고,

맨 밑 원판을 C로 옮기고,

다시 B에 있는 원판들을 C로 옮기는 과정이기 때문입니다. 

 

이제 코드를 작성해보겠습니다. 

void HanoiTower(int n, char start, char middle, char goal){
    if(n == 1)
        system.out.println(start + "를 " + goal + "로 옮긴다."); // 함수에서 두 번째 인자를 네 번째 인자로 옮긴다
    else {
        HanoiTower(n-1, start, goal, middle); // A를 B로 옮긴다
        system.out.println(start +"를 " + goal + "로 옮긴다."); // A를 C로 옮긴다
        HanoiTower(n-1, middle, start, goal); // B를 C로 옮긴다
    }
}

경우의 수가 가장 작을 때를 기준으로 탄탄하게 코드를 작성해 놓으면, n값이 증가해도 올바른 결과값이 도출됩니다. 

---

📌 연습문제