재귀와 분할 정복 — 큰 문제를 작게 쪼개는 사고법

// 팩토리얼: n! = n × (n-1)!
public static int factorial(int n) {
    if (n <= 1) return 1;        // 기저 조건(Base Case)
    return n * factorial(n - 1); // 재귀 호출
}

factorial(4) 호출 시 콜 스택:

| factorial(1) |  ← 기저 조건, 반환 시작
| factorial(2) |
| factorial(3) |
| factorial(4) |
|    main()    |

// 이러면 터집니다
public static void infiniteRecursion(int n) {
    infiniteRecursion(n + 1); // 기저 조건이 없음!
}

java -Xss4m MyProgram  # 스택 크기를 4MB로 설정

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return; // 기저 조건: 원소가 1개 이하

    int mid = left + (right - left) / 2;

    // 분할 + 정복
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // 결합
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    // 두 부분 배열을 비교하며 병합
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 남은 원소 복사
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    // 원래 배열에 복사
    System.arraycopy(temp, 0, arr, left, temp.length);
}

T(n) = aT(n/b) + O(n^d)

a: 하위 문제의 개수
b: 문제를 나누는 비율
d: 결합 단계의 복잡도 지수

// 빠른 거듭제곱: O(log n)
public static long power(long base, long exp, long mod) {
    if (exp == 0) return 1;

    long half = power(base, exp / 2, mod);
    long result = (half * half) % mod;

    if (exp % 2 == 1) {
        result = (result * base) % mod;
    }
    return result;
}

// 일반 재귀 — 반환 후 n을 곱하는 연산이 남아 있음
public static int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1); // 곱셈이 남아 있으므로 꼬리 재귀가 아님
}

// 꼬리 재귀 — 결과를 누적하여 전달
public static int factorialTail(int n, int acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc); // 마지막 동작이 재귀 호출
}

// 재귀 DFS
public void dfsRecursive(int node, boolean[] visited) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfsRecursive(next, visited);
        }
    }
}

// 반복문 DFS — 명시적 스택 사용
public void dfsIterative(int start) {
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) {
                stack.push(next);
            }
        }
    }
}

public static void listFiles(File dir) {
    File[] files = dir.listFiles();
    if (files == null) return;

    for (File file : files) {
        if (file.isDirectory()) {
            listFiles(file); // 재귀 탐색
        } else {
            System.out.println(file.getPath());
        }
    }
}