Khóa học C++

Appearance

🔄 Đệ quy nâng cao (Advanced Recursion) ​

📖 Giới thiệu ​

Đệ quy nâng cao là kỹ thuật powerful để giải quyết các vấn đề phức tạp bằng cách chia nhỏ thành các subproblems tương tự. Từ Tower of Hanoi classical đến modern backtracking algorithms, đệ quy là tool không thể thiếu trong competitive programming và algorithm design.

Tại sao đệ quy nâng cao quan trọng?

  • Problem decomposition: Chia vấn đề phức tạp thành parts đơn giản hơn
  • Tree/Graph traversal: DFS, binary tree operations
  • Backtracking: N-Queens, Sudoku, maze solving
  • Mathematical problems: Combinatorics, number theory

Các pattern đệ quy chính:

  • Linear recursion: Fibonacci, factorial
  • Tree recursion: Binary tree traversal
  • Tail recursion: Optimized recursive calls
  • Backtracking: Trial and error với undo
  • Divide & Conquer: Merge sort, quick sort

🔧 Cú pháp ​

Classic Recursive Problems ​

cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Tower of Hanoi - Classic recursion problem
void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    
    // Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, from, aux, to);
    
    // Move the largest disk from source to destination
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    
    // Move n-1 disks from auxiliary to destination
    towerOfHanoi(n - 1, aux, to, from);
}

// N-Queens Problem - Backtracking
class NQueens {
private:
    vector<vector<string>> solutions;
    vector<string> board;
    int n;
    
    bool isSafe(int row, int col) {
        // Check column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        
        // Check diagonal (top-left)
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        
        // Check diagonal (top-right)
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }
    
    void backtrack(int row) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';      // Place queen
                backtrack(row + 1);         // Recursive call
                board[row][col] = '.';      // Backtrack
            }
        }
    }
    
public:
    vector<vector<string>> solveNQueens(int size) {
        n = size;
        board = vector<string>(n, string(n, '.'));
        solutions.clear();
        
        backtrack(0);
        return solutions;
    }
};

// Permutations using backtracking
void generatePermutations(vector<int>& nums, vector<int>& current, 
                         vector<bool>& used, vector<vector<int>>& result) {
    if (current.size() == nums.size()) {
        result.push_back(current);
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        if (!used[i]) {
            used[i] = true;
            current.push_back(nums[i]);
            
            generatePermutations(nums, current, used, result);
            
            current.pop_back();  // Backtrack
            used[i] = false;
        }
    }
}

Tree Recursion ​

cpp
// Binary Tree Node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Tree traversals using recursion
void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root) {
        inorderTraversal(root->left, result);   // Left
        result.push_back(root->val);            // Root
        inorderTraversal(root->right, result);  // Right
    }
}

void preorderTraversal(TreeNode* root, vector<int>& result) {
    if (root) {
        result.push_back(root->val);            // Root
        preorderTraversal(root->left, result);  // Left
        preorderTraversal(root->right, result); // Right
    }
}

void postorderTraversal(TreeNode* root, vector<int>& result) {
    if (root) {
        postorderTraversal(root->left, result);  // Left
        postorderTraversal(root->right, result); // Right
        result.push_back(root->val);             // Root
    }
}

// Tree properties using recursion
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    
    function<bool(TreeNode*, TreeNode*)> helper = [&](TreeNode* left, TreeNode* right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        
        return (left->val == right->val) &&
               helper(left->left, right->right) &&
               helper(left->right, right->left);
    };
    
    return helper(root->left, root->right);
}

// Path sum problems
bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    
    if (!root->left && !root->right) {
        return root->val == targetSum;
    }
    
    return hasPathSum(root->left, targetSum - root->val) ||
           hasPathSum(root->right, targetSum - root->val);
}

Advanced Backtracking ​

cpp
// Sudoku Solver
class SudokuSolver {
private:
    bool isValid(vector<vector<char>>& board, int row, int col, char num) {
        // Check row
        for (int j = 0; j < 9; j++) {
            if (board[row][j] == num) return false;
        }
        
        // Check column
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) return false;
        }
        
        // Check 3x3 box
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == num) return false;
            }
        }
        
        return true;
    }
    
    bool solve(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, i, j, num)) {
                            board[i][j] = num;
                            
                            if (solve(board)) {
                                return true;
                            }
                            
                            board[i][j] = '.';  // Backtrack
                        }
                    }
                    return false;  // No valid number found
                }
            }
        }
        return true;  // All cells filled
    }
    
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
};

// Maze pathfinding with backtracking
class MazeSolver {
private:
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    bool isValid(vector<vector<int>>& maze, int x, int y, vector<vector<bool>>& visited) {
        int m = maze.size(), n = maze[0].size();
        return x >= 0 && x < m && y >= 0 && y < n && 
               maze[x][y] == 0 && !visited[x][y];
    }
    
    bool findPath(vector<vector<int>>& maze, int x, int y, int destX, int destY,
                  vector<vector<bool>>& visited, vector<pair<int, int>>& path) {
        if (x == destX && y == destY) {
            path.push_back({x, y});
            return true;
        }
        
        visited[x][y] = true;
        path.push_back({x, y});
        
        for (auto& dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            
            if (isValid(maze, newX, newY, visited)) {
                if (findPath(maze, newX, newY, destX, destY, visited, path)) {
                    return true;
                }
            }
        }
        
        // Backtrack
        path.pop_back();
        visited[x][y] = false;
        return false;
    }
    
public:
    vector<pair<int, int>> solveMaze(vector<vector<int>>& maze, 
                                    pair<int, int> start, pair<int, int> end) {
        vector<pair<int, int>> path;
        vector<vector<bool>> visited(maze.size(), 
                                   vector<bool>(maze[0].size(), false));
        
        if (findPath(maze, start.first, start.second, 
                    end.first, end.second, visited, path)) {
            return path;
        }
        return {};  // No path found
    }
};

🔬 Phân tích & Giải thích chi tiết ​

Recursion vs Iteration Trade-offs ​

Recursion Advantages:

  • Elegant code: More readable for tree/graph problems
  • Natural fit: Some problems are inherently recursive
  • Divide & conquer: Easy to implement
  • Backtracking: Natural undo mechanism

Recursion Disadvantages:

  • Stack overflow: Deep recursion can exceed stack space
  • Performance: Function call overhead
  • Memory usage: Each call uses stack frame
  • Debugging: Harder to trace execution

Optimization Techniques ​

Tail Recursion Optimization:

cpp
// Non-tail recursive (not optimizable)
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // Operation after recursive call
}

// Tail recursive (optimizable)
int factorialTail(int n, int acc = 1) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);  // Recursive call is last operation
}

// Iterative equivalent
int factorialIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Memoization for Recursive Problems:

cpp
// Fibonacci with memoization
unordered_map<int, long long> memo;

long long fibonacciMemo(int n) {
    if (n <= 1) return n;
    
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
    return memo[n];
}

💻 Ví dụ minh họa ​

Ví dụ 1: Advanced Combinatorial Problems ​

cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class CombinatoricsRecursion {
public:
    // Generate all subsets (Power Set)
    void generateSubsets(vector<int>& nums, int index, vector<int>& current, 
                        vector<vector<int>>& result) {
        if (index == nums.size()) {
            result.push_back(current);
            return;
        }
        
        // Don't include current element
        generateSubsets(nums, index + 1, current, result);
        
        // Include current element
        current.push_back(nums[index]);
        generateSubsets(nums, index + 1, current, result);
        current.pop_back();  // Backtrack
    }
    
    // Generate combinations of size k
    void generateCombinations(vector<int>& nums, int start, int k, 
                             vector<int>& current, vector<vector<int>>& result) {
        if (current.size() == k) {
            result.push_back(current);
            return;
        }
        
        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            generateCombinations(nums, i + 1, k, current, result);
            current.pop_back();  // Backtrack
        }
    }
    
    // Generate all valid parentheses combinations
    void generateParentheses(int n, int open, int close, string current, 
                           vector<string>& result) {
        if (current.length() == 2 * n) {
            result.push_back(current);
            return;
        }
        
        if (open < n) {
            generateParentheses(n, open + 1, close, current + "(", result);
        }
        
        if (close < open) {
            generateParentheses(n, open, close + 1, current + ")", result);
        }
    }
    
    // Word Break problem using recursion with memoization
    bool wordBreakHelper(string s, vector<string>& wordDict, int start, 
                        unordered_set<string>& wordSet, vector<int>& memo) {
        if (start == s.length()) {
            return true;
        }
        
        if (memo[start] != -1) {
            return memo[start];
        }
        
        for (int end = start + 1; end <= s.length(); end++) {
            string substr = s.substr(start, end - start);
            if (wordSet.find(substr) != wordSet.end() && 
                wordBreakHelper(s, wordDict, end, wordSet, memo)) {
                memo[start] = 1;
                return true;
            }
        }
        
        memo[start] = 0;
        return false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> memo(s.length(), -1);
        return wordBreakHelper(s, wordDict, 0, wordSet, memo);
    }
    
    void demonstrateRecursion() {
        cout << "=== ADVANCED RECURSION DEMONSTRATIONS ===" << endl;
        
        // Subsets demo
        cout << "\n🔢 Generating all subsets of [1, 2, 3]:" << endl;
        vector<int> nums = {1, 2, 3};
        vector<vector<int>> subsets;
        vector<int> current;
        generateSubsets(nums, 0, current, subsets);
        
        for (const auto& subset : subsets) {
            cout << "[";
            for (int i = 0; i < subset.size(); i++) {
                cout << subset[i];
                if (i < subset.size() - 1) cout << ", ";
            }
            cout << "] ";
        }
        cout << endl;
        
        // Combinations demo
        cout << "\n🔢 Generating combinations of size 2 from [1, 2, 3, 4]:" << endl;
        vector<int> nums2 = {1, 2, 3, 4};
        vector<vector<int>> combinations;
        current.clear();
        generateCombinations(nums2, 0, 2, current, combinations);
        
        for (const auto& combo : combinations) {
            cout << "[" << combo[0] << ", " << combo[1] << "] ";
        }
        cout << endl;
        
        // Parentheses demo
        cout << "\n📋 Valid parentheses for n=3:" << endl;
        vector<string> parentheses;
        generateParentheses(3, 0, 0, "", parentheses);
        
        for (const string& p : parentheses) {
            cout << p << " ";
        }
        cout << endl;
        
        // Word break demo
        cout << "\n📝 Word break example:" << endl;
        string s = "leetcode";
        vector<string> wordDict = {"leet", "code"};
        bool canBreak = wordBreak(s, wordDict);
        cout << "Can break '" << s << "': " << (canBreak ? "Yes" : "No") << endl;
    }
};

int main() {
    CombinatoricsRecursion demo;
    demo.demonstrateRecursion();
    
    return 0;
}

🏋️ Thực hành ​

Bài tập 1: Knight's Tour Problem ​

Implement Knight's Tour sử dụng backtracking:

  • 8x8 chessboard
  • Knight phải visit mỗi square exactly once
  • Return valid tour path

Bài tập 2: Expression Evaluation ​

Build recursive expression evaluator:

  • Support +, -, *, /, parentheses
  • Handle operator precedence
  • Error handling cho invalid expressions

Bài tập 3: Tree Serialization ​

Implement binary tree serialization/deserialization:

  • Convert tree to string representation
  • Reconstruct tree from string
  • Handle null nodes properly

Bài tập 4: Palindrome Partitioning ​

Find all possible palindrome partitions của string:

  • Each partition phải là palindrome
  • Return all valid partitioning ways
  • Optimize với memoization

📋 Tóm tắt ​

Các điểm quan trọng ​

Recursion Patterns:

  • Linear: Simple chain of calls
  • Tree: Multiple recursive calls
  • Backtracking: Try and undo approach
  • Tail: Last operation is recursive call

Common Applications:

  • Tree/Graph traversal: DFS, tree operations
  • Combinatorics: Permutations, combinations
  • Puzzle solving: N-Queens, Sudoku
  • String processing: Parsing, pattern matching

Optimization Strategies:

  • Memoization: Cache results
  • Tail recursion: Enable compiler optimization
  • Iterative conversion: When stack space is concern
  • Early termination: Prune unnecessary branches

Best Practices ​

Design:

  • Define clear base case
  • Ensure progress toward base case
  • Minimize parameter passing
  • Use appropriate data structures

Performance:

  • Consider iterative alternatives
  • Use memoization cho overlapping subproblems
  • Monitor stack depth
  • Profile recursive vs iterative performance

Chuẩn bị cho bài tiếp theo ​

Bài học tiếp theo sẽ tìm hiểu về Dynamic Programming:

  • Memoization: Top-down approach
  • Tabulation: Bottom-up approach
  • Classic Problems: Fibonacci, Knapsack, LIS
  • Optimization: Space complexity reduction
  • Advanced DP: 2D, tree DP, digit DP

Advanced recursion là foundation cho many algorithmic techniques. Master recursion để solve complex problems elegantly!

Khóa học C++ miễn phí

Copyright © 2024 zukahai