순환(Recursion)

순환 알고리즘

Factorial 계산

수열의 합

거듭제곱 계산

하노이 탑

순열 나열하기

피보나치 수열

순환 알고리즘

여러 개의 함수로 구성된 프로그램에서 함수는 다른 함수를 호출할 수 있다. 때로는 함수가 자기 자신을 호출하기도 하는데 이것을 순환 호출이라고 부른다. 함수가 다른 함수를 부르고, 그 함수가 다시 처음 호출한 함수를 부를 수도 있다. 이것도 역시 순환 호출의 일종으로 간접 순환 호출이라고 한다.

순환 호출을 이용하여 주어진 문제보다 □크기가 작은 문제□를 풀어서 원래 문제를 해결하는 방식으로 알고리즘을 설계할 수 있다.

순환 호출에서 종료 조건은 반드시 필요하다. 호출을 무한정 계속 반복할 수는 없기 때문이다. 순환 호출을 사용하여 프로그래밍할 때 이 점을 실수하기 쉬우므로 주의하여야 한다.

또 하나 주의할 것은 크기가 더 큰 문제로 순환 호출을 하여서는 안 된다는 것이다. 더 큰 문제로 순환 호출을 하면 호출이 무한히 반복될 것이다.

Factorial 계산

양의 정수 [eqn: n]에 대해서 [eqn: n!]을 계산하라는 문제이다. [eqn: n! = 1*2* cdots * n]이라고 생각할 수 있지만, [eqn: n! = n * (n-1)!]이라고 생각할 수 있다. [eqn: n!]을 계산할 때 먼저 크기가 작은 문제인 [eqn: (n-1)!]을 순환 호출을 이용하여 풀고 그 값에 [eqn: n]을 곱하면 된다. [eqn: n]이 [eqn: 1]일 때는 위 식으로 계산할 수 없으므로 [eqn: 1]을 복귀시킨다. 이것이 종료 조건이다.

unsigned long Factorial(unsigned n)

{

if (n == 1) return 1;

else return n * Factorial(n-1);

}

[eqn: n! = (n+1)!/(n+1)]이라는 점에 착안하여 다음과 같이 알고리즘을 작성하였다. 이 알고리즘에서 잘못된 점은 무엇일까?

unsigned long Factorial(unsigned n)

{

if (n == 1) return 1;

else return Factorial(n+1) / (n+1);

}

수열의 합

정수로 구성된 수열 [eqn: a_0 , a_1 , cdots , a_n-1]의 원소의 합 [eqn: sum_{0 le i le n-1} a_i]을 구하는 문제이다. 수열은 배열 A[n]으로 표현되어 있다. 배열의 합 [eqn: sum_{0 le i le n-1} a_i]를 순환적 방식으로 생각하여 보자.

·[eqn: sum_{0 le i le n-1} a_i = sum_{0 le i le n-2} a_i \\ + \\ a_n-1]

·[eqn: sum_{0 le i le n-1} a_i = a_0 \\ + \\ sum_{1 le i le n-1} a_i]

·[eqn: sum_{0 le i le n-1} a_i = sum_{0 le i le lfloor{(n-1)/2}RFLOOR } a_i \\ + \\ sum_{LFLOOR{(n-1)/2}RFLOOR +1 le i le n-1} a_i]

첫 번째 방식으로 알고리즘을 작성하여 보자. 배열 A[n]의 합을 계산하는 함수를 작성한다. SeqSum(A,0,n-1)을 호출함으로써 A[n]의 합을 구할 수 있다. [eqn: i le j]라고 가정한다.

unsigned long SeqSum(int A[], unsigned i, unsigned j)

{

if (i == j) return A[i];

else return SeqSum(A,i,j-1) + A[j];

}

수열의 합 (계속)

두 번째 방식은 첫 번째 방식과 거의 유사하다.

unsigned long SeqSum(int A[], unsigned i, unsigned j)

{

if (i == j) return A[i];

else return A[i] + SeqSum(A,i+1,j);

}

마지막 방식은 앞의 두 방식과는 달리 원래 문제의 입력을 크기가 거의 같도록 나눈다. 이 경우도 어렵지 않게 알고리즘을 만들 수 있다.

unsigned long SeqSum(int A[], unsigned i, unsigned j)

{

unsigned k;

if (i == j) return A[i];

else {

k = (i + j) / 2;

return SeqSum(A,i,k) + SeqSum(A,k+1,j);

}

}

위의 알고리즘에서 [eqn: k = lceil (i+j)/2 rceil]라고 두면 잘 동작하지 않는다. 왜 그럴까?

거듭제곱 계산

실수 [eqn: x]와 양의 정수 [eqn: n]이 주어져 있을 때 [eqn: x^n]을 구하는 문제이다. 순환적 방식으로 접근하여 보기로 하자.

· [eqn: x^n = x * x^{n-1}]

· [eqn: n]이 짝수이면 [eqn: x^n = x^{lfloor n/2 rfloor}*x^{lfloor n/2 rfloor}]이고

[eqn: n]이 홀수이면 [eqn: x^n = x^{lfloor n/2 rfloor}*x^{lfloor n/2 rfloor}*x]이다.

두 번째 방식으로 [eqn: x^{100}]을 구하는 예를 들어보자.

[eqn: x^{100} = x^{50} * x^{50}]

[eqn: x^{50} = x^{25}*x^{25}]

[eqn: x^{25} = x^{12}*x^{12}*x]

[eqn: x^{12} = x^{6}*x^{6}]

[eqn: x^{6} = x^{3}*x^{3}]

[eqn: x^{3} = x^{1}*x^{1}*x]

첫 번째 방식으로 [eqn: x^{100}]을 구하려면 100회 혹은 99회 곱셈을 하여야 할 것이다. 그러나 두 번째의 경우는 위에서 보는 바와 같이 [eqn: x^{100}]을 구하는데 곱셈의 횟수가 8회이면 충분하다. 두 번째 방식이 첫 번째 방식보다 곱셈의 횟수가 훨씬 작다.

거듭제곱 계산 (계속)

앞에서 관찰한 것을 토대로 순환 알고리즘을 설계하여 보자. 종료 조건은 [eqn: n = 1]일 때이고 이 경우는 순환 호출을 하지 않고

그냥 [eqn: x] 값을 복귀시킨다. even(n)은 n이 짝수이면 TRUE를 돌려주는 함수나 마크로라고 가정한다.

long double Power(float x, unsigned n)

{

if (n == 1) return x;

else return x * Power(x,n-1);

}

long double Power(float x, unsigned n)

{

long double y;

if (n == 1) return x;

else {

y = Power(x,n/2);

if (even(n)) return y * y;

else return y * y * x;

}

}

위의 두 알고리즘의 시간복잡도는 각각 [eqn: O(n)], [eqn: O(log n)]으로 두 번째 것이 더 효율적이다. 시간복잡도에 대해서는 다음에 배우게 되므로 걱정하지 않아도 된다.

하노이 탑

크기가 다른 [eqn: n]개의 디스크가 [eqn: 1]번 말뚝에 놓여 있다. 이 디스크를 모두 [eqn: 3]번 말뚝으로 옮기는 문제이다. 맨 위에 놓여 있는 디스크를 한 개씩 다른 말뚝으로 옮길 수 있으며 큰 디스크를 작은 디스크 위에 놓아서는 안 된다. 디스크의 크기를 순서대로 [eqn: 1, \ 2, \ 3, \ cdots , \ n]이라고 하자.

|                |                |

|                |                |

[=1=]              |                |

[==2==]             |                |

[===3===]            |                |

[====4====]           |                |

-------------    -------------     -------------

말뚝 1          말뚝 2          말뚝 3

위의 그림과 같이 디스크 [eqn: 4]개가 [eqn: 1]번 말뚝에 있다면 어떻게 [eqn: 3]번 말뚝으로 디스크를 모두 옮길 수 있을까? 이 때 필요한 최소의 디스크 이동 횟수는 얼마일까?

하노이 탑 (계속)

말뚝 [eqn: 1]에서 [eqn: 3]으로 디스크를 [eqn: n]개 옮기고자 한다. 언젠가는 제일 큰 디스크를 말뚝 [eqn: 3]으로 이동하여야 할 것이고, 바로 이 때 말뚝 [eqn: 1]에는 제일 큰 디스크 한 개만이 있고 말뚝 [eqn: 3]에는 아무 것도 없다. 그리고 나머지 디스크는 모두 말뚝 [eqn: 2]에 있다.

제일 큰 디스크를 옮기기 위해서는 먼저 이 보다 작은 [eqn: n-1]개의 디스크를 모두 임시로 다른 말뚝에 옮겨 놓아야 한다. 그 다음에 제일 큰 디스크를 옮기면 된다. 이제 남은 것은 임시로 옮겨 놓은 [eqn: n-1]개의 디스크를 목적지에 옮기면 된다.

하노이 탑 (계속)

이 문제에 대한 알고리즘은 순환 호출을 이용하면 어렵지 않게 설계할 수 있다. 말뚝 [eqn: 1]에서 [eqn: 3]으로 디스크 [eqn: n]개를 옮기고자 할 때는 HanoiTower(1,3,n)을 호출한다.

알고리즘에서 말뚝을 나타내기 위해서 사용하는 변수인 FromPeg과 ToPeg은 [eqn: LEFT { 1, \ 2, \ 3 RIGHT }]에서 서로 다른 값을 가지며 이것과 다른 것이 AuxPeg의 값이다.

void Hanoi(unsigned FromPeg, unsigned ToPeg, unsigned n)

{

unsigned AuxPeg;

if (n == 1)

FromPeg에서 ToPeg으로 맨 위의 디스크를 옮긴다;

else {

AuxPeg = 6 - FromPeg - ToPeg;

Hanoi(FromPeg,AuxPeg,n-1);

FromPeg에서 ToPeg으로 맨 위의 디스크를 옮긴다.

Hanoi(AuxPeg,ToPeg,n-1);

}

}

순열 나열하기

[eqn: n]개의 원소를 가진 집합에서 모든 가능한 순열을 출력하라는 문제이다. 물론 출력해야 할 순열의 개수는 [eqn: n!]이다. 예를 들어 집합이 [eqn: LEFT { a, b, c RIGHT }]라면 출력해야 할 순열은 다음과 같다.

[eqn: abc, acb, bac, bca, cab, cba]

집합 [eqn: LEFT { a, b, c, d RIGHT }]에 대한 순열은 다음과 같은 방식으로 모두 나열할 수 있다.

· [eqn: a]를 출력하고 그 뒤에 [eqn: LEFT { b, c, d RIGHT }]의 순열을 모두 나열한다.

· [eqn: b]를 출력하고 그 뒤에 [eqn: LEFT { a, c, d RIGHT }]의 순열을 모두 나열한다.

· [eqn: c]를 출력하고 그 뒤에 [eqn: LEFT { a, b, d RIGHT }]의 순열을 모두 나열한다.

· [eqn: d]를 출력하고 그 뒤에 [eqn: LEFT { a, b, c RIGHT }]의 순열을 모두 나열한다.

원소 [eqn: n]개에 대한 순열은 원소 [eqn: n-1]개에 대한 순열을 이용하여 구할 수 있음을 보여주고 있다. 이제 관찰한 사실을 이용하여 순환 알고리즘을 개발하여 보자.

순열 나열하기 (계속)

집합의 원소가 배열 A[n]에 저장되어 있다고 가정한다. GeneratePerm(A,0,n)을 호출하면 모든 순열을 구할 수 있다. swap()은 두 원소를 서로 바꾸는 함수이다.

void GeneratePerm(char A[], unsigned k, unsigned n)

{

unsigned i;

if (k == n-1) {

for (i=0; i<n; i++)

printf("%c", A[i]);

printf("\n");

}

else {

for (i=k; i<n; i++) {

swap(A[i],A[k]);

GeneratePerm(A,k+1,n);

swap(A[i],A[k]);

}

}

}

위의 알고리즘이 옳게 동작한다는 확신을 가질 때까지 원소의 개수가 [eqn: 1, \ 2, \ 3, \ 4]인 예를 만들어서 알고리즘을 실행시켜 보아라.

피보나치 수열

피보나치 수열은 다음과 같이 정의된다.

[eqn: F_0 = 0]; [eqn: F_1 = 1]; [eqn: F_n = F_{n-1} + F_{n-2}], [eqn: n geq 2]

즉 피보나치 수열은 [eqn: 0, \ 1, \ 1, \ 2, \ 3, \ 5, \ 8, \ 13, \ cdots \]이다. 문제는 [eqn: n]이 주어졌을 때 [eqn: n]번째 피보나치 수 [eqn: F_n]을 구하라는 것이다.

피보나치 수열의 정의 자체가 순환적이므로 쉽게 순환 알고리즘을 설계할 수 있다.

unsigned long FibonacciNum(unsigned n)

{

if (n == 0) return 0;

else if (n == 1) return 1;

else return FibonacciNum(n-1) + FibonacciNum(n-2);

}

이 알고리즘이 옳게 동작한다는 것은 쉽게 알 수 있다. 이 알고리즘은 만족할 만큼 효율적인가?

피보나치 수열 (계속)

[eqn: F_5]는 어떻게 계산하는지 알고리즘을 따라가 보자. [eqn: F_5]를 계산하는데 다음과 같이 덧셈을 [eqn: 7]회 수행하게 된다.

[eqn: F_5 = F_4 + F_3]

[eqn: = \{ F_3 + F_2 \} + \{ F_2 + F_1 \}]

[eqn: = \{ [ F_2 + F_1 ] + [ F_1 + F_0 ] \} + \{ [ F_1 + F_0 ] + F_1 \}]

[eqn: = \{ [ ( F_1 + F_0 ) + F_1 ] + [ F_1 + F_0 ] \} + \{ [ F_1 + F_0 ] + F_1 \}]

[eqn: F_0], [eqn: F_1]은 덧셈을 하지 않아도 알 수 있고 덧셈 한번에 [eqn: F_2], [eqn: 2]회에 [eqn: F_3]을 계산할 수 있으므로 [eqn: F_5]는 덧셈 [eqn: 4]회만 수행하면 충분하다. 왜 이렇게 많은 덧셈을 하게 되었을까?

위의 식을 다시 한번 자세히 살펴보자. [eqn: F_5]를 계산하는데 [eqn: F_4]와 [eqn: F_3] 값을 알아야 한다. [eqn: F_4]를 구하기 위해서 또 [eqn: F_3]가 필요한데, 한번 계산한 결과를 이용하지 않고 중복해서 계산을 하고 있다.

실제 [eqn: n]이 커지면 덧셈의 수는 기하급수적으로 늘어난다. 덧셈의 횟수는 [eqn: F_{n+1}-1]로 약 [eqn: {1} over {sqrt{5}} LEFT ( {1+sqrt{5}} over {2} RIGHT ) ^{n+1} - 1]이다. 믿어지지 않는 사람은 수학적 귀납법으로 증명하여 보라.

피보나치 수열 (계속)

이 문제와 같은 경우는 순환적 방식보다는 반복적 방식으로 알고리즘을 설계하면 효율적인 알고리즘을 얻을 수 있다.

unsigned long FibonacciNum(unsigned n)

{

unsigned long Low, Hi, temp;

unsigned i;

if (n == 0) return 0;

else if (n == 1) return 1;

else {

Low = 0;

Hi = 1;

for (i=2; i<=n; i++) {

Temp = Low;

Low = Hi;

Hi = Temp + Low;

}

return Hi;

}

}

위의 알고리즘은 옳다는 것을 어떻게 보일 수 있을까?