6. 순환

잠깐동안 tistory를 또 작성하지 못했다. 오늘의 내용은 순환이다.

 

순환이란?

- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법이다.

- 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

 

예를 들어 정수의 팩토리얼은 다음과 같이 정의된다.

n! = 1 (n=0)

n! = n*(n-1)! (n>=1)

 

위의 정의에서 팩토리얼 n!을 정의하는데 다시 팩토리얼(n-1)!이 사용되었다. 이러한 정의를 순환적이라 한다.

 

위의 정의에 따라 n!를 구하는 함수 factorial을 제작해보자면,

int factorial(int n)
{
    if( n<= 1 ) return(1); //순환을 멈추는 부분
    else return (n * factorial(n-1) ); //순환 호출은 하는 부분
}

와 같다. 주의해야 할 점은 순환 호출을 멈추는 부분이 없다면 시스템 오류가 발생할 때까지 무한정 호출하게 된다.

 

순환을 이해하기 위해선 먼저 함수 호출의 과정을 살펴볼 필요가 있다.

프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다.

즉 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드라 한다.

이러한 준비가 끝나면 호출된 함수의 시작 위치로 점프하여 수행을 시작한다. 만약 호출된 함수가 자기 자신이면 자기 자신의 시작 위치로 점프하게 되는 것이다. 호출된 함수가 끝나게 되면 시스템 스택에서 복귀주소를 추출하여 호출한 함수로 되돌아가게 된다. 순환호출이 계속 중첩될수록 시스템 스택에는 활성레크드들이 쌓이게 된다.

 

사실 대부분의 순환은 반복으로 바꾸어 작성할 수 있다. 하지만 반복을 사용하게 되면 지나치게 복잡해지는 문제들도 존재한다. 이런 경우에는 순환이 좋은 해결책이 될 수 있다. 순환은 주어진 문제를 해결하기 위하여 자신을 다시 호출하여 작업을 수행하는 방식이다. 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

하지만 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서는 떨어진다. (물론 순환이 더 빠른 예제도 있음)

 

그렇다면 반복적인 작업을 하는 프로그램을 작성함에 있어 어떤 형태가 더 바람직할까?

정답은 없지만 보통 실행시간이 중요하지 않고 문제의 정의가 순환적으로 되어 있는 경우 순환으로 작성하는 것이 좋다.

결론은 상황에 맞게 잘 선택하는게 중요하다는 것이다.

 

순환의 강력함을 가장 잘 보여주는 예제가 바로 하노이 탑이다. 

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to) {
	if (n == 1) {
		printf("No.1 disk moves from %c to %c\n", from, to);
	}
	else {
		hanoi_tower(n - 1, from, to, tmp);
		printf("No.%d disk moves from %c to %c\n", n, from, to);
		hanoi_tower(n - 1, tmp, from, to);
	}
}
int main() {
	hanoi_tower(3,'A','B','C');
	return 0;
}

이해가 조금 어려울 수 있다. 각 과정별로 쉽게 정리해주신 분이 있어서 공유해본다.

[자료구조] C언어로 하노이 탑 만들기 (tistory.com)

[자료구조] C언어로 하노이 탑 만들기