재귀 함수는 "함수 내부에서 자기 자신을 호출하는 함수"다. 이름 그대로 자기 자신을 반복적으로 호출하면서 특정 조건이 충족될 때 실행을 종료한다. 이러한 동작은 프로그래밍에서 반복적인 문제를 간결하게 해결하는 데 유용하게 쓰인다.
1. 재귀 함수의 동작 원리
재귀 함수는 호출될 때마다 함수의 인스턴스가 스택 메모리에 쌓인다. 이를 콜 스택(Call Stack)이라고도 부른다. 함수는 호출된 순서대로 스택에 쌓이고, 마지막에 호출된 함수부터 순차적으로 종료되면서 스택에서 제거된다. 이를 이해하기 위해 간단한 예제 코드를 보자.
재귀 함수 예제 코드
#include <stdio.h>
void recursive_function(int n) {
if (n == 0) return; // 종료 조건
printf("Entering: %d\n", n);
recursive_function(n - 1); // 재귀 호출
printf("Exiting: %d\n", n);
}
int main() {
recursive_function(3);
return 0;
}출력 결과
Entering: 3
Entering: 2
Entering: 1
Exiting: 1
Exiting: 2
Exiting: 3
위 코드에서 recursive_function(3)이 호출되면, 다음과 같은 순서로 동작한다:
- 스택에 쌓임: n=3 → n=2 → n=1 순서로 함수를 호출하며 스택에 추가된다.
- 스택에서 제거: 종료 조건(n==0)에 도달한 뒤, 호출된 순서의 역순으로 스택에서 제거된다.
이처럼 재귀 함수는 "끝까지 내려갔다가 돌아오는" 원리로 동작한다.
2. 재귀 함수로 거듭제곱 계산하기
거듭제곱 계산의 개념
위 규칙을 기반으로 재귀적으로 구현해 보자.
거듭제곱 예제 코드
#include <stdio.h>
// 재귀 함수로 거듭제곱 계산
int power(int x, int y) {
if (y == 0) return 1; // 종료 조건
return x * power(x, y - 1); // 재귀 호출
}
int main() {
int base = 2, exponent = 4;
printf("%d^%d = %d\n", base, exponent, power(base, exponent));
return 0;
}
출력 결과
2^4 = 163. 분할 정복
이 방식은 y를 절반씩 줄이기 때문에, 시간 복잡도가 O(log y)로 감소한다.
분할 정복 예제 코드
#include <stdio.h>
// 최적화된 거듭제곱 계산
int power_optimized(int x, int y) {
if (y == 0) return 1; // 종료 조건
int half = power_optimized(x, y / 2); // 재귀 호출로 분할
if (y % 2 == 0) {
return half * half; // 짝수일 때
} else {
return x * half * half; // 홀수일 때
}
}
int main() {
int base = 2, exponent = 10;
printf("%d^%d = %d\n", base, exponent, power_optimized(base, exponent));
return 0;
}출력 결과
2^10 = 1024시간 복잡도 분석
4. 최대공약수(GCD)와 유클리드 호제법
최대공약수(GCD, Greatest Common Divisor)는 두 수의 공통된 약수 중 가장 큰 값을 말한다. 예를 들어, 72와 30의 최대공약수는 2*3= 6이다.
1. 기본적인 최대공약수 계산법
최대공약수를 구하려면 두 수를 공통된 약수로 나눠 나머지가 0이 될 때까지 반복하면 된다. 예를 들어, 72와 30의 최대공약수를 아래와 같이 구할 수 있다.
따라서 최대공약수는 2×3=6 이다.
하지만 이 방식은 두 수가 크거나 공통 약수를 찾기 어려울 경우 비효율적이다. 이를 개선하기 위해 우리는 유클리드 호제법을 사용할 수 있다.
2. 유클리드 호제법의 원리
유클리드 호제법은 두 수의 최대공약수를 구할 때 나눗셈의 나머지를 활용하는 알고리즘이다. 원리는 다음과 같다.
이는 마치 두 수가 정사각형으로 이루어졌다고 생각하고, 더 큰 수를 긴변, 작은 수를 짧은 변으로 두고
두 수의 나머지가 0일 때까지 계속 쪼개는 것과 같다.
이를 일반화하면 다음과 같다.
x % y = r
y % r = r '
r % r' = r''
예시
72 % 30 = 12
30 % 12 = 6
12 % 6 = 0
첫 번째 연산 이후 y가 x의 자리로 들어가고 x % y 의 결과 값이 y 가 되는 식으로 나머지가 0이 될 때까지 연산이 반복된다. 이를 코드로 나타내면 다음과 같다.
유클리드 호제법 예제 코드
#include <stdio.h>
// 유클리드 호제법을 사용한 최대공약수 계산
int gcd(int x, int y) {
if (y == 0) return a; // 종료 조건: 나머지가 0이면 최대공약수 반환
return gcd(y, x % y); // 재귀 호출
}
int main() {
int x = 72, y = 30;
printf("GCD of %d and %d is %d\n", x, y, gcd(x, y));
return 0;
}
출력 결과
GCD of 72 and 30 is 6
유클리드 호제법은 매우 효율적인 알고리즘으로, 두 수의 크기 에 대해 시간 복잡도는 O(logn)이다.
이는 반복적으로 나눗셈을 수행하며 문제를 절반으로 줄이기 때문이다.
5. 반복문을 사용한 유클리드 호제법
재귀 호출 대신 반복문으로 구현하면 스택 메모리 사용을 줄일 수 있다.
#include <stdio.h>
// 반복문을 사용한 최대공약수 계산
int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
int main() {
int x = 72, y = 30;
printf("GCD of %d and %d is %d\n", a, b, gcd(x, y));
return 0;
}
출력 결과
GCD of 72 and 30 is 6
5. 재귀함수로 구현한 피보나치 수열
피보나치 수열은 첫 번째와 두 번째 항이 각각 1로 시작하며, 세 번째 항부터는 이전 두 항의 합으로 이루어지는 수열이다. 수열의 예는 다음과 같다.
1,1,2,3,5,8,13...
수학적으로는 다음과 같은 관계식을 따른다.
#include <stdio.h>
// 재귀 함수로 피보나치 수열 계산
int fibonacci(int n) {
if (n <= 2) return 1; // 종료 조건
return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 호출
}
int main() {
int n = 10; // 구하고자 하는 피보나치 수열의 항
printf("Fibonacci(%d): %d\n", n, fibonacci(n));
return 0;
}Fibonacci(10): 55
위 코드는 간단하지만, 시간이 지남에 따라 비효율적이다. 이유는 중복 계산 때문이다.
예를 들어, F(5) 계산하는 과정을 살펴보면 다음과 같다.
여기서 F(3)와 F(2)는 여러 번 반복적으로 계산된다. 이러한 중복 계산 때문에 시간 복잡도가 O(2^n)에 달하며, n이 커질수록 계산량이 급격히 증가한다.
6. 동적 계획법(Dynamic Programming)으로 이미 계산한 값 재사용하기
중복 계산 문제를 해결하려면, 이미 계산한 값을 저장하고 재사용하면 된다. 이를 메모이제이션(Memoization)이라 한다. 동적 계획법은 이런 저장과 재사용 개념을 기반으로 한다. 동적 계획법은 재귀 호출을 사용하지 않고, 반복문을 통해 아래에서 위로 값을 계산한다. (Bottom up)
#include <stdio.h>
#define MAX 100 // 최대 크기 설정
// 메모이제이션을 위한 배열 초기화
int memo[MAX] = {0};
// 동적 계획법으로 피보나치 수열 계산
int fibonacci_dp(int n) {
if (n <= 2) return 1; // 종료 조건
if (memo[n] != 0) return memo[n]; // 이미 계산된 값 사용
memo[n] = fibonacci_dp(n - 1) + fibonacci_dp(n - 2); // 계산 후 저장
return memo[n];
}
int main() {
int n = 10; // 구하고자 하는 피보나치 수열의 항
printf("Fibonacci(%d): %d\n", n, fibonacci_dp(n));
return 0;
}Fibonacci(10): 55
시간 복잡도
- 메모이제이션 덕분에 중복 계산이 제거되어 시간 복잡도가 O(n)으로 줄어든다.
- 이 방식은 효율적이며, nn이 커져도 적은 계산으로 결과를 구할 수 있다.
7. 반복문을 사용한 구현
재귀 함수 대신 반복문으로도 피보나치 수열을 구현할 수 있다. 반복문을 사용하면 함수 호출 스택을 사용하지 않으므로 메모리 사용량이 줄어든다.
#include <stdio.h>
// 반복문으로 피보나치 수열 계산
int fibonacci_iterative(int n) {
if (n <= 2) return 1; // 종료 조건
int prev1 = 1, prev2 = 1, result = 0;
for (int i = 3; i <= n; i++) {
result = prev1 + prev2;
prev1 = prev2;
prev2 = result;
}
return result;
}
int main() {
int n = 10; // 구하고자 하는 피보나치 수열의 항
printf("Fibonacci(%d): %d\n", n, fibonacci_iterative(n));
return 0;
}Fibonacci(10): 55
시간 복잡도
- 반복문 방식도 O(n)의 시간 복잡도를 가진다.
- 하지만 재귀 호출 없이 단순 반복을 사용하므로 스택 메모리를 절약할 수 있다.
8. 최적화된 반복문 구현
배열을 사용하지 않고, 이전 두 항의 값만 저장하여 공간 복잡도를 O(1)로 줄일 수 있다.
#include <stdio.h>
int fibonacci_optimized(int n) {
if (n <= 2) return 1; // 종료 조건
int prev1 = 1, prev2 = 1, current = 0;
for (int i = 3; i <= n; i++) {
current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
return current;
}
int main() {
int n = 10;
printf("Fibonacci(%d): %d\n", n, fibonacci_optimized(n));
return 0;
}특징
- 시간 복잡도: O(n), 반복문 사용.
- 공간 복잡도: O(1), 추가 메모리 사용 최소화.
요약 정리
- 재귀 호출은 간단한 구현이 필요할 때 적합하지만, 성능이 떨어진다.
- 메모이제이션은 재귀 호출의 직관성과 효율성을 결합한 방식이다.
- 동적 계획법(DP)은 반복문을 사용해 효율적이고 직관적으로 구현할 수 있다.
- 최적화된 반복문은 메모리 사용량을 줄이면서도 빠른 실행 속도를 제공한다.
'자료구조&알고리즘' 카테고리의 다른 글
| 연결리스트란? (1) | 2024.12.09 |
|---|---|
| 연결리스트와 배열의 비교 (0) | 2024.12.09 |
| 이중 연결 리스트(Doubly Linked List) (0) | 2024.10.06 |
| 알고리즘의 성능을 평가하는 빅오 표기법 (1) | 2024.10.06 |
| 단일 연결 리스트(Singly Linked List) (0) | 2024.10.05 |
