10. Recursion (Đệ quy)

🎯 Mục tiêu học tập

Hiểu cách hoạt động của recursion và call stack
Phân biệt tail recursion và non-tail recursion
Tối ưu hóa recursive algorithms
Giải quyết các bài toán đệ quy kinh điển

📚 Lý thuyết

Recursion là gì?

Định nghĩa: Kỹ thuật giải quyết bài toán bằng cách gọi chính nó với input nhỏ hơn.

Cấu trúc cơ bản:

returnType recursiveFunction(parameters) {
    // Base case - điều kiện dừng
    if (baseCondition) {
        return baseValue;
    }

    // Recursive case - gọi chính nó
    return recursiveFunction(modifiedParameters);
}

🔄 Types of Recursion

1. Direct Recursion

// Function gọi chính nó
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

2. Indirect Recursion

// Function A gọi Function B, Function B gọi Function A
void functionA(int n) {
    if (n > 0) {
        functionB(n - 1);
    }
}
void functionB(int n) {
    if (n > 0) {
        functionA(n - 1);
    }
}

3. Tail Recursion

// Recursive call là statement cuối cùng
int factorial(int n, int result) {
    if (n <= 1) return result;
    return factorial(n - 1, n * result);  // Tail recursive
}

4. Non-tail Recursion

// Có operations sau recursive call
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // Non-tail: multiplication after call
}

🧮 Bài toán kinh điển

1. Mathematical Problems

// Factorial
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

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

// Power
int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

2. Array Problems

// Array Sum
int arraySum(int[] arr, int index) {
    if (index >= arr.length) return 0;
    return arr[index] + arraySum(arr, index + 1);
}

// Binary Search
int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) 
        return binarySearch(arr, target, mid + 1, right);
    else 
        return binarySearch(arr, target, left, mid - 1);
}

3. String Problems

// Reverse String
String reverse(String str) {
    if (str.length() <= 1) return str;
    return reverse(str.substring(1)) + str.charAt(0);
}

// Check Palindrome
boolean isPalindrome(String str, int start, int end) {
    if (start >= end) return true;
    if (str.charAt(start) != str.charAt(end)) return false;
    return isPalindrome(str, start + 1, end - 1);
}

4. Backtracking Problems

// Generate Permutations
void permute(int[] nums, List<Integer> current, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int num : nums) {
        if (!current.contains(num)) {
            current.add(num);
            permute(nums, current, result);
            current.remove(current.size() - 1);  // Backtrack
        }
    }
}

💡 Optimization Techniques

1. Memoization

// Cache kết quả để tránh tính lại
Map<Integer, Integer> memo = new HashMap<>();
int fibonacci(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);

    int result = fibonacci(n - 1) + fibonacci(n - 2);
    memo.put(n, result);
    return result;
}

2. Tail Call Optimization

// Chuyển non-tail thành tail recursion
int factorialHelper(int n, int accumulator) {
    if (n <= 1) return accumulator;
    return factorialHelper(n - 1, n * accumulator);
}

int factorial(int n) {
    return factorialHelper(n, 1);
}

3. Iterative Conversion

// Chuyển recursion thành iteration
int factorialIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

⚠️ Common Pitfalls

1. Stack Overflow

// Quá nhiều recursive calls
// Solution: Optimize hoặc chuyển sang iteration

2. Inefficient Recursion

// Fibonacci naive: O(2^n)
// Solution: Memoization hoặc DP

3. Missing Base Case

// Không có điều kiện dừng → infinite recursion

🔍 When to Use Recursion

✅ Good for:

Tree/Graph traversal
Divide and conquer algorithms
Backtracking problems
Mathematical calculations
Problems with recursive structure

❌ Avoid when:

Simple iteration is sufficient
Performance is critical
Deep recursion (stack overflow risk)
No clear recursive structure

📋 Bài tập thực hành

Cơ bản:

Factorial, Fibonacci
Array sum, product
String reverse, palindrome check
Binary search recursive

Trung bình:

Tower of Hanoi
Generate all permutations
Combination sum
Word search in matrix

Nâng cao:

N-Queens problem
Sudoku solver
Generate valid parentheses
Expression evaluation

🚀 Chuẩn bị code

mkdir 10-recursion
# Files: BasicRecursion.java, BacktrackingProblems.java, RecursionOptimization.java