Advanced Recursion Problems with Function Calls Inside a Loop (Part 2)

Continuing from our previous discussion on recursive function calls inside a loop, let's explore more problems where this pattern is commonly used. These problems often arise in combinatorial and backtracking scenarios.

---

1. N-Queens Problem (Function Call in Loop)

Problem: Place N queens on an N × N chessboard such that no two queens attack each other.

Code:

public static void solveNQueens(int n, int row, boolean[] cols, boolean[] diag1, boolean[] diag2, List<Integer> board, List<List<Integer>> result) {
    if (row == n) {
        result.add(new ArrayList<>(board));
        return;
    }
    for (int col = 0; col < n; col++) { // Looping through columns
        if (!cols[col] && !diag1[row - col + n - 1] && !diag2[row + col]) {
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = true;
            board.add(col);
            solveNQueens(n, row + 1, cols, diag1, diag2, board, result); // Recursive call inside loop
            board.remove(board.size() - 1);
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = false;
        }
    }
}

---

2. Word Search (Backtracking with Loop)

Problem: Given a m x n board and a word, determine if the word exists in the board by moving in four directions.

Code:

public static boolean wordSearch(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
    if (index == word.length()) return true;
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index))
        return false;

    visited[i][j] = true;
    int[] rowDir = {-1, 1, 0, 0};
    int[] colDir = {0, 0, -1, 1};
    for (int d = 0; d < 4; d++) { // Looping through 4 directions
        if (wordSearch(board, word, i + rowDir[d], j + colDir[d], index + 1, visited))
            return true;
    }
    visited[i][j] = false;
    return false;
}

---

3. Sudoku Solver (Backtracking with Loop)

Problem: Solve a 9 × 9 Sudoku puzzle by filling empty cells following Sudoku rules.

Code:

public static boolean solveSudoku(char[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; c++) { // Looping through numbers 1-9
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (solveSudoku(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

---

4. Palindrome Partitioning (Function Call in Loop)

Problem: Partition a string into palindromic substrings.

Code:

public static void palindromePartitioning(String s, int start, List<String> temp, List<List<String>> result) {
    if (start == s.length()) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int end = start; end < s.length(); end++) { // Looping through substring partitions
        if (isPalindrome(s, start, end)) {
            temp.add(s.substring(start, end + 1));
            palindromePartitioning(s, end + 1, temp, result); // Recursive call inside loop
            temp.remove(temp.size() - 1);
        }
    }
}

---

Summary

Problem Type	Function Call in Loop?
N-Queens Problem	✅ Yes
Word Search	✅ Yes
Sudoku Solver	✅ Yes
Palindrome Partitioning	✅ Yes

Key Takeaways:

• Recursive function calls inside loops appear in backtracking problems like Sudoku, N-Queens, and Palindrome Partitioning.
• Looping through choices and making a recursive call inside the loop helps explore different possibilities.
• Backtracking is crucial when the problem requires exploring multiple paths and undoing choices.

This concludes Part 2 of recursion problems with function calls inside a loop. Let me know if you want more advanced cases or refinements! 🚀