Bài 13: Đệ quy (Recursion)

📖 Giới thiệu

Đệ quy (Recursion) là một kỹ thuật lập trình mạnh mẽ trong đó hàm gọi chính nó để giải quyết bài toán. Đây là một phương pháp tự nhiên để xử lý các vấn đề có cấu trúc lặp lại hoặc có thể chia nhỏ thành các bài toán con tương tự.

Đệ quy được sử dụng rộng rãi trong:

Toán học: Tính giai thừa, dãy Fibonacci, tổ hợp
Cấu trúc dữ liệu: Duyệt cây, tìm kiếm trong graph
Thuật toán: Quicksort, mergesort, binary search
Xử lý chuỗi: Palindrome, pattern matching
Game development: Minimax, backtracking

Hiểu rõ đệ quy giúp bạn:

Giải quyết bài toán phức tạp một cách elegant
Hiểu sâu về call stack và memory management
Làm chủ các thuật toán nâng cao
Tư duy logic và phân tích bài toán

🔧 Cú pháp

Cấu trúc cơ bản

cpp

return_type recursiveFunction(parameters) {
    // Base case (điều kiện dừng)
    if (baseCondition) {
        return baseValue;
    }
    
    // Recursive case (gọi đệ quy)
    return recursiveFunction(modifiedParameters);
}

Ví dụ đơn giản - Giai thừa

cpp

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

// Gọi: factorial(5)
// = 5 * factorial(4)
// = 5 * 4 * factorial(3) 
// = 5 * 4 * 3 * factorial(2)
// = 5 * 4 * 3 * 2 * factorial(1)
// = 5 * 4 * 3 * 2 * 1
// = 120

Các dạng đệ quy

cpp

// 1. Linear recursion (đệ quy tuyến tính)
int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}

// 2. Binary recursion (đệ quy nhị phân)
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 3. Tail recursion (đệ quy đuôi)
int factorialTail(int n, int result = 1) {
    if (n == 0) return result;
    return factorialTail(n - 1, n * result);
}

// 4. Mutual recursion (đệ quy tương hỗ)
bool isEven(int n);
bool isOdd(int n);

bool isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);
}

bool isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);
}

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

Call Stack trong đệ quy

cpp

int factorial(int n) {
    cout << "Goi factorial(" << n << ")" << endl;
    
    if (n <= 1) {
        cout << "Base case: tra ve 1" << endl;
        return 1;
    }
    
    int result = n * factorial(n - 1);
    cout << "Tra ve " << n << " * factorial(" << (n-1) << ") = " << result << endl;
    
    return result;
}

// Output cho factorial(4):
// Goi factorial(4)
// Goi factorial(3)  
// Goi factorial(2)
// Goi factorial(1)
// Base case: tra ve 1
// Tra ve 2 * factorial(1) = 2
// Tra ve 3 * factorial(2) = 6
// Tra ve 4 * factorial(3) = 24

Điều kiện cần thiết cho đệ quy

Base case: Điều kiện dừng rõ ràng
Recursive case: Gọi hàm với tham số đơn giản hơn
Progress: Mỗi lần gọi phải tiến gần đến base case
Correctness: Logic đúng cho cả base case và recursive case

So sánh Recursion vs Iteration

Đặc điểm	Recursion	Iteration
Syntax	Elegant, ngắn gọn	Dài hơn, phức tạp hơn
Memory	Nhiều (call stack)	Ít (chỉ variables)
Performance	Chậm hơn (function calls)	Nhanh hơn
Stack Overflow	Có thể xảy ra	Không
Debugging	Khó debug	Dễ debug hơn

Khi nào sử dụng đệ quy

Nên sử dụng:

Bài toán có cấu trúc đệ quy tự nhiên
Code ngắn gọn, dễ hiểu quan trọng hơn performance
Tree/graph traversal
Divide and conquer algorithms

Không nên sử dụng:

Bài toán đơn giản có solution iterative
Performance critical applications
Limited stack memory
Deep recursion (nguy cơ stack overflow)

💻 Ví dụ minh họa

Ví dụ 1: Hệ thống tính toán toán học

cpp

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

// Giai thừa với tối ưu hóa
long long factorial(int n) {
    if (n < 0) {
        cout << "Giai thua khong xac dinh cho so am!" << endl;
        return -1;
    }
    if (n == 0 || n == 1) return 1;
    
    // Tối ưu hóa cho số lớn
    if (n > 20) {
        cout << "So qua lon, co the gay tran so!" << endl;
        return -1;
    }
    
    return n * factorial(n - 1);
}

// Fibonacci với memoization
vector<long long> fibMemo(100, -1);

long long fibonacci(int n) {
    if (n < 0) return -1;
    if (n <= 1) return n;
    
    // Kiểm tra cache
    if (fibMemo[n] != -1) {
        return fibMemo[n];
    }
    
    // Tính và lưu cache
    fibMemo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return fibMemo[n];
}

// Ước chung lớn nhất (Euclidean algorithm)
int gcd(int a, int b) {
    cout << "gcd(" << a << ", " << b << ")" << endl;
    
    if (b == 0) {
        cout << "Base case: gcd(" << a << ", 0) = " << a << endl;
        return a;
    }
    
    return gcd(b, a % b);
}

// Luy thừa nhanh
long long power(long long base, int exp) {
    if (exp == 0) return 1;
    if (exp == 1) return base;
    
    if (exp % 2 == 0) {
        long long half = power(base, exp / 2);
        return half * half;
    } else {
        return base * power(base, exp - 1);
    }
}

// Tính tổng các chữ số
int sumDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumDigits(n / 10);
}

// Đảo ngược số
int reverseNumber(int n, int reversed = 0) {
    if (n == 0) return reversed;
    return reverseNumber(n / 10, reversed * 10 + n % 10);
}

// Kiểm tra palindrome số
bool isPalindromeNumber(int n) {
    return n == reverseNumber(n);
}

// Tháp Hà Nội
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Chuyen dia " << n << " tu " << from << " sang " << to << endl;
        return;
    }
    
    hanoi(n - 1, from, aux, to);
    cout << "Chuyen dia " << n << " tu " << from << " sang " << to << endl;
    hanoi(n - 1, aux, to, from);
}

// Menu và test functions
void testFactorial() {
    int n;
    cout << "Nhap n de tinh giai thua: ";
    cin >> n;
    
    long long result = factorial(n);
    if (result != -1) {
        cout << n << "! = " << result << endl;
    }
}

void testFibonacci() {
    int n;
    cout << "Nhap n de tinh Fibonacci: ";
    cin >> n;
    
    cout << "Day Fibonacci: ";
    for (int i = 0; i <= n; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    cout << "F(" << n << ") = " << fibonacci(n) << endl;
}

void testGCD() {
    int a, b;
    cout << "Nhap hai so de tim UCLN: ";
    cin >> a >> b;
    
    cout << "Qua trinh tinh toan:" << endl;
    int result = gcd(abs(a), abs(b));
    cout << "UCLN(" << a << ", " << b << ") = " << result << endl;
}

void testPower() {
    int base, exp;
    cout << "Nhap co so va so mu: ";
    cin >> base >> exp;
    
    long long result = power(base, exp);
    cout << base << "^" << exp << " = " << result << endl;
}

void testDigitOperations() {
    int n;
    cout << "Nhap so nguyen duong: ";
    cin >> n;
    
    cout << "Tong cac chu so: " << sumDigits(n) << endl;
    cout << "So dao nguoc: " << reverseNumber(n) << endl;
    cout << "Co phai palindrome? " << (isPalindromeNumber(n) ? "Co" : "Khong") << endl;
}

void testHanoi() {
    int n;
    cout << "Nhap so dia: ";
    cin >> n;
    
    cout << "Cac buoc giai Thap Ha Noi:" << endl;
    hanoi(n, 'A', 'C', 'B');
    cout << "Tong so buoc: " << (int)pow(2, n) - 1 << endl;
}

void showMenu() {
    cout << "\n=== HE THONG TINH TOAN RECURSIVE ===" << endl;
    cout << "1. Giai thua" << endl;
    cout << "2. Day Fibonacci" << endl;
    cout << "3. Uoc chung lon nhat (GCD)" << endl;
    cout << "4. Luy thua nhanh" << endl;
    cout << "5. Thao tac voi chu so" << endl;
    cout << "6. Thap Ha Noi" << endl;
    cout << "0. Thoat" << endl;
    cout << "Lua chon: ";
}

int main() {
    // Khởi tạo memoization cho Fibonacci
    fibMemo[0] = 0;
    fibMemo[1] = 1;
    
    int choice;
    
    do {
        showMenu();
        cin >> choice;
        
        switch (choice) {
            case 1:
                testFactorial();
                break;
            case 2:
                testFibonacci();
                break;
            case 3:
                testGCD();
                break;
            case 4:
                testPower();
                break;
            case 5:
                testDigitOperations();
                break;
            case 6:
                testHanoi();
                break;
            case 0:
                cout << "Cam on ban da su dung chuong trinh!" << endl;
                break;
            default:
                cout << "Lua chon khong hop le!" << endl;
        }
        
    } while (choice != 0);
    
    return 0;
}

Ví dụ 2: Xử lý chuỗi và mảng đệ quy

cpp

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

// Đảo ngược chuỗi
string reverseString(const string& str, int start = 0) {
    if (start >= str.length()) return "";
    return reverseString(str, start + 1) + str[start];
}

// Kiểm tra palindrome chuỗi
bool isPalindrome(const string& str, int left, int right) {
    // Bỏ qua ký tự không phải chữ/số
    while (left < right && !isalnum(str[left])) left++;
    while (left < right && !isalnum(str[right])) right--;
    
    if (left >= right) return true;
    
    if (tolower(str[left]) != tolower(str[right])) {
        return false;
    }
    
    return isPalindrome(str, left + 1, right - 1);
}

// Đếm ký tự trong chuỗi
int countChar(const string& str, char target, int index = 0) {
    if (index >= str.length()) return 0;
    
    int count = (str[index] == target) ? 1 : 0;
    return count + countChar(str, target, index + 1);
}

// Thay thế tất cả ký tự
string replaceChar(const string& str, char oldChar, char newChar, int index = 0) {
    if (index >= str.length()) return "";
    
    char currentChar = (str[index] == oldChar) ? newChar : str[index];
    return currentChar + replaceChar(str, oldChar, newChar, index + 1);
}

// Tìm kiếm nhị phân
int binarySearch(const vector<int>& arr, int target, int left, int right) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    cout << "Tim kiem trong doan [" << left << ", " << right 
         << "], mid = " << mid << " (gia tri: " << arr[mid] << ")" << endl;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

// Quick Sort
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        
        cout << "Sau khi partition [" << low << ", " << high 
             << "] voi pivot " << pivot << ": ";
        for (int i = low; i <= high; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// Merge Sort
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        cout << "Chia mang [" << left << ", " << right 
             << "] thanh [" << left << ", " << mid 
             << "] va [" << (mid + 1) << ", " << right << "]" << endl;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(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++];
    
    for (int i = 0; i < temp.size(); i++) {
        arr[left + i] = temp[i];
    }
    
    cout << "Merge [" << left << ", " << right << "]: ";
    for (int i = left; i <= right; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Tìm tất cả tập con
void findSubsets(const vector<int>& set, vector<int>& current, 
                vector<vector<int>>& result, int index = 0) {
    if (index == set.size()) {
        result.push_back(current);
        return;
    }
    
    // Không chọn phần tử hiện tại
    findSubsets(set, current, result, index + 1);
    
    // Chọn phần tử hiện tại
    current.push_back(set[index]);
    findSubsets(set, current, result, index + 1);
    current.pop_back();
}

// Test functions
void testStringOperations() {
    string str;
    cout << "Nhap chuoi: ";
    cin.ignore();
    getline(cin, str);
    
    cout << "Chuoi goc: " << str << endl;
    cout << "Dao nguoc: " << reverseString(str) << endl;
    cout << "Palindrome? " << (isPalindrome(str, 0, str.length() - 1) ? "Co" : "Khong") << endl;
    
    char target;
    cout << "Nhap ky tu can dem: ";
    cin >> target;
    cout << "So lan xuat hien: " << countChar(str, target) << endl;
    
    char oldChar, newChar;
    cout << "Nhap ky tu cu va ky tu moi: ";
    cin >> oldChar >> newChar;
    cout << "Sau khi thay the: " << replaceChar(str, oldChar, newChar) << endl;
}

void testBinarySearch() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target;
    
    cout << "Mang da sap xep: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    cout << "Nhap gia tri can tim: ";
    cin >> target;
    
    int result = binarySearch(arr, target, 0, arr.size() - 1);
    if (result != -1) {
        cout << "Tim thay tai vi tri: " << result << endl;
    } else {
        cout << "Khong tim thay!" << endl;
    }
}

void testSorting() {
    vector<int> arr;
    int n;
    
    cout << "Nhap so phan tu: ";
    cin >> n;
    
    cout << "Nhap cac phan tu: ";
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    
    int choice;
    cout << "Chon thuat toan sap xep (1: Quick Sort, 2: Merge Sort): ";
    cin >> choice;
    
    cout << "Mang ban dau: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    if (choice == 1) {
        cout << "\nQua trinh Quick Sort:" << endl;
        quickSort(arr, 0, arr.size() - 1);
    } else {
        cout << "\nQua trinh Merge Sort:" << endl;
        mergeSort(arr, 0, arr.size() - 1);
    }
    
    cout << "Mang sau sap xep: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
}

void testSubsets() {
    vector<int> set;
    int n;
    
    cout << "Nhap so phan tu cua tap hop: ";
    cin >> n;
    
    cout << "Nhap cac phan tu: ";
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        set.push_back(x);
    }
    
    vector<vector<int>> result;
    vector<int> current;
    
    findSubsets(set, current, result);
    
    cout << "Tat ca tap con:" << endl;
    for (const auto& subset : result) {
        cout << "{ ";
        for (int x : subset) {
            cout << x << " ";
        }
        cout << "}" << endl;
    }
    cout << "Tong so tap con: " << result.size() << endl;
}

int main() {
    int choice;
    
    do {
        cout << "\n=== XU LY CHUOI VA MANG RECURSIVE ===" << endl;
        cout << "1. Thao tac voi chuoi" << endl;
        cout << "2. Tim kiem nhi phan" << endl;
        cout << "3. Sap xep (Quick/Merge Sort)" << endl;
        cout << "4. Tim tat ca tap con" << endl;
        cout << "0. Thoat" << endl;
        cout << "Lua chon: ";
        cin >> choice;
        
        switch (choice) {
            case 1:
                testStringOperations();
                break;
            case 2:
                testBinarySearch();
                break;
            case 3:
                testSorting();
                break;
            case 4:
                testSubsets();
                break;
            case 0:
                cout << "Tam biet!" << endl;
                break;
            default:
                cout << "Lua chon khong hop le!" << endl;
        }
        
    } while (choice != 0);
    
    return 0;
}

🏋️ Thực hành

Bài tập 1: Recursive Tree Operations

cpp

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

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Chèn node vào BST
TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) {
        return new TreeNode(value);
    }
    
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    
    return root;
}

// Duyệt cây (Inorder)
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

// Tìm kiếm trong BST
bool search(TreeNode* root, int value) {
    if (root == nullptr) return false;
    if (root->data == value) return true;
    
    if (value < root->data) {
        return search(root->left, value);
    } else {
        return search(root->right, value);
    }
}

// Tính chiều cao cây
int height(TreeNode* root) {
    if (root == nullptr) return -1;
    
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    
    return 1 + max(leftHeight, rightHeight);
}

// Đếm số node
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    TreeNode* root = nullptr;
    vector<int> values = {50, 30, 70, 20, 40, 60, 80};
    
    cout << "Xay dung BST voi cac gia tri: ";
    for (int val : values) {
        cout << val << " ";
        root = insert(root, val);
    }
    cout << endl;
    
    cout << "Duyet cay (Inorder): ";
    inorderTraversal(root);
    cout << endl;
    
    cout << "Chieu cao cay: " << height(root) << endl;
    cout << "So node: " << countNodes(root) << endl;
    
    int searchValue = 40;
    cout << "Tim " << searchValue << ": " 
         << (search(root, searchValue) ? "Tim thay" : "Khong tim thay") << endl;
    
    return 0;
}

Bài tập 2: Backtracking - N Queens Problem

cpp

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

class NQueens {
private:
    int n;
    vector<vector<int>> board;
    int solutionCount;
    
    bool isSafe(int row, int col) {
        // Kiểm tra cột
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 1) return false;
        }
        
        // Kiểm tra đường chéo trái
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) return false;
        }
        
        // Kiểm tra đường chéo phải
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 1) return false;
        }
        
        return true;
    }
    
    void printBoard() {
        cout << "\n--- Giai phap " << (++solutionCount) << " ---" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << (board[i][j] ? "Q " : ". ");
            }
            cout << endl;
        }
    }
    
    bool solveNQueens(int row) {
        if (row == n) {
            printBoard();
            return true;
        }
        
        bool foundSolution = false;
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 1;
                
                if (solveNQueens(row + 1)) {
                    foundSolution = true;
                }
                
                board[row][col] = 0; // Backtrack
            }
        }
        
        return foundSolution;
    }
    
public:
    NQueens(int size) : n(size), solutionCount(0) {
        board = vector<vector<int>>(n, vector<int>(n, 0));
    }
    
    void solve() {
        cout << "Giai bai toan " << n << " Queens:" << endl;
        if (!solveNQueens(0)) {
            cout << "Khong co giai phap!" << endl;
        } else {
            cout << "\nTong so giai phap tim thay: " << solutionCount << endl;
        }
    }
};

int main() {
    int n;
    cout << "Nhap kich thuoc ban co (n): ";
    cin >> n;
    
    if (n < 4) {
        cout << "N phai >= 4 de co giai phap!" << endl;
        return 1;
    }
    
    NQueens queens(n);
    queens.solve();
    
    return 0;
}

📋 Tóm tắt

Các điểm quan trọng

Cấu trúc đệ quy:
- Base case: Điều kiện dừng
- Recursive case: Gọi hàm với input đơn giản hơn
- Progress: Tiến gần đến base case
Các dạng đệ quy:
- Linear: Gọi một lần (factorial, sum)
- Binary: Gọi hai lần (fibonacci, tree traversal)
- Tail: Gọi cuối cùng (có thể tối ưu)
Ứng dụng:
- Mathematical computations
- Tree/Graph algorithms
- Sorting algorithms
- Backtracking problems

Best Practices

Luôn có base case: Tránh infinite recursion
Test với input nhỏ: Đảm bảo logic đúng
Xem xét stack overflow: Với input lớn
Sử dụng memoization: Tối ưu performance
Consider iterative: Nếu performance quan trọng

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

Bài tiếp theo chúng ta sẽ bắt đầu Pointers và Memory Management:

Khái niệm pointer và address
Dynamic memory allocation
Pointer arithmetic
Memory leaks và prevention

Đệ quy là một kỹ thuật mạnh mẽ, hãy luyện tập nhiều để thành thạo!

Bài 13: Đệ quy (Recursion) ​

📖 Giới thiệu ​

🔧 Cú pháp ​

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

Ví dụ đơn giản - Giai thừa ​

Các dạng đệ quy ​

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

Call Stack trong đệ quy ​

Điều kiện cần thiết cho đệ quy ​

So sánh Recursion vs Iteration ​

Khi nào sử dụng đệ quy ​

💻 Ví dụ minh họa ​

Ví dụ 1: Hệ thống tính toán toán học ​

Ví dụ 2: Xử lý chuỗi và mảng đệ quy ​

🏋️ Thực hành ​

Bài tập 1: Recursive Tree Operations ​

Bài tập 2: Backtracking - N Queens Problem ​

📋 Tóm tắt ​

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

Best Practices ​

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