순환 알고리즘 (Recursion Algorithm)
순환(Recursion)은 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 방법입니다. 순환 알고리즘은 다른 말로 "재귀 알고리즘"이라고도 불립니다. 순환 알고리즘을 사용하면 순환이 진행될수록 문제의 크기가 작아지게 됩니다. 대표적인 예시로 "팩토리얼 정의"를 순환 알고리즘으로 나타낼 수 있습니다.
팩토리얼(Factorial, 계승)
팩토리얼은 다음과 같이 수학적으로 정의됩니다.
$$ n!=\begin{cases} 1 & n = 0 \\ n \times (n - 1)! & n \leq 1 \end{cases} $$
위 공식을 보아 알 수 있듯이 n이 0인 경우는 1로 정의되지만, n이 1보다 크거나 같은 경우에는 팩토리얼을 정의하기 위해 다시 팩토리얼이 사용되었습니다.
순환 알고리즘으로 팩토리얼을 구현한다면 이렇게 코드를 작성할 수 있습니다.
#include <stdio.h>
int Factorial(int n);
int main() {
printf("%d\n" Factorial(5));
return 1;
}
int Factorial(int n) {
if(n == 0) return 1;
else return n * Factorial(n - 1);
}
어딘가 이상해보이는 코드이지만 정상적으로 작동합니다. 이렇게 순환 알고리즘은 한 번에 문제를 해결하지는 못하지만 문제의 크기를 줄이며 점차적으로 해결해나갑니다. 이렇게 되풀이하는 작업은 순환 알고리즘을 통해서도 구현할 수 있지만 "반복"을 통해서도 구현이 가능합니다.
반복 알고리즘 (Loop Algorithm)
반복(Loop)은 for문이나 while문을 통해 반복구조를 만들어 되풀이하는 방법입니다. 반복적인 방법은 자신이 일정 횟수만큼 반복을 수행시킬 수도 있고 조건을 만족시킬 때까지 반복을 시킬 수도 있습니다. 반복과 순환은 문제 해결 능력이 같으며 상황에 따라 더 알맞은 알고리즘을 사용하여 구현하면 됩니다. 순환 알고리즘 중 순환 호출이 끝에서 일어나는 "꼬리 순환(Tail Recursion)"의 경우 반복 알고리즘으로 바꾸어 사용하기 쉽습니다.
반복 알고리즘으로 팩토리얼을 구현하면 다음과 같습니다.
#include <stdio.h>
int main() {
int n;
int i , result = 1;
printf("팩토리얼 계산할 숫자를 입력하세요. -> ");
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
result = result * i;
}
printf("팩토리얼 계산 결과는 %d입니다. \n", result);
return 1;
}순환 알고리즘 & 반복 알고리즘 비교
순환 알고리즘과 반복 알고리즘은 필요한 경우 더 적절한 방식으로 사용하면 됩니다. 아까 말했듯이 같은 문제 해결 능력을 가지고 있기 때문입니다. 순환 알고리즘과 반복 알고리즘의 시간 복잡도는 둘 다 \( O(n) \)입니다. 그러나 일반적으로 순환 알고리즘은 함수 호출을 하게 되므로 반복 알고리즘에 비해 수행 속도는 떨어집니다. 또한 함수 호출이 일어날 때 함수의 상태를 기억해야 하기에 기억 공간도 순환 알고리즘이 더 사용하게 됩니다. 그렇지만 순환 알고리즘은 조금 더 직관적으로 이해하기 쉬운 코드 작성이 가능하다는 장점이 있습니다. 또한 순환 방법이 더 빠른 문제도 있기에 순환 알고리즘을 사용하는 경우도 많습니다
댓글