Recursive

1. 기본 재귀 함수

• 재귀적으로 1부터 n까지의 합 구하기:

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

---

2. 피보나치 수열 (Fibonacci Sequence)

• 재귀를 사용한 피보나치 수열:

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

---

3. 팩토리얼 (Factorial)

• n! 구하기 (n의 팩토리얼):

int factorial(int n) {
    if (n == 0 || n == 1) return 1;
    return n * factorial(n - 1);
}

---

4. 이진 탐색 (Binary Search)

• 재귀적으로 이진 탐색 구현:

int binarySearch(int[] arr, int target, int low, int high) {
    if (low > high) return -1;

    int mid = (low + high) / 2;
    
    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) return binarySearch(arr, target, low, mid - 1);
    else return binarySearch(arr, target, mid + 1, high);
}

---

5. 하노이의 탑 (Tower of Hanoi)

• n개의 원판을 옮기는 재귀 알고리즘:

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        System.out.println("Move disk 1 from " + from + " to " + to);
        return;
    }

    hanoi(n - 1, from, aux, to);
    System.out.println("Move disk " + n + " from " + from + " to " + to);
    hanoi(n - 1, aux, to, from);
}

---

6. 문자열 순열 (Permutations of a String)

• 주어진 문자열의 모든 순열을 생성:

void permute(String str, int left, int right) {
    if (left == right) {
        System.out.println(str);
    } else {
        for (int i = left; i <= right; i++) {
            str = swap(str, left, i);
            permute(str, left + 1, right);
            str = swap(str, left, i);  // 백트래킹
        }
    }
}

String swap(String str, int i, int j) {
    char[] charArray = str.toCharArray();
    char temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

---

7. 부분 집합 구하기 (Subsets)

• 모든 부분 집합을 구하는 재귀 알고리즘:

void findSubsets(int[] nums, List<Integer> subset, int index) {
    if (index == nums.length) {
        System.out.println(subset);
        return;
    }

    // 현재 원소를 포함하지 않는 경우
    findSubsets(nums, subset, index + 1);

    // 현재 원소를 포함하는 경우
    subset.add(nums[index]);
    findSubsets(nums, subset, index + 1);

    // 백트래킹
    subset.remove(subset.size() - 1);
}

---

8. 재귀적으로 트리 순회

• 이진 트리의 전위, 중위, 후위 순회 (Preorder, Inorder, Postorder):

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int x) {
        val = x;
    }
}

// 전위 순회 (Preorder)
void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

// 중위 순회 (Inorder)
void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

// 후위 순회 (Postorder)
void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

---

9. N-Queens 문제

• N-Queens 문제를 재귀적으로 해결:

void solveNQueens(int n) {
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }
    backtrack(board, 0);
}

boolean backtrack(char[][] board, int row) {
    if (row == board.length) {
        printBoard(board);
        return true;
    }

    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(board, row + 1);
            board[row][col] = '.';
        }
    }
    return false;
}

boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

void printBoard(char[][] board) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            System.out.print(board[i][j] + " ");
        }
        System.out.println();
    }
}

---

10. 조합 (Combinations)

• 주어진 숫자 집합에서 가능한 모든 조합을 구하는 재귀 함수:

void findCombinations(int[] nums, int start, List<Integer> combination, int k) {
    if (combination.size() == k) {
        System.out.println(combination);
        return;
    }

    for (int i = start; i < nums.length; i++) {
        combination.add(nums[i]);
        findCombinations(nums, i + 1, combination, k);
        combination.remove(combination.size() - 1);  // 백트래킹
    }
}