Thuật toán đệ quy - Sức mạnh phân rã bài toán

admin đã đăng vào 31, Tháng 7, 2026, 23:01

THUẬT TOÁN ĐỆ QUY - SỨC MẠNH PHÂN RÃ BÀI TOÁN

Chào các bạn học sinh và lập trình viên! Trong lập trình thi đấu và học tập cấu trúc dữ liệu - giải thuật trên hệ thống Sen Code Online Judge!, chúng ta thường gặp những bài toán có cấu trúc tự lặp lại hoặc có thể chia nhỏ thành các bài toán con tương tự nhưng có quy mô nhỏ hơn.

Để giải quyết các bài toán này một cách tối giản và nghệ thuật nhất, người ta sử dụng Đệ quy (Recursion). Đệ quy không chỉ là một kỹ thuật viết code, mà là một tư duy phân rã bài toán cực kỳ mạnh mẽ. Bài viết này sẽ giúp các bạn làm chủ khái niệm đệ quy, cơ chế hoạt động bên trong bộ nhớ máy tính, các lưu ý về độ phức tạp và các ví dụ điển hình.

1. Khái niệm đệ quy là gì?

Trong lập trình, một chương trình con (hàm hoặc thủ tục) được gọi là Đệ quy nếu trong quá trình thực thi khối lệnh của mình, nó có câu lệnh tự gọi lại chính nó.

Cấu trúc bắt buộc của một hàm đệ quy:

Mỗi hàm đệ quy bắt buộc phải gồm hai phần chính:

Trường hợp cơ sở (Base Case / Điểm dừng): Đây là trường hợp đơn giản nhất của bài toán mà ta đã biết sẵn kết quả trực tiếp mà không cần tính toán đệ quy thêm. Nếu thiếu trường hợp cơ sở, hàm đệ quy sẽ tự gọi mãi mãi, gây treo máy hoặc tràn bộ nhớ.
Bước đệ quy (Recursive Step): Đây là phần hàm tự gọi lại chính nó nhưng với các tham số đầu vào có quy mô nhỏ hơn để dần dần tiếp cận đến trường hợp cơ sở.

2. Giải thích sâu sắc về cơ chế hoạt động của Đệ quy

Cơ chế Ngăn xếp gọi hàm (Call Stack):

Khi một hàm được gọi, hệ điều hành sẽ cấp phát một vùng nhớ trong ngăn xếp gọi hàm (Call Stack) để lưu giữ các biến cục bộ và trạng thái hiện tại của hàm đó.

Khi hàm đệ quy tự gọi lại chính nó, một khung ngăn xếp (Stack Frame) mới lại được đẩy (push) lên đỉnh của Call Stack. Hàm cũ tạm dừng hoạt động và chờ hàm mới thực thi xong.
Quá trình này lặp lại cho đến khi gặp Trường hợp cơ sở. Lúc này, hàm tại đỉnh ngăn xếp sẽ trả về kết quả và giải phóng vùng nhớ (pop). Các hàm nằm phía dưới lần lượt nhận kết quả, hoàn thành nhiệm vụ và rút khỏi ngăn xếp theo thứ tự LIFO (Vào sau ra trước).

3. Các lưu ý quan trọng về Độ phức tạp khi dùng Đệ quy

Đệ quy là một con dao hai lưỡi. Nếu dùng không cẩn thận, chương trình của bạn sẽ gặp các lỗi nghiêm trọng về hiệu năng:

a. Độ phức tạp thời gian (Time Complexity) - Bùng nổ tổ hợp

Nếu mỗi lời gọi đệ quy phân nhánh thành nhiều lời gọi đệ quy con (ví dụ đệ quy Fibonacci phân đôi thành 2 nhánh), số lượng phép tính có thể tăng trưởng theo cấp số nhân (lũy thừa $O(2^{N})$ hoặc giai thừa $O(N!)$). Điều này khiến chương trình lập tức bị quá thời gian (TLE) ngay cả với N rất nhỏ.

b. Độ phức tạp không gian (Space Complexity) - Lỗi tràn ngăn xếp

Do mỗi lời gọi đệ quy đều chiếm dụng một khung nhớ trên Call Stack, nên nếu độ sâu đệ quy lớn nhất là D (số tầng đệ quy lồng nhau), độ phức tạp không gian bổ sung sẽ là $O(D)$.
Nếu đệ quy quá sâu (ví dụ $D > 10^{5}$), Call Stack của hệ thống sẽ bị đầy, dẫn đến lỗi crash chương trình kinh điển: Stack Overflow (Tràn ngăn xếp).

4. Ba ví dụ minh họa bằng C++ và giải tích chi tiết

Ví dụ 1: Tính giai thừa của số nguyên dương N (Đệ quy tuyến tính)

Công thức toán học của giai thừa:

Nếu N = 0 hoặc N = 1: N! = 1 (Trường hợp cơ sở)
Nếu N > 1: N! = N * (N - 1)! (Bước đệ quy)

#include <bits/stdc++.h>

using namespace std;

// Hàm đệ quy tính giai thừa
long long giaiThua(int n) {
    if (n == 0 || n == 1) { // (1) Trường hợp cơ sở
        return 1;
    }
    return n * giaiThua(n - 1); // (2) Bước đệ quy gọi lại với (n-1)
}

int main() {
    int N;
    cin >> N;
    cout << N << "! = " << giaiThua(N) << "\n";
    return 0;
}

Giải tích chi tiết cơ chế chạy với N = 3:

Lời gọi giaiThua(3) được tạo trên Call Stack. Vì 3 != 1, hàm thực hiện lệnh return 3 * giaiThua(2). Lời gọi tạm dừng để chờ kết quả của giaiThua(2).
Lời gọi giaiThua(2) được đẩy vào Stack. Thực hiện return 2 * giaiThua(1), tạm dừng chờ giaiThua(1).
Lời gọi giaiThua(1) được đẩy vào Stack. Gặp trường hợp cơ sở n == 1, hàm lập tức trả về 1 và giải phóng khỏi Stack.
Lời gọi giaiThua(2) nhận kết quả 1 từ bước 3, tính 2 * 1 = 2, trả về 2 và giải phóng khỏi Stack.
Lời gọi giaiThua(3) nhận kết quả 2 từ bước 4, tính 3 * 2 = 6, trả về kết quả cuối cùng là 6.

Độ phức tạp thời gian: $O(N)$ vì có đúng N lần gọi hàm.
Độ phức tạp bộ nhớ: $O(N)$ do ngăn xếp chứa tối đa N hàm cùng lúc.

Ví dụ 2: Tìm số Fibonacci thứ N (Đệ quy phân nhánh)

Công thức Fibonacci:

Nếu N = 0: F₀ = 0; nếu N = 1: F₁ = 1.
Nếu N > 1: F_N = F_N-1 + F_N-2.

#include <bits/stdc++.h>

using namespace std;

// Hàm đệ quy Fibonacci phân nhánh
long long fibo(int n) {
    if (n == 0) return 0; // Trường hợp cơ sở 1
    if (n == 1) return 1; // Trường hợp cơ sở 2
    return fibo(n - 1) + fibo(n - 2); // Bước đệ quy rẽ làm 2 nhánh
}

int main() {
    int N;
    cin >> N;
    cout << "F(" << N << ") = " << fibo(N) << "\n";
    return 0;
}

Giải tích chi tiết về hiệu năng:

Lời gọi fibo(N) sẽ phân rã thành hai cuộc gọi là fibo(N-1) và fibo(N-2). Bản chất quá trình này tạo nên một cây quyết định nhị phân có chiều cao tối đa là N.
Tổng số nút trên cây đệ quy này là $O(2^N)$. Với N = 40, số phép tính đã lên tới hơn 1 nghìn tỷ phép tính, khiến chương trình chạy mất vài phút. Đây là minh chứng rõ nhất của sự bùng nổ độ phức tạp thời gian khi đệ quy không được tối ưu.

Ví dụ 3: Tìm kiếm nhị phân bằng Đệ quy

Tìm kiếm nhị phân có thể được viết cực kỳ ngắn gọn bằng đệ quy chia để trị.

#include <bits/stdc++.h>

using namespace std;

// Hàm đệ quy tìm kiếm nhị phân x trong đoạn [left, right] của mảng A
int binarySearchDeQuy(int A[], int left, int right, int x) {
    if (left > right) {
        return -1; // Trường hợp cơ sở: Khoảng tìm kiếm rỗng (Không tìm thấy)
    }

    int mid = left + (right - left) / 2;

    if (A[mid] == x) {
        return mid; // Trường hợp cơ sở: Tìm thấy x tại vị trí mid
    }

    if (A[mid] > x) {
        // Bước đệ quy: tìm ở nửa bên trái
        return binarySearchDeQuy(A, left, mid - 1, x);
    } else {
        // Bước đệ quy: tìm ở nửa bên phải
        return binarySearchDeQuy(A, mid + 1, right, x);
    }
}

Giải tích chi tiết:

Tại mỗi bước gọi đệ quy, khoảng tìm kiếm bị chia đôi. Do đó độ sâu lớn nhất của ngăn xếp đệ quy chỉ là $O(\log N)$.
Độ phức tạp thời gian: $O(\log N)$.
Độ phức tạp bộ nhớ (Call Stack): $O(\log N)$.

5. ĐỀ XUẤT 10 BÀI TẬP THỰC HÀNH THỰC TẾ (THUẬT TOÁN ĐỆ QUY)

Hãy lập trình đọc/ghi dữ liệu bằng tệp thông qua freopen đối với 10 bài tập ứng dụng đệ quy đa dạng lĩnh vực sau đây:

Bài 1: Lũy thừa nhị phân nhanh trong mã hóa mật mã

Ngữ cảnh: Trong hệ thống mã hóa bảo mật thông tin, ta cần tính giá trị A^B chia lấy dư cho M (A^B % M) với số mũ B cực kỳ lớn (lên tới 10¹⁸). Phép nhân lặp tuần tự thông thường $O(B)$ bước sẽ bị TLE. Ta cần sử dụng đệ quy chia để trị (Lũy thừa nhị phân):
- Nếu B = 0: A⁰ = 1.
- Nếu B chẵn: A^B = (A^B/2)².
- Nếu B lẻ: A^B = A * (A^B/2)².
Yêu cầu: Viết hàm đệ quy long long luyThuaNhanh(long long A, long long B, long long M) tính A^B % M. Đọc từ tệp powmod.inp ghi ra tệp powmod.out.
Đầu vào (Input - tệp powmod.inp): Một dòng chứa 3 số nguyên dương A, B, M (1 <= A, M <= 10⁹, 1 <= B <= 10¹⁸).
Đầu ra (Output - tệp powmod.out): Một số nguyên duy nhất là kết quả phép tính.
Ví dụ:
- Input: 2 10 1000
- Output: 24 (Vì 2¹⁰ = 1024 % 1000 = 24)

Bài 2: Ước lượng sự sinh sản của vi khuẩn phòng thí nghiệm

Ngữ cảnh: Một nhà sinh học nghiên cứu một loài vi khuẩn phân đôi. Ban đầu chỉ có 1 con vi khuẩn. Cứ sau mỗi giờ, một con vi khuẩn trưởng thành sẽ tự phân chia thành 2 con vi khuẩn mới.
Yêu cầu: Viết hàm đệ quy tính số lượng vi khuẩn sau H giờ. Đọc H từ tệp bacteria.inp ghi ra tệp bacteria.out.
Đầu vào (Input - tệp bacteria.inp): Một số nguyên duy nhất H (0 <= H <= 60).
Đầu ra (Output - tệp bacteria.out): Một số nguyên duy nhất là số lượng vi khuẩn (sử dụng kiểu long long).
Ví dụ:
- Input: 3
- Output: 8 (Ban đầu: 1 -> Giờ 1: 2 -> Giờ 2: 4 -> Giờ 3: 8)

Bài 3: Trò chơi Tháp Hà Nội huyền thoại

Ngữ cảnh: Trò chơi Tháp Hà Nội gồm 3 cột A, B, C và N chiếc đĩa kích thước khác nhau. Ban đầu, các đĩa xếp chồng lên nhau ở cột A theo thứ tự nhỏ ở trên, lớn ở dưới. Nhiệm vụ là chuyển toàn bộ đĩa sang cột C tuân thủ quy tắc: mỗi lần chỉ chuyển 1 đĩa và đĩa lớn tuyệt đối không được đặt đè lên đĩa nhỏ.
Yêu cầu: Viết hàm đệ quy đếm số bước di chuyển tối thiểu để chuyển hết N đĩa từ cột A sang C. Đọc N từ tệp hanoi.inp ghi kết quả ra tệp hanoi.out (công thức tối thiểu là 2^N - 1 bước).
Đầu vào (Input - tệp hanoi.inp): Số nguyên N (1 <= N <= 30).
Đầu ra (Output - tệp hanoi.out): Số nguyên duy nhất là số bước di chuyển tối thiểu.
Ví dụ:
- Input: 3
- Output: 7

Bài 4: Ước chung lớn nhất đệ quy Euclid

Ngữ cảnh: Thuật toán Euclid tìm ước chung lớn nhất (UCLN) của hai số A và B có thể cài đặt cực kỳ ngắn gọn bằng đệ quy dựa trên tính chất: UCLN(A, B) = UCLN(B, A % B) nếu B != 0, và bằng A nếu B = 0.
Yêu cầu: Viết hàm đệ quy long long ucln(long long a, long long b). Đọc hai số từ tệp gcd.inp ghi ra tệp gcd.out.
Đầu vào (Input - tệp gcd.inp): Một dòng chứa hai số nguyên dương A và B (1 <= A, B <= 10¹⁸).
Đầu ra (Output - tệp gcd.out): Ước chung lớn nhất của A và B.
Ví dụ:
- Input: 48 18
- Output: 6

Bài 5: Tìm chữ số lớn nhất của số nguyên

Ngữ cảnh: Cho một số nguyên dương N. Bạn cần phân tích cấu trúc chữ số của N để tìm ra chữ số có giá trị lớn nhất trong số đó.
Yêu cầu: Viết một hàm đệ quy int chuSoMax(long long N). Đọc N từ tệp maxdigit.inp ghi ra tệp maxdigit.out.
Đầu vào (Input - tệp maxdigit.inp): Số nguyên dương N (1 <= N <= 10¹⁸).
Đầu ra (Output - tệp maxdigit.out): Chữ số lớn nhất của N (từ 0 đến 9).
Ví dụ:
- Input: 90281
- Output: 9

Bài 6: Đảo ngược tin nhắn tình báo

Ngữ cảnh: Để gửi tin nhắn mật, một điệp viên sử dụng phương pháp đảo ngược hoàn toàn thứ tự các ký tự của chuỗi tin nhắn S ban đầu.
Yêu cầu: Viết hàm đệ quy đảo ngược chuỗi ký tự S. Đọc S từ tệp reverse.inp ghi kết quả ra tệp reverse.out.
Đầu vào (Input - tệp reverse.inp): Một chuỗi ký tự S có thể chứa khoảng trắng (độ dài không quá 1000 ký tự).
Đầu ra (Output - tệp reverse.out): Chuỗi S sau khi đã được đảo ngược.
Ví dụ:
- Input: Sencode
- Output: edocneS

Bài 7: Tính tổng mảng bằng đệ quy

Ngữ cảnh: Cho một mảng gồm N số nguyên. Hãy thực hiện tính tổng các phần tử của mảng này bằng phương pháp đệ quy (Tổng của N phần tử = phần tử cuối + Tổng của N-1 phần tử trước đó).
Yêu cầu: Viết hàm đệ quy long long tongMang(int A[], int N). Đọc dữ liệu từ tệp arraysum.inp ghi ra tệp arraysum.out.
Đầu vào (Input - tệp arraysum.inp):
- Dòng 1 chứa số nguyên dương N (1 <= N <= 1000).
- Dòng 2 chứa N số nguyên của mảng.
Đầu ra (Output - tệp arraysum.out): Một số nguyên duy nhất là tổng mảng.
Ví dụ:
- Input:
```
4
3 5 2 10
```
- Output: 20

Bài 8: Chọn kiện hàng tối ưu (Subset Sum)

Ngữ cảnh: Một xe tải có thể chở tối đa trọng lượng W. Có N kiện hàng với trọng lượng lần lượt là A[0], A[1], ..., A[N-1]. Người xếp hàng muốn biết có bao nhiêu cách chọn một nhóm kiện hàng sao cho tổng trọng lượng của chúng đúng bằng W.
Yêu cầu: Viết thuật toán đệ quy quay lui (Backtracking) để đếm số cách chọn thỏa mãn. Đọc dữ liệu từ tệp subset.inp ghi ra tệp subset.out.
Đầu vào (Input - tệp subset.inp):
- Dòng 1 chứa hai số nguyên N và W (1 <= N <= 20, 1 <= W <= 10⁵).
- Dòng 2 chứa N số nguyên dương là trọng lượng của từng kiện hàng.
Đầu ra (Output - tệp subset.out): Số lượng cách chọn kiện hàng thỏa mãn.
Ví dụ:
- Input:
```
4 10
2 3 5 8
```
- Output: 2 (Hai cách chọn là: {2, 3, 5} và {2, 8})

Bài 9: Sinh khóa nhị phân an ninh mạng

Ngữ cảnh: Một chuyên gia an ninh mạng cần sinh ra toàn bộ các mã khóa nhị phân (chỉ gồm các ký tự '0' và '1') có độ dài N để kiểm tra thử hệ thống bảo mật.
Yêu cầu: Viết hàm đệ quy quay lui để sinh ra toàn bộ các chuỗi nhị phân độ dài N theo thứ tự từ điển. Đọc N từ tệp binarygen.inp ghi kết quả ra tệp binarygen.out.
Đầu vào (Input - tệp binarygen.inp): Số nguyên dương N (1 <= N <= 15).
Đầu ra (Output - tệp binarygen.out): Toàn bộ các chuỗi nhị phân độ dài N, mỗi chuỗi trên một dòng.
Ví dụ:
- Input: 3
- Output:
```
000
001
010
011
100
101
110
111
```

Bài 10: Số đường đi trong mê cung lưới ô vuông

Ngữ cảnh: Một robot đứng ở góc trên bên trái ô (1, 1) của một lưới ô vuông kích thước M x N. Robot cần di chuyển đến góc dưới bên phải ô (M, N). Tại mỗi bước, robot chỉ được phép di chuyển sang phải 1 ô hoặc xuống dưới 1 ô.
Yêu cầu: Viết hàm đệ quy tính số lượng con đường khác nhau mà robot có thể đi để đến được đích. Đọc M và N từ tệp maze.inp ghi ra tệp maze.out (số lượng đường đi từ ô (i, j) = số đường đi từ ô (i+1, j) + số đường đi từ ô (i, j+1)).
Đầu vào (Input - tệp maze.inp): Một dòng chứa hai số nguyên dương M và N (1 <= M, N <= 10).
Đầu ra (Output - tệp maze.out): Số lượng con đường đi phân biệt.
Ví dụ:
- Input: 3 3
- Output: 6

Lời kết

Tư duy đệ quy là một bước ngoặt lớn giúp thay đổi cách bạn tiếp cận và giải quyết các bài toán phức tạp. Hãy nắm vững cách xác định Trường hợp cơ sở và Độ sâu ngăn xếp của hàm để viết nên những chương trình đệ quy an toàn, hiệu quả!

Hãy lập trình và nộp bài giải của 10 bài tập đệ quy trên tại hệ thống Sen Code Online Judge! nhé! Chúc các bạn học tập thật tốt!

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

admin đã bình luận lúc 31, Tháng 7, 2026, 16:21

Test comments!