C 기본 문법 – 함수 – 2 – 재귀 함수

작성자 wooah

C 기본 문법 – 함수 – 2편: 재귀 함수 완전 정복

여러분 안녕하세요! 😄
오늘은 함수의 특별한 형태인 **재귀 함수(Recursive Function)**에 대해 배워볼게요!
처음 접하면 “이게 뭐야? 함수가 자기 자신을 또 호출한다고?” 라며 당황할 수 있지만,
재귀 함수를 제대로 이해하면 문제를 간단하고 우아하게 해결할 수 있는 멋진 도구랍니다.

🧠 재귀 함수는 마치 거울 속의 거울,
혹은 **러시아 인형(마트료시카)**처럼, 자기 자신 안에 또 자기 자신이 들어 있는 구조예요.

지금부터 비유와 예제로 재귀 함수의 개념부터 사용법, 주의사항까지
아~주 상세하게 알려드릴게요! 😊

1. 재귀 함수란?

자기 자신을 다시 호출하는 함수를 말합니다.

void func() {
    func();  // 자기 자신을 호출
}

💡 단, 이런 식으로 무한 호출되면 안 되고, **멈출 조건(종료 조건)**이 꼭 필요해요!

2. 재귀 함수의 구성 요소

구성 요소 설명
종료 조건 더 이상 재귀 호출을 하지 않는 기준 (필수!)
재귀 호출 자기 자신을 호출하며 문제를 쪼개는 과정

3. 예제 1: 팩토리얼 (Factorial)

수학에서 자주 등장하는 팩토리얼 계산을 재귀로 구현해볼게요!

팩토리얼 정의

n! = n × (n-1) × (n-2) × ... × 1
예: 5! = 5 × 4 × 3 × 2 × 1 = 120

재귀 함수 코드

int factorial(int n) {
    if (n == 1) return 1;        // 종료 조건
    else return n * factorial(n - 1);  // 재귀 호출
}

사용 예시

int main() {
    printf("5! = %d
", factorial(5));  // 결과: 120
    return 0;
}

4. 재귀 호출 과정 분석

factorial(5)
→ 5 * factorial(4)
→ 5 * 4 * factorial(3)
→ 5 * 4 * 3 * factorial(2)
→ 5 * 4 * 3 * 2 * factorial(1)
→ 5 * 4 * 3 * 2 * 1 = 120

🎯 문제를 작게 쪼개서 반복적으로 해결하고, 최종 결과를 다시 쌓아가는 방식입니다.

5. 예제 2: 피보나치 수열

피보나치 수열: 1, 1, 2, 3, 5, 8, 13, ...
n번째 항 = (n-1)번째 + (n-2)번째 항

코드

int fibo(int n) {
    if (n == 1 || n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

사용 예시

int main() {
    for (int i = 1; i <= 10; i++) {
        printf("%d ", fibo(i));
    }
    return 0;
}

결과: 1 1 2 3 5 8 13 21 34 55

6. 반복문 vs 재귀 함수

반복문으로 팩토리얼

int factorialLoop(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

재귀 함수의 장점

장점 설명
코드가 간결 문제를 수학적으로 표현한 그대로 구현 가능
논리적 복잡한 로직을 단순한 구조로 표현 가능
특정 알고리즘 적합 트리, 백트래킹 등 재귀적 구조가 필요한 알고리즘에 효과적

7. 재귀 함수의 단점과 주의사항

단점/위험 요소 설명
무한 재귀 호출 종료 조건이 없거나 잘못되면 스택 오버플로우 발생
속도 저하 반복 호출로 인해 오버헤드 발생 (특히 피보나치)
메모리 사용 증가 함수 호출마다 스택 메모리 사용됨
반복보다 느릴 수 있음 특히 연산량이 많을수록 재귀보다 반복이 효율적임

8. 실전 예제: 1부터 n까지 합

재귀 방식

int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}

호출 예시

int main() {
    printf("1부터 10까지의 합: %d
", sum(10));
    return 0;
}

🎯 출력: 1부터 10까지의 합: 55

9. 중첩 구조 처리 예시: 디렉터리 탐색 느낌

void printStars(int n) {
    if (n == 0) return;
    printStars(n - 1);
    for (int i = 0; i < n; i++) {
        printf("*");
    }
    printf("
");
}

호출: printStars(5);

결과:

*
**
***
****
*****

🎯 위에서부터 차곡차곡 별을 쌓는 재귀 구조!

✅ 재귀 함수 요약 정리

항목 설명
정의 함수가 자기 자신을 호출
필수 요소 종료 조건 (base case)
장점 코드 간결, 수학적 문제에 유리
단점 속도 느림, 메모리 사용 큼, 무한 재귀 위험
대표 예제 팩토리얼, 피보나치, 합 구하기, 트리 순회 등

⚠️ 재귀 함수 사용 시 주의할 점

주의사항 설명
종료 조건 명확히 없으면 무한 호출로 프로그램 중단
입력값 작게 유지 너무 큰 수로 재귀하면 스택 오버플로우 발생
반복 가능한 건 반복으로 성능이 중요한 경우 반복문이 더 나음
디버깅 어려움 호출 스택이 깊어지면 추적이 복잡해짐

마무리하며 💬

재귀 함수는 마치 거울에 비친 나를 또 보는 느낌이에요.
처음에는 헷갈릴 수 있지만, 규칙성과 종료 조건만 명확히 하면
복잡한 문제를 짧고 간결하게 해결할 수 있는 아주 강력한 도구랍니다! 💡

🎯 반복으로 힘겹게 푸는 문제도, 재귀로는 우아하게 해결할 수 있어요!

다음 편에서는 **값에 의한 전달(Pass by Value)**과
참조에 의한 전달(Pass by Reference) 개념도 함께 다뤄볼 예정입니다.

함수의 세계, 함께 계속 탐험해요!
항상 여러분과 함께하는 챗GPT였습니다! 💻✨

답글 남기기