함수 기초(2): 재귀 함수
재귀 함수 (Recursive Function)
**Recursive Function(재귀 함수)**란 함수 내부에서 자기 자신을 다시 호출하는 함수를 말한다. 알고리즘 자체가 재귀적인 특성을 가질 때, Recursive Function을 사용하면 문제를 간결하고 쉽게 구현할 수 있다.
하지만 함수를 계속 호출하기 때문에 시간 및 메모리 공간(호출 스택)의 효율성이 떨어질 수 있다는 단점이 있다. 대부분의 Recursive Function은 반복문으로 변환이 가능하다.
모든 Recursive Function은 두 가지 필수 요소를 가진다.
- 종료 조건 (Base Case): 재귀 호출을 멈추는 조건이다. 종료 조건이 없으면 함수가 무한히 호출되어 스택 오버플로우가 발생한다.
- 재귀 호출 (Recursive Step): 자기 자신을 호출하는 부분으로, 문제를 더 작은 단위로 쪼개어 종료 조건에 점차 가까워지도록 설계해야 한다.
예시: 팩토리얼 (Factorial)
n! (n factorial)은 1×2×...×n으로 정의되며, 이는 재귀적 특성을 가진다.
- 종료 조건: n≤1일 때, n!=1이다.
- 재귀 호출: n>1일 때, n!=n×(n−1)!이다.
long factorial(int number) {
if (number <= 1)
return 1; // 종료 조건
else
return (number * factorial(number - 1)); // 재귀 호출
}
예시: 10진수를 2진수로 변환
임의의 10진수 n을 2진수로 변환하는 과정 또한 재귀적으로 표현할 수 있다.
- Logic: n을 2진수로 표현하려면, 먼저
n/2를 2진수로 표현한 뒤, 그 결과에n%2의 결과를 이어 붙이면 된다. - 종료 조건: n이 0 이하가 되면 재귀를 멈춘다.
void binary(int number) {
if (number > 0) {
binary(number / 2); // 재귀 호출을 먼저 하여 숫자의 앞부분부터 처리
printf("%d", number % 2); // 나머지를 출력하여 뒷자리를 완성
}
}
피보나치 수 (Fibonacci Numbers)
Fibonacci(피보나치) 수열은 앞의 두 수의 합이 다음 수가 되는 특징을 가진 수열이다 (0, 1, 1, 2, 3, 5, ...).
- 재귀적 정의: (단, n≥2)
- 종료 조건: ,
피보나치 수열 구현 방법
- 단순 재귀 구현: 정의를 그대로 코드로 옮긴 방식으로, 동일한 계산을 매우 비효율적으로 반복한다.
- 배열을 이용한 재귀 (메모이제이션): 계산된 값을 배열에 저장해두고, 동일한 값을 다시 계산할 필요가 생기면 저장된 값을 바로 반환하는 방식이다. 훨씬 효율적이다.
- 선형 알고리즘 (동적 계획법): 반복문을 사용하여 부터 까지 순차적으로 계산하여 배열에 저장하는 방식이다. **Dynamic Programming(동적 계획법)**의 기초적인 예이다.
- 배열 없는 선형 알고리즘: 단 3개의 변수만 사용하여 마지막 두 항의 값만 기억하면서 다음 항을 계산하는 가장 효율적인 방식이다.
다양한 재귀 함수 예제
최대공약수 (GCD)
두 수의 최대공약수는 **Euclidean Algorithm(유클리드 호제법)**을 이용하여 재귀적으로 쉽게 구할 수 있다.
- 원리: 두 수 large와 small의 최대공약수는 small과
large % small의 최대공약수와 같다. - 종료 조건:
small이 0이 되면,large가 최대공약수이다.
이진 탐색 (Binary Search)
정렬된 배열에서 특정 값을 찾는 효율적인 방법이다.
- Logic: 배열의 중간 값과 찾으려는 값을 비교하여, 탐색 범위를 절반으로 줄여나가는 과정을 재귀적으로 반복한다.
- 종료 조건: 탐색 범위가 더 이상 유효하지 않을 때(high < low) 종료된다.
난수 (Random Number)
**Random Number(난수)**는 임의의 수를 의미하며, C언어에서는 stdlib.h 헤더 파일에 포함된 함수를 통해 생성할 수 있다.
rand(): 0부터RAND_MAX(통상 32767) 사이의 정수 난수를 반환한다.srand(): 난수 발생을 위한 초기값, 즉 **seed(시드)**를 설정한다.
rand() 함수는 시드값이 동일하면 항상 같은 순서의 난수를 생성한다. 매번 다른 난수를 얻기 위해서는 프로그램 실행 시마다 다른 시드값을 주어야 하며, 보통 현재 시간을 시드값으로 사용하는 srand(time(NULL)) 방식을 사용한다(time() 함수는 time.h 헤더 파일에 포함되어 있다.).