- 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. ![][//hackmd.io/_uploads/H1PPNoqW6.png] ![][//hackmd.io/_uploads/SyfsEs9Za.png] Đệ 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]$. ![][//hackmd.io/_uploads/rymSQa5WT.png] ### 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]$ ![][//hackmd.io/_uploads/HJppJFZfT.png] Đươ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ị đó. ![][//hackmd.io/_uploads/HJhu48bfT.png] **Code mẫu cho các bước trên** ```cpp= void Backtracking[int k] { for[] { if [] { ; if [] { ; } 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é! ![][//hackmd.io/_uploads/r15qaHbzT.png] 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= cnt_best] return; // 0: không chọn; 1: chọn for [int j = 0; j > n >> S; for [int i = 1; i > a[i]; for [int i = n; i >= 0; i--] a_max[i] = max[a_max[i + 1], a[i]]; // a_max[i] = max[a[i], ..., a[n]] cnt_best = n + 1; // ban đầu chưa có phương án nào nên đặt cnt_best = n + 1 branch_and_bound[1]; // trong trường hợp không có phương án nào thoả mãn ta in ra -1 if [cnt == n + 1] cout > S; for [int i = 1; i > a[i]; cout M$ thì ta chỉ có thể bỏ qua đồ vật $n$ và đi tiếp tới đồ vật tiếp theo mà thôi. Đệ quy sẽ dừng khi đi tới điểm bên ngoài của dãy. **Code mẫu** ```cpp=

include using namespace std; long long V[41], W[41]; long long f[int n, long long M] { if [n == 0] return 0; if [W[n] > n >> M; for [int i = 1; i > W[i] >> V[i]; cout