- title Đệ quy và quay lui (Recursion and backtracking) - Đệ quy và quay lui (Recursion and backtracking) === - ###### ✍️ Author: 2School Guideline ###### 📋 Content: [TOC] - # Giới thiệu chung Trong đời sống, ta thỉnh thoảng sẽ bắt gặp được đệ quy xung quanh chúng ta. Ví dụ, ta đặt 2 cái gương đối diện nhau và đứng ở giữa, khi đó ta sẽ thấy được hình ảnh phản chiếu của gương thứ nhất trong gương thứ hai, gương thứ hai lại chứa hình ảnh phản chiếu của gương thứ nhất, và cứ như vậy tới vô cùng... Hoặc khi ta trình chiếu màn hình trên google meet và khi ta đang ở cửa sổ meet thì hiện tượng đệ quy cũng sẽ xảy ra.   Đệ quy trong khoa học máy tính và toán học rất quan trọng. Mặc dù là kiến thức cơ bản, tuy nhiên tính ứng dụng của nó vào các bài toán từ cơ bản tới nâng cao là rất cao, là nền tảng cần thiết để giúp chúng ta đi sâu vào các chiến lược xây dựng kĩ thuật như quay lui, chia để trị, quy hoạch động,... Vậy đệ quy là gì? Hãy cùng nhau tìm hiểu thông qua bài viết này nhé! # Đệ quy ## 1. Khái niệm > Ta gọi một đối tượng là đệ quy (recursion) nếu nó được định nghĩa qua chính nó hoặc một đối tượng cùng dạng với chính nó bằng quy nạp. Hay nói đơn giản hơn, trong tin học, đệ quy là một hàm tự gọi lại chính nó. ```cpp= // Đây là một hàm gọi đệ quy void f() { f(); } ``` Một bài toán mang tính chất đệ quy khi nó có thể được chia thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được chia thành các bài toán nhỏ hơn nữa theo cùng tính chất đó. Một bài toán đệ quy gồm có $2$ phần: - **Phần neo / trường hợp cơ sở / bài toán nhỏ nhất:** Đây là phần có thể giải trực tiếp mà không cần chia ra các bài toán con nào, và cũng là điểm dừng của bài toán đệ quy. - **Phần đệ quy:** Đây là phần mà chúng ta phải chia ra các bài toán con để giải, khi ta có được lời giải cho bài toán con thì khi đó chúng ta sẽ dựa vào kết quả bài toán con đó để giải cho bài toán cha. Phần này sẽ được thực hiện cho đến khi nào bài toán được đưa đến trường hợp cơ sở. Chúng ta hãy cùng đi đến các bài toán ví dụ để hình dung về tư tưởng đệ quy: ## 2. Bài tập ví dụ ### 2.1. Tính tổng - **Bài toán:** Tính tổng các số từ $1$ đến $n$ - **Phân tích:** Xét phần [1.](

1-Khái-niệm), chúng ta có thể phân tích ra các thành phần của đệ quy như sau: - Gọi $f(n)$ là tổng các số từ $1$ đến $n$, ta có: $$ \begin{cases} f(n) = 1 & (n = 1) \; (1) \\ f(n) = f(n-1) + n & (n > 1) \; (2) \end{cases} $$ - Từ đây, ta thấy được $(1)$ chính là trường hợp cơ sở và $(2)$ chính là phần đệ quy. - Code mẫu ```cpp= int f(int n) { if (n == 1) return 1; // trường hợp cơ sở return f(n - 1) + n; // phần đệ quy } ``` - **Độ phức tạp:** Chúng ta hãy thử phân tích độ phức tạp của code trên. Ta thấy rằng khi ta gọi $f(n)$ thì $f(n)$ lại gọi hàm $f(n - 1)$ và cứ tương tự như vậy tới khi $f(1)$ thì ta sẽ trả ra $1$. Vậy số lần gọi hàm $f$ là $n$ lần. Vậy độ phức tạp của code trên là $O(n)$.  ### 2.2. Tính số fibonacci - **Bài toán:** Tìm số fibonacci thứ $n$. Một dãy số fibonacci là dãy mà mỗi số hạng bằng tổng $2$ số hạng liền trước của nó. Các số đầu tiên của dãy fibonacci là $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...$ - **Phân tích:** Dựa vào yêu cầu đề đã cho, chúng ta có thể phân tích bài toán về dạng như sau: - Gọi $f(n)$ là số fibonacci thứ $n$. Vậy để tìm được $f(n)$ thì ta cần tìm $f(n-1)$ và $f(n-2)$ ($2$ số fibonacci liền trước). Tuy nhiên với $f(1)$ và $f(2)$ chúng ta không có số fibonacci đằng trước nên có thể coi đây là $2$ trường hợp cơ sở. Viết một cách toán học là: $$ \begin{cases} f(n) = 0 & (n = 1) \\ f(n) = 1 & (n = 2) \\ f(n) = f(n - 1) + f(n - 2) & (n > 1) \end{cases} $$ - Code mẫu ```cpp= int f(int n) { if (n == 1) return 0; // trường hợp cơ sở 1 if (n == 2) return 1; // trường hợp cơ sở 2 return f(n - 1) + f(n - 2); // phần đệ quy } ``` - **Độ phức tạp:** Chúng ta hãy cùng tính toán độ phức tạp của đoạn code trên. - Gọi $T(n)$ là số phép tính toán khi gọi hàm $f(n)$, ta có: $T(n) = T(n - 1) + T(n - 2) + O(1)$ $< 2T(n - 1) + O(1)$ $< 4T(n - 2) + 3O(1)$ $...$ $< 2^k*T(n - k) + (2^k - 1)*O(1)$ $...$ $< 2^n*T(1) + (2^n - 1)*O(1)$ $= O(2^n)$  Đương nhiên, không phải bài toán nào chúng ta cũng có thể nhìn ra một công thức đệ quy đơn giản như vậy. Đôi khi có những bài còn không có một công thức cụ thể, chỉ đơn thuần là giữa bài toán con và bài toán cha có điểm tương đồng nhau thôi. Vậy để giải quyết những bài toán như vậy chúng ta cần phải trả lời những câu hỏi sau: - Bài toán có thể được giải qua những bài toán con tương tự hay không? (Nói cách khác, bài toán có thể chia nhỏ thành các bài toán con hay không?) - Việc chia nhỏ bài toán con sẽ dừng khi nào? ## 3. Lí do dùng đệ quy Ưu điểm dễ thấy nhất khi dùng đệ quy đó chính là viết code ngắn gọn hơn. Tuy nhiên với những bài toán lớn như sinh cấu hình nhị phân thì việc dùng đệ quy lại rất cồng kềnh. Một ưu điểm khác của đệ quy giúp giải dễ dàng các bài toán có dạng một phần nhỏ hơn của công việc cộng thêm một vài lệnh khác, ví dụ như các bài toán duyệt cây và đồ thị. Tất nhiên, đệ quy không phải công cụ toàn năng. Đệ quy làm cho thuật toán trở nên khó hiểu hơn khi đọc trực tiếp, đặc biệt là với những thuật toán dài. Đệ quy cũng sử dụng thời gian và bộ nhớ hơn so với phương pháp duyệt trực tiếp, do bộ nhớ cần phải lưu trữ lại stack các hàm đệ quy. # Phương pháp quay lui ## 1. Giới thiệu Phương pháp quay lui là một phương pháp giải quyết bài toán thông qua việc thử tất cả các lựa chọn có thể, và nếu một lựa chọn dẫn đến giải pháp không thỏa mãn, thuật toán sẽ quay lui để thử các lựa chọn khác. Nó là một phương pháp để giải quyết các bài toán với mục đích tối ưu độ phức tạp hoặc ứng dụng trong các bài toán tìm kiếm hoặc liệt kê tất cả các giải pháp có thể. ## 2. Khái niệm: Quay lui là một phương pháp được thiết kế dựa trên đệ quy với ý tưởng: Tại mỗi bước, ta sẽ tìm một lời giải hợp lí cho bước đó rồi tiếp tục xét đến bước tiếp theo. ## 3. Ý tưởng Dưới đây là các bước chính của thuật toán quay lui: ***1. Khởi tạo:*** Bắt đầu và chuẩn bị dữ liệu cần thiết. ***2. Tìm kiếm:*** Duyệt qua tất cả các lựa chọn có thể tại mỗi bước. Điều này có thể liên quan đến việc thử tất cả các giá trị có thể cho một biến hoặc thử tất cả các hướng đi có thể trong một mê cung. ***3. Kiểm tra điều kiện dừng:*** Tại mỗi bước, kiểm tra xem liệu chúng ta đã tìm thấy lời giải (hoặc một số điều kiện khác) chưa. Nếu rồi, dừng thuật toán và trả về kết quả. ***4. Kiểm tra tính hợp lệ:*** Tại mỗi bước, kiểm tra xem lựa chọn hiện tại có thỏa mãn các ràng buộc và giới hạn không. Nếu không, quay lại bước trước đó (backtrack). ***5. Quay lại (Backtrack):*** Nếu lựa chọn hiện tại dẫn đến một tình huống không thỏa mãn hoặc đã kiếm tra hết tất cả các lựa chọn mà không tìm thấy lời giải, quay lại bước trước đó để thử các lựa chọn khác. ***6. Lặp lại:*** Lặp lại các bước 2 đến 5 cho đến khi tìm thấy lời giải hoặc xác định rằng không có lời giải. ### Nói một cách đơn giản: - Dùng để giải bài toán liệt kê các cấu hình (là một dãy gồm các nghiệm). Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng. Các bước trong việc liệt kê cấu hình dạng $X[1...n]$: + Xét tất cả các giá trị $X_1$ có thể nhận, thử $X_1$ nhận các giá trị đó. Với mỗi giá trị của $X_1$ ta sẽ: + Xét tất cả giá trị $X_2$ có thể nhận, lại thử $X_2$ cho các giá trị đó. Với mỗi giá trị $X_2$ lại xét khả năng giá trị của $X_3$,...tiếp tục như vậy cho tới bước: ... + Xét tất cả giá trị $X_n$ có thể nhận, thử cho $X_n$ nhận lần lượt giá trị đó.  **Code mẫu cho các bước trên** ```cpp= void Backtracking(int k) { for() { if () { ; if () { <Đưa ra kết quả>; } else { Backtracking(k+1); ; } } } } ``` ## 4. Bài tập ví dụ ### Bài toán sinh các dãy nhị phân #### Đề bài - Liệt kê tất cả các dãy nhị phân độ dài $n$, là dãy có tất cả $n$ ký tự và gồm toàn các ký tự $0$ và $1$. #### Dữ liệu nhập: - Gồm một số nguyên dương $n$ $(1 \le n \le 25)$. #### Kết quả: - Mỗi dòng in một dãy nhị phân độ dài n tìm được. Các dãy nhị phân in tăng dần theo thứ tự từ điển. #### Sample input 1: ``` 1 ``` #### Sample output 2: ``` 0 1 ``` #### Sample input 3: ``` 3 ``` #### Sample output 3: ``` 000 001 010 011 100 101 110 111 ``` #### Lời giải ::: spoiler Tự suy nghĩ trước khi coi lời giải nhé!  Tại hàm $gen(1)$, ta xét từng giá trị của ký tự hiện tại, sau đó gọi $gen(2)$ với từng ký tự đó. Tương tự như vậy, ta gọi $gen(3)$ từ các ký tự ở $gen(2)$ và rồi $gen(4)$. Tới $gen(4)$, ta đã duyệt hết các vị trí và không thể thử thêm nữa, nên có thể in ra xâu. ### Code tham khảo: ```cpp=

include using namespace std; int N,X[100]; void xuat() { for (int i=1;i<=N;i++) { cout << X[i]; } cout << endl; } void Try(int i) { //Duyet qua cac kha nang cua X[i] for (int j=0;j<=1;j++) { X[i] = j; if (i==N) { xuat(); } else { Try(i+1); } } } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N; Try(1); return 0; } ``` - Độ phức tạp: $O(2^n)$ ::: ## 6. Ưu điểm và nhược điểm ### Ưu điểm - Dễ hiểu và áp dụng. - Cho phép tìm kiếm tất cả các giải pháp có thể. ### Nhược điểm - Trong trường hợp xấu nhất độ phức tạp của quay lui là cấp số mũ. - Nguy cơ tràn bộ nhớ vì gọi đệ quy quá nhiều [(memory leak)](https://vi.wikipedia.org/wiki/Rò_rỉ_bộ_nhớ) # Kỹ thuật nhánh cận ## 1. Giới thiệu - Kỹ thuật nhánh và cận (Branch and bound) là một kỹ thuật tối ưu từ phương pháp quay lui, được sử dụng trong các bài toán tìm kết quả tốt nhất. ## 2. Ý tưởng 1. Giống như phương pháp quay lui, chúng ta sẽ vẫn biểu diễn các cấu hình nghiệm dưới dạng một tập $X = \{x_1, x_2, ..., x_n\}$ là tập con thuộc tập $S$. 2. Tuy nhiên ở bước này sẽ hơi khác phương pháp quay lui một tí. Nếu như ở quay lui, chúng ta chỉ đơn thuần là chọn các phần tử trong tập $S$ cho tới vị trí cuối cùng và liệt kê các tập đó ra, thì ở kỹ thuật này, mỗi tập $X$ sẽ được đánh giá bằng một hàm $f(X)$. Vì đây là một bài toán tối ưu, nên mục tiêu của chúng ta là đi tìm nghiệm có hàm $f(X)$ là tốt nhất. 3. Bước này cũng chính là đặc trưng của kỹ thuật nhánh cận và nó được tối ưu từ phương pháp quay lui. Giả sử bạn đã xây dựng được $i$ phần tử của tập là $X_i = \{x_1, x_2, ..., x_i\}$ và chuẩn bị thêm một phần tử vào tập $X_{i+1} = \{x_1, x_2, ..., x_i, x_{i+1}\}$. Nếu như bạn dự đoán trước được chính xác độ tốt của tập sau khi thêm $x_{i+1}, x_{i+2},...$ vào và biết được rằng độ tốt của tập $X = \{x_1, x_2, ..., x_i, x_{i+1},..., x_n\}$ không thể tốt hơn độ tốt của tập hiện tại $X_i$ thì ta sẽ không thêm $x_{i+1}$ vào tập $X_i$ nữa mà chúng ta sẽ chuyển qua chọn phần tử khác cho vị trí $i$ luôn. Từ đó sẽ giúp ta loại bỏ đi rất nhiều nhánh của phương pháp quay lui. Tuy nhiên ở kỹ thuật này, bước khó nhất là tìm ra cách để dự đoán trước được chính xác độ tốt của tập sau khi thêm $x_{i+1}, x_{i+2},...$ và chắc chắn rằng không thể có một kết quả tối ưu hơn sau đó. Vì thế khi áp dụng kỹ thuật này, chúng ta phải lưu ý cẩn thận để không xảy ra trường hợp bỏ sót kết quả.  **Code mẫu cho các bước trên** ```cpp= void branch_and_bound(int i) { if () { return; } if () return; for () { branch_and_bound(i + 1); } } ``` ## 3. Bài tập ví dụ ### Đề bài Ở một quốc gia có $n$ tờ tiền gồm các mệnh giá $a_1,a_2,…,a_n$. Có cách nào để lấy các tờ tiền sao cho tổng mệnh giá của chúng là $S$ và số tờ tiền đã lấy là ít nhất? ### Input - Dòng đầu tiên chứa 2 số nguyên dương $n, S$ $(1 \le n \le 20; 1 \le S \le 1000)$ - Dòng thứ hai chứa $n$ số $a_1,a_2,…,a_n$ phân tách nhau bởi dấu cách $(1 \le a_i \le 1000)$ ### Output - Nếu như có thể trả số tiền $S$ thì in ra số tờ tiền ít nhất cần sử dụng, ngược lại in ra $-1$. ### Sample input ``` 10 390 200 10 20 20 50 50 50 50 100 100 ``` ### Sample output ``` 5 ``` ### Giải thích Có thể dùng các tờ tiền $\{20, 20, 50, 100, 200\}$ ### Lời giải ::: spoiler Tự suy nghĩ trước khi coi lời giải nhé! Ta sẽ quay lui để xây dựng các cấu hình dạng $(x_1, x_2, ..., x_n)$ và các giá trị của $x_i = 0/1$ với ý nghĩa $x_i = 0$ nếu tờ tiền thứ $i$ không được chọn, $x_i = 1$ nếu tờ tiền thứ $i$ được chọn. Bài toán sẽ trở về dạng như sau: $$ \begin{cases} a_1 \cdot x_1 + a_2 \cdot x_2 + ... + a_n \cdot x_n = S \\ x_1 + x_2 + ... + x_n \; \text{nhỏ nhất} \end{cases} $$ Giả sử ta đã xây dựng được dãy $(x_1, x_2, ..., x_i)$, tổng số tờ tiền chọn (hay $sum(x_1, x_2, ..., x_i)$) là $cnt$ và số tiền đã lấy là $sum$, ta có thể rút ra được nhận xét sau: - Số tiền còn lại cần lấy là $S - sum$ - Số tờ tiền ít nhất cần lấy thêm là $\frac{S - sum}{max(x_{i + 1}, ..., x_n)}$. Tức là tổng số tờ tiền cần lấy ít nhất của cấu hình này là $cnt\_cur = cnt$ + $\frac{S - sum}{max(x_{i + 1}, ..., x_n)}$. - Gọi số tờ tiền ít nhất cần lấy hiện tại là $cnt\_best$. Nếu $cnt\_cur \ge cnt\_best$, ta sẽ không cần phải mở rộng thêm dãy nghiệm từ $(x_1, x_2, ..., x_i)$ nữa. **Code mẫu** ```cpp=