재귀 함수란 무엇인가?
재귀 함수(Recursive Function)란 함수 본문 내부에서 자기 자신을 다시 호출하는 함수를 의미합니다. 복잡한 문제를 동일한 구조의 더 작은 문제로 나누어 해결할 때 매우 유용하게 사용됩니다.
대표적인 예시: 팩토리얼 계산
가장 대표적인 재귀 함수의 예는 정수 N의 팩토리얼을 계산하는 fact() 함수입니다. 팩토리얼은 1부터 N까지 모든 자연수를 곱한 값입니다.
- 인자가 1 또는 0으로 전달되면 함수는 1을 반환합니다.
- 그 외의 경우에는
n * fact(n-1)을 반환하며, 이 과정은 n이 1이 될 때까지 반복됩니다.
예를 들어 5의 팩토리얼이 계산되는 과정은 다음과 같습니다.
fact(5) = 5 * fact(4)
= 5 * 4 * fact(3)
= 5 * 4 * 3 * fact(2)
= 5 * 4 * 3 * 2 * fact(1)
= 5 * 4 * 3 * 2 * 1
= 120
재귀 함수를 이용한 팩토리얼 계산 C 프로그램
다음은 재귀 함수를 사용하여 숫자를 처리하는 기본적인 C 프로그램 예제입니다.
#include<stdio.h>
main() {
int n, f;
int fact(int);
clrscr();
printf("enter a number");
scanf("%d", &n);
f = fact(n);
printf("factorial value = %d", f);
}
int fact(int n) {
int f;
if ((n == 1) || (n == 0))
return 1;
else
f = n * fact(n - 1);
return f;
}
실행 결과
Enter a number 5
Factorial value = 120
재귀 함수를 이용해 주어진 숫자를 뒤집는 C 프로그램
이번에는 재귀 함수를 활용하여 입력받은 숫자의 자릿수 순서를 거꾸로 뒤집는 프로그램을 살펴보겠습니다. 핵심 원리는 다음과 같습니다.
- 숫자를 10으로 나눈 나머지(
%10)를 구하면 가장 마지막 자릿수를 얻을 수 있습니다. - 기존 결과값에 10을 곱한 뒤 나머지를 더하면 자릿수가 한 칸씩 밀려나며 쌓입니다.
- 숫자를 10으로 나눈 몫(
/10)을 인자로 하여 함수를 재귀적으로 호출합니다. - 숫자가 0이 되면 재귀 호출을 멈추고 누적된 결과값을 반환합니다.
#include<stdio.h>
int sum = 0, rem;
int main() {
int num, revNum;
printf("enter number:\n");
scanf("%d", &num);
revNum = revNumFunction(num); // 입력받은 숫자를 뒤집는 함수 호출
printf("the number after reverse :%d", revNum);
return 0;
}
revNumFunction(int num) {
if (num) {
rem = num % 10;
sum = sum * 10 + rem;
revNumFunction(num / 10);
}
else
return sum;
}
실행 결과
enter number: 1357
the number after reverse is :7531
정리
재귀 함수는 자기 자신을 반복적으로 호출하며 문제를 단계적으로 축소해 나가는 강력한 프로그래밍 기법입니다. 위 예제에서 확인했듯이, 팩토리얼 계산뿐만 아니라 숫자 뒤집기와 같은 자릿수 조작 문제에서도 재귀 함수를 효과적으로 활용할 수 있습니다. 다만 재귀 호출이 깊어질 경우 스택 오버플로우가 발생할 수 있으므로 종료 조건(base case)을 명확히 설정하는 것이 중요합니다.