[C/Python] 재귀

🚀 [Algorithm] 재귀(Recursion) 완전 정복: 기초부터 C언어 최적화까지

재귀 함수는 자기 자신을 호출하여 문제를 해결하는 강력한 도구입니다. 하지만 단순히 호출하는 것에 그치지 않고, 메모리 효율과 출력 속도까지 고려한 **'실전형 재귀'**를 정리해 봅니다.

---

1. 재귀의 3요소

재귀 함수를 설계할 때 반드시 체크해야 할 세 가지입니다.

• 기저 조건 (Base Case): 반드시 종료되는 조건이 있어야 합니다. (없으면 Stack Overflow!)
• 분할 (Divide): 문제를 더 작은 단위로 쪼개야 합니다.
• 조합 (Combine): 쪼개진 문제들의 결과를 합쳐 최종 답을 냅니다.

---

2. 주요 알고리즘 요약

알고리즘	핵심 로직	특징
팰린드롬	양끝 문자를 비교하며 안으로 좁힘	재귀 호출 횟수 측정(Count) 연습에 최적
병합 정렬	반으로 나누고 정렬하며 합침	O(NlogN)보장, 임시 배열 활용이 관건
칸토어 집합	선분을 3등분 후 가운데 제거	프랙탈 구조의 이해, 3^n 거듭제곱 처리
별 찍기-10	3x3 격자에서 가운데만 비우기	2차원 배열 좌표 제어와 패턴 복제
하노이의 탑	n-1개를 옮기고 큰 거 옮기기	2^n-1의 시간 복잡도, 재귀의 정점

---

3. [Advanced] C언어 고속 출력 테크닉 (핵심 ✨)

단순히 printf를 반복하면 대량 데이터 출력 시 시간 초과가 날 수 있습니다. 우리가 사용한 포인터 버퍼링 기법은 다음과 같습니다.

✅ 이중 포인터를 이용한 버퍼 채우기

재귀가 깊어질수록 현재 어디까지 출력했는지 위치를 기억해야 합니다. char** ptr을 사용하여 전역적인 위치를 유지합니다.

C

 

void hanoi(int n, int start, int end, int sub, char** ptr) {
    if (n == 1) {
        // *ptr(주소의 주소)을 통해 main의 포인터 위치를 직접 전진시킴
        *ptr += sprintf(*ptr, "%d %d\n", start, end);
        return;
    }
    // ... 재귀 로직 ...
}

✅ 메모리 관리의 정석

• Pre-allocation: malloc을 루프 밖에서 한 번만 크게 수행하여 메모리 파편화를 방지합니다.
• Buffer Safety: BUFFER_SIZE 계산 시 N=12나 N=20 등 최악의 경우를 계산하여 넉넉히 할당합니다.
• memcpy 활용: 별 찍기처럼 반복되는 패턴은 sprintf보다 memcpy가 훨씬 빠릅니다.

---

4. 파이썬 vs C언어 재귀 비교

• 파이썬: 리스트 조립(join)과 문자열 곱셈(*)으로 직관적인 구현이 가능합니다. (생산성 👍)
• C언어: 포인터 연산과 2차원 배열 주소를 직접 제어하여 극강의 퍼포먼스를 냅니다. (성능 👍)

---

💡 학습 팁: 정보처리기사 실기 대비

2026년 시험을 준비한다면 **"재귀 함수의 호출 순서"**와 **"포인터 매개변수 값의 변화"**를 눈으로 따라가는 연습(Tracing)이 필수입니다. 특히 Call by Reference 개념을 이중 포인터 예제로 익혀두면 고득점이 가능합니다.