Recursion (재귀) | KAITRUST AI 백과사전

📖 상세 설명

재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다. 복잡한 문제를 동일한 구조의 더 작은 하위 문제로 분해하여 해결하는 "분할 정복(Divide and Conquer)" 전략의 핵심입니다. 재귀적 사고는 프로그래밍에서 매우 강력한 도구이며, 많은 알고리즘과 자료구조가 재귀를 기반으로 설계되어 있습니다.

재귀 함수는 반드시 두 가지 요소를 포함해야 합니다. Base case(기저 조건)는 재귀 호출을 멈추는 종료 조건으로, 더 이상 분해할 수 없는 가장 단순한 경우입니다. Recursive case(재귀 조건)는 문제를 더 작은 하위 문제로 분해하고 자기 자신을 호출하는 부분입니다. Base case가 없거나 도달하지 못하면 무한 루프에 빠져 Stack Overflow가 발생합니다.

꼬리 재귀 최적화(Tail Call Optimization, TCO)는 재귀 호출이 함수의 마지막 동작일 때 컴파일러가 스택 프레임을 재사용하는 최적화 기법입니다. 일반 재귀에서는 호출마다 스택에 프레임이 쌓이지만, 꼬리 재귀는 이를 방지합니다. Scheme, Scala, Elixir 등의 언어는 TCO를 지원하지만, JavaScript(ES6 명세에 있으나 대부분의 엔진 미구현)와 Python은 지원하지 않아 깊은 재귀 시 주의가 필요합니다.

재귀는 실무에서 다양하게 활용됩니다. 트리 순회(전위, 중위, 후위 순회)는 재귀의 대표적 사례입니다. 분할 정복 알고리즘인 퀵소트, 병합정렬이 재귀를 사용하며, 백트래킹 문제(N-Queens, 미로 탐색)에서도 필수입니다. 파일 시스템의 디렉토리 탐색, JSON 객체 파싱, DOM 트리 순회 등 계층적 구조를 다룰 때 재귀가 코드를 훨씬 간결하게 만듭니다.

💻 코드 예제

// 1. 팩토리얼 (기본 재귀)
function factorial(n) {
    // Base case: 종료 조건
    if (n <= 1) return 1;

    // Recursive case: 자기 자신 호출
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)


// 2. 피보나치 (비효율적인 재귀)
function fibonacciSlow(n) {
    if (n <= 1) return n;
    return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
    // 문제: 동일한 계산이 반복됨 (지수적 시간복잡도)
}


// 3. 피보나치 (메모이제이션으로 최적화)
function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];  // 캐시된 결과 반환
    if (n <= 1) return n;

    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

console.log(fibonacciMemo(50)); // 12586269025 (빠르게 계산)


// 4. 꼬리 재귀 (Tail Recursion)
function factorialTail(n, acc = 1) {
    if (n <= 1) return acc;
    // 재귀 호출이 마지막 동작 (추가 연산 없음)
    return factorialTail(n - 1, n * acc);
}


// 5. 깊은 객체 탐색 (실무 활용)
function findValue(obj, targetKey) {
    for (const key in obj) {
        if (key === targetKey) return obj[key];

        if (typeof obj[key] === 'object' && obj[key] !== null) {
            const result = findValue(obj[key], targetKey);
            if (result !== undefined) return result;
        }
    }
    return undefined;
}

const data = {
    user: {
        profile: {
            name: '홍길동',
            contact: { email: 'hong@example.com' }
        }
    }
};

console.log(findValue(data, 'email')); // 'hong@example.com'

# 1. 팩토리얼
def factorial(n):
    if n <= 1:  # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # 120


# 2. 피보나치 (메모이제이션 with lru_cache)
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(50))  # 12586269025


# 3. 리스트 합계 (반복문 대신 재귀)
def sum_list(lst):
    if not lst:  # Base case: 빈 리스트
        return 0
    return lst[0] + sum_list(lst[1:])  # 첫 요소 + 나머지 합

print(sum_list([1, 2, 3, 4, 5]))  # 15


# 4. 디렉토리 내 모든 파일 찾기
import os

def find_files(directory, extension):
    files = []
    for item in os.listdir(directory):
        path = os.path.join(directory, item)
        if os.path.isdir(path):
            # 재귀: 하위 디렉토리 탐색
            files.extend(find_files(path, extension))
        elif item.endswith(extension):
            files.append(path)
    return files

# python_files = find_files('/project', '.py')


# 5. 재귀 깊이 제한 변경 (주의해서 사용)
import sys
print(sys.getrecursionlimit())  # 기본값: 1000
# sys.setrecursionlimit(3000)  # 필요시 증가


# 6. 반복문으로 변환 (Stack Overflow 방지)
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

// 이진 트리 노드 정의
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 트리 생성
//       1
//      / \
//     2   3
//    / \
//   4   5
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);


// 1. 전위 순회 (Pre-order): 루트 -> 왼쪽 -> 오른쪽
function preorder(node) {
    if (!node) return;
    console.log(node.val);    // 현재 노드 방문
    preorder(node.left);       // 왼쪽 서브트리
    preorder(node.right);      // 오른쪽 서브트리
}
preorder(root);  // 1, 2, 4, 5, 3


// 2. 중위 순회 (In-order): 왼쪽 -> 루트 -> 오른쪽
function inorder(node) {
    if (!node) return;
    inorder(node.left);
    console.log(node.val);
    inorder(node.right);
}
inorder(root);  // 4, 2, 5, 1, 3


// 3. 후위 순회 (Post-order): 왼쪽 -> 오른쪽 -> 루트
function postorder(node) {
    if (!node) return;
    postorder(node.left);
    postorder(node.right);
    console.log(node.val);
}
postorder(root);  // 4, 5, 2, 3, 1


// 4. 트리 최대 깊이 구하기
function maxDepth(node) {
    if (!node) return 0;  // Base case

    const leftDepth = maxDepth(node.left);
    const rightDepth = maxDepth(node.right);

    return Math.max(leftDepth, rightDepth) + 1;
}
console.log(maxDepth(root));  // 3


// 5. 트리 모든 노드 합계
function sumTree(node) {
    if (!node) return 0;
    return node.val + sumTree(node.left) + sumTree(node.right);
}
console.log(sumTree(root));  // 15 (1+2+3+4+5)


// 6. 경로 찾기 (루트에서 특정 값까지)
function findPath(node, target, path = []) {
    if (!node) return null;

    path.push(node.val);

    if (node.val === target) return path;

    const leftPath = findPath(node.left, target, [...path]);
    if (leftPath) return leftPath;

    const rightPath = findPath(node.right, target, [...path]);
    if (rightPath) return rightPath;

    return null;
}
console.log(findPath(root, 5));  // [1, 2, 5]

🗣️ 실무에서 이렇게 말하세요

💬 면접에서 (재귀 vs 반복문)

"재귀는 코드가 직관적이고 트리나 그래프 같은 계층 구조에 적합합니다. 하지만 호출마다 스택 프레임이 쌓여서 깊이가 깊으면 Stack Overflow가 발생합니다. 반복문은 스택을 사용하지 않아 메모리 효율이 좋지만, 복잡한 분기가 있으면 코드가 장황해집니다. 저는 트리 순회에는 재귀를, 단순 반복에는 for문을 사용합니다."

💬 코드 리뷰에서 (스택 오버플로우 방지)

"이 재귀 함수가 사용자 입력에 따라 깊이가 결정되네요. 최대 깊이를 예측할 수 없으면 반복문으로 바꾸거나, 명시적 스택을 사용하는 게 안전합니다. 또 피보나치처럼 중복 계산이 많은 경우 메모이제이션을 추가해서 시간복잡도를 O(2^n)에서 O(n)으로 줄이는 것도 고려해보세요."

💬 동료 설명할 때

"재귀 생각할 때는 '이 함수가 더 작은 문제를 이미 풀 수 있다고 가정'하고 시작하면 돼요. factorial(n-1)이 이미 (n-1)!을 반환한다고 믿고, 거기에 n을 곱하면 되는 거죠. Base case만 잘 정의하면 나머지는 자연스럽게 따라옵니다."

⚠️ 흔한 실수 & 주의사항

❌

Stack Overflow (스택 오버플로우)

재귀 깊이가 너무 깊으면 호출 스택이 가득 차서 프로그램이 중단됩니다. JavaScript는 수천 번, Python은 기본 1000번이 한계입니다. 깊이가 예측 불가능하거나 큰 경우, 반복문이나 꼬리 재귀(TCO 지원 언어), 명시적 스택으로 대체하세요.

❌

Base case 누락 또는 도달 불가

종료 조건이 없거나 잘못 설정하면 무한 재귀에 빠집니다. `if (n == 0)` 대신 `if (n <= 0)`처럼 엣지 케이스를 포함하세요. 재귀 함수를 작성할 때 항상 "어떻게 멈추는가?"를 먼저 정의하세요.

❌

중복 계산 (메모이제이션 미적용)

피보나치의 단순 재귀는 fib(5)를 계산할 때 fib(3)을 여러 번 계산합니다. 시간복잡도가 O(2^n)이 되어 n=40만 되어도 수 초가 걸립니다. 메모이제이션(결과 캐싱)으로 O(n)으로 개선하거나, 동적 프로그래밍의 bottom-up 방식을 사용하세요.

✅

재귀가 적합한 상황 판단

트리/그래프 탐색, 분할 정복(퀵소트, 병합정렬), 백트래킹(N-Queens), 계층적 데이터 처리에 재귀가 효과적입니다. 단순 반복 작업(배열 합계, 카운팅)에는 반복문이 더 효율적입니다. 문제의 특성에 맞는 도구를 선택하세요.

🔗 관련 용어

📚 더 배우기

📄 MDN 재귀 문서 (한국어) 🎨 VisuAlgo - 재귀 시각화 🎓 GeeksforGeeks - Recursion Tutorial