순환이란

1. 순환의 개념

 함수는 자기 자신을 호출할 수도 있다. 이것을 순환이라고 부른다. 순환은 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 이것은 처음에는 상당히 이상하게 보이지만 사실 순환은 가장 흥미롭고 또 효과적인 프레임 워크를 제공한다. 즉 위의 정의에서 팩토리얼을 정의하는데 다시 팩토리얼이 사용되었다. 이러한 정의를 순환적이라고 한다.

 

2. 순환 함수의 구조

 순환 알고리즘은 자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있다. 만약 순환 호출을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출되다가 결국 에러를 내면서 멈출 것이다.

 

3. 피보나치 수열의 계산 

보통 순환을 사용하게 되면 보통 단순하게 작성할 수 있으며 가독성이 높아진다. 그러나 똑같은 계산을 몇 번씩 반복한다면 아주 단순한 경우라 할지라도 계산 시간이 엄청나게 길어질 수 있다. 이러한 예로 순환 호출을 이용하여 피보나치 수열을 계산해 보자. 피보나치 수열이란 다음과 같이 정의되는 수열이다. 즉 일반적일 때, 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만들면 된다. 피보나치 수열은 정의 자체가 순환적으로 되어 있다. 따라서 구현 시에 순환 호출을 사용하는 것이 자연스러운 방법이다. 

 

앞의 함수는 매우 단순하고 이해하기 쉽지만, 매우 비효율적이다. 예를 들어 fib으로 호출하였을 경우 fib이 두 번이나 계산되기 때문이다. fib은 3번 계산되고 이런 현상은 순환 호출이 깊어질수록 점점 심해진다. 따라서 상당히 비효율적임을 알 수 있다. 근본적인 이유는 중간에 계산되었던 값을 기억하지 않고 다시 계산하기 때문이다. 그렇다면 피보나치 수열을 계산하는데 다른 방법이 있을까? 이 경우에는 순환을 사용하지 않고 반복 구조를 이용하여 프로그램하면 제일 좋은 결과를 얻을 수 있다. 

 

4. 하노이 탑 문제 

순환의 파워를 가장 극명하게 보여주는 예제가 바로 하노이 탑 문제이다. 하노이 탑 문제는 다음과 같다. 고대 인도의 베나레스에는 세계의 중심이 있고, 그곳에는 아주 큰 사원이 있다. 이 사원에는 높이 50cm 정도 되는 다이아몬드 막대 3개가 있다. 그중 한 막대에는 천지 창조 때에 신이 구멍이 뚫린 64장의 순금으로 된 원판을 크기가 큰 것부터 아래에 놓이도록 하면서 차례로 쌓아 놓았다. 그리고 신은 승려들에게 밤낮으로 쉬지 않고 한 장씩 원판을 옮기어 빈 다이아몬드 막대 중 어느 한 곳으로 모두 옮겨 놓도록 명령하였다. 원판은 한 번에 한 개씩 옮겨야 하고, 절대로 작은 원판 위에 큰 원판을 올려놓을 수 없고 64개의 원판의 크기는 모두 다르다. 단, 원판의 이동 횟수는 최소로 한다. 고대 인도의 이 전설의 탑을 '하노이 탑'이라고 부른다. 주어진 문제를 이해하기 위하여 원판의 개수가 3개인 경우를 살펴보자.