Module 13: Đệ quy chuyên sâu

Đệ quy nâng cao

Đệ quy quay lui (Backtracking)

Kỹ thuật thử-sai: thử từng lựa chọn, nếu sai thì quay lại bước trước.

// In tat ca nhi phan do dai n
void binary(int n, int arr[], int i) {
    if (i == n) {
        for (int j = 0; j < n; j++) printf("%d", arr[j]);
        printf("\n"); return;
    }
    arr[i] = 0; binary(n, arr, i+1);
    arr[i] = 1; binary(n, arr, i+1);
}

Chia để trị (Divide and Conquer)

Chia bài toán thành các bài toán con, giải đệ quy, kết hợp kết quả.

int power(int x, int n) {
    if (n == 0) return 1;
    int half = power(x, n/2);
    if (n % 2 == 0) return half * half;
    else return half * half * x;
}

Đệ quy có nhớ (Memoization)

Lưu kết quả đã tính để tránh tính lại.

int fib[100] = {0};
int fib_memo(int n) {
    if (n <= 1) return n;
    if (fib[n]) return fib[n];
    fib[n] = fib_memo(n-1) + fib_memo(n-2);
    return fib[n];
}

Nhánh cận (Branch and Bound)

Cắt tỉa nhánh không khả thi để tối ưu thời gian chạy.