# Đệ quy & chia để trị ## Đệ quy ### Call stack Trước hết, ta hãy cùng tìm hiểu về call stack. Trong các ngôn ngữ lập trình bậc cao, trình biên dịch sử dụng call stack để lưu lại thông tin về các chương trình con đang được thực thi, nhằm theo dõi chúng nên được trả về vị trí nào (câu lệnh nào) sau khi đã thực thi xong [(1)]( https://en.wikipedia.org/wiki/Call_stack). Nhờ có call stack, đoạn code của bạn mới được biên dịch & thực thi một cách hợp lí, đặc biệt là khi trong code của bạn có chứa hàm, chương trình con này gọi đến hàm, chương trình con khác, chồng chéo lên nhau, và trường hợp đặc biệt nhất là hàm đệ quy. Bạn có thể tham khảo một ví dụ ngắn gọn tại [đây](https://developer.mozilla.org/en-US/docs/Glossary/Call_stack) Nguyên lí hoạt động của call stack: - Khi bạn gọi một chương trình con, một số thông tin như (tham số, địa chỉ của câu lệnh gọi đến nó - 'return address', biến cục bộ, ...) sẽ được thêm vào stack - Khi một chương trình con được thực hiện xong, những thông tin của nó sẽ được đẩy ra khỏi stack, đồng thời trình biên dịch sẽ quay về return address và tiếp tục thực hiện những lệnh ở đằng sau ### Đệ quy Trước hết, hãy xem qua một số hình ảnh của đệ quy trong đời sống. ![](https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/375px-Sierpinski_triangle.svg.png) ![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Romanesco_broccoli_%28Brassica_oleracea%29.jpg/394px-Romanesco_broccoli_%28Brassica_oleracea%29.jpg) ![](https://images.theconversation.com/files/163337/original/image-20170330-4592-1n4ji0f.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=1200&h=1200.0&fit=crop) Đệ quy là một khái niệm rất cơ bản trong lập trình: một chương trình con tự gọi lại chính nó. Xét đoạn code C sau: ```cpp! void f() { f(); } ``` Đây là ví dụ đơn giản nhất về hàm 'đệ quy'. Chú ý rằng: mặc dù bằng mắt thường, chúng ta không thể phân biệt hàm `f()` ở ngoài, và hàm `f()` được gọi bên trong, vì chúng không có tham số; tuy nhiên, **địa chỉ câu lệnh** mà các hàm này được gọi là khác nhau. Vì thế trình biên dịch sẽ phân biệt được chính xác. ![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d3/Call_stack_layout.svg/513px-Call_stack_layout.svg.png) Trong ví dụ trên, các `f()` sẽ được thêm liên tục vào call stack. Vì bộ nhớ cho phép là hữu hạn nên chương trình của bạn sẽ bị ngắt khi nó sử dụng quá giới hạn bộ nhớ stack - lỗi stack overflow (trên các online judge sẽ hiện ra kết quả RTE hoặc WA) Vì thế, điều quan trọng nhất khi code hàm đệ quy là phải có **điều kiện dừng**. ```cpp int sum_1_to_n(int n) { if (n <= 0) return 0; return n + sum_1_to_n(n-1); } ``` ### Bài toán ví dụ #### Tìm số Fibonacci thứ $n$ Dãy số Fibonacci được định nghĩa như sau: $f(0) = 1$ $f(1) = 1$ $f(i) = f(i-1) + f(i-2) \forall i \ge 2$ Từ định nghĩa của dãy Fibonacci, ta có ngay đoạn code: ```cpp int fibo(int n) { if (n <= 1) return 1; return fibo(n-1) + fibo(n-2); } ``` #### Hệ thống file & thư mục ###### Duyệt theo chiều sâu - Depth-first search (DFS) [Link đọc đề & nộp bài](https://lqdoj.edu.vn/problem/directory) ##### Lời giải Nhận xét đơn giản: Đường dẫn tới $A$ = đường dẫn tới cha của $A$ $+$ **"/A"**. ```cpp vector<int> childs[N]; string path[N]; void traverse(int u) { for (auto v : childs[u]) { path[v] = path[u] + "/" + name[v]; traverse(v); } } ``` ## Chia để trị ### Tư tưởng Ý tưởng chung của phương pháp "Chia để trị" như sau: Để giải quyết bài toán A, ta sẽ: - <u>B1</u>: Nếu $A$ đủ đơn giản, có thể tìm ra nghiệm ngay thì kết thúc quá trình giải. - <u>B2</u> Ngược lại, ta sẽ phân rã bài toán $A$ thành những bài toán con $A_1, A_2, A_3, ..., A_k$. Những bài toán con này có cùng bản chất với bài toán $A$, nhưng các tham số sẽ nhỏ hơn - <u>B3</u> Tiến hành giải từng bài toán con $A_1, A_2, ..., A_k$ (quay lại <u>B1</u> với mỗi bài toán con) - <u>B4</u> Tổng hợp lời giải của $k$ bài toán con để có được lời giải cho bài toán $A$. Như vậy, quá trình giải bài toán sẽ như sau: Ta sẽ phân rã một vấn đề ra cho tới khi nó thành những phần đơn giản nhất, dễ dàng tìm ra nghiệm - tạm gọi là các "nguyên tử". Từ những "nguyên tử" này, ta dần dần tổng hợp nên lời giải của bài toán muốn giải quyết. Tư tưởng của "Chia để trị" rất gần với "Đệ quy". Từ ý tưởng, ta dễ dàng chuyển qua mô hình code như sau: ```cpp struct Solution {}; struct Problem {}; Solution solve(Problem a) {}; //giải những bài đủ đơn giản Solution divide_and_conquer(Problem a) { if (a is small) return solve(a); subproblems = {}; Partion a into subproblems; solutions = {}; for (int i = 1; i <= num_problems; i++) { solutions[i] = divide_and_conquer(subproblems[i]); } Solution result; Combine solutions to result; return result; } ``` ### Bài toán #### Tính $a^b \mod n$ ##### Cày trâu Khởi tạo một biến kết quả `res = 1` và nhân $a$ vào kết quả $b$ lần. Độ phức tạp $O(b)$ ##### Thuật tốt hơn Quan sát: + $a^0 = 1 (\mod n)$ + $a^x . a^y = a^{x+y} (\mod n)$ Do đó, nếu ta có kết quả của $a^x \mod n$ và $a^{b-x} \mod n$ thì sẽ tính được $a^b \mod n$. Ta định nghĩa một hệ thức truy hồi như sau: - $a^0 = 1 (\mod n)$ - $a^b = a^{b-1} . a (\mod n)$ với $b$ lẻ - $a^b = (a^{b/2})^2 (\mod n)$ với $b$ chẵn Code C++: ```cpp long long pwr(int a, int b, int n) { if (b == 0) return 1; if (b%2 == 0) { long long res = pwr(a, b/2, n); return res*res % n; } return pwr(a,b-1,n) * (1LL * a) % n; } ``` Phân tích độ phức tạp: Để tính được $a^b$ từ $a^{b \div 2}$, ta cần tối đa $2$ phép tính nhân (khi $b$ là số lẻ). Trường hợp tệ nhất là khi $b = 2^k - 1$, lúc này ta cần sử dụng đúng $2k$ phép tính nhân (và modulo). ĐPT là $O(log_2(b))$ #### Tháp Hà Nội Tháp Hà Nội là một trò chơi toán học thú vị của cha ông ta, được người Pháp đem về nghiên cứu và phổ biến cho toàn thế giới [(2)](https://vi.wikipedia.org/wiki/Th%C3%A1p_H%C3%A0_N%E1%BB%99i) Luật chơi như sau: - Ban đầu có 3 cột thẳng đứng trên một đế nằm ngang - Người ta đặt $n$ chiếc đĩa (đục lỗ ở tâm) vào cột thứ nhất, tạo thành một "tháp". Toàn bộ chiếc đĩa này có kích thước khác nhau, và được sắp theo thứ tự: đĩa có kích thước lớn hơn sẽ được đặt vào trước. ![](https://upload.wikimedia.org/wikipedia/commons/thumb/0/07/Tower_of_Hanoi.jpeg/450px-Tower_of_Hanoi.jpeg) - Tại mỗi bước, bạn được phép chuyển một đĩa nằm ở trên cùng của một cột để chuyển qua cột khác. - Tại mọi thời điểm, phải đảm bảo không có đĩa có kích thước lớn hơn nằm trên đĩa có kích thước nhỏ hơn - Hỏi bạn có thể đưa toàn bộ $n$ đĩa qua cột thứ 3 trong thời gian ngắn nhất là bao nhiêu nước đi? Đi như thế nào? [Link nộp bài tập](https://lqdoj.edu.vn/problem/cses2165) ##### Lời giải Các trường hợp $n \le 4$ đều đủ đơn giản để tự thử nghiệm, tìm lời giải hợp lí. Quan sát: Vì đĩa lớn hơn không được đặt lên đĩa nhỏ hơn, nên đĩa ở dưới đáy (kích thước lớn nhất) chỉ có thể được chuyển qua một cột trống. Do đó, nếu ta có cách nào đó chuyển được $n-1$ đĩa ở trên qua cột ở giữa, thì ta có thể đưa đĩa lớn nhất về đúng vị trí. Đến đây, ta nhận thấy vấn đề cần giải quyết đã được phân tích & quy về những vấn đề tương tự, nhưng kích thước nhỏ hơn, cụ thể là: "Nếu tôi có cách chuyển $n-1$ đĩa, tôi chắc chắn sẽ chuyển được $n$ đĩa". Chúng ta sẽ mô hình hóa vấn đề trên: ```cpp void solve(int n, int a, int b); ``` Hàm trên sẽ in ra các thao tác để di chuyển $n$ đĩa ở trên cùng của cột $a$ sang cột $b$. Lời giải như sau: ```cpp void solve(int n, int a, int b) { if (n == 1) { cout << a << ' ' << b << endl; } else { int mid = (1+2+3) - (a+b); //chỉ số cột trung gian solve(n-1, a, mid); cout << a << ' ' << b << endl; solve(n-1, mid, b); } } ``` #### Sắp xếp trộn Mục tiêu: sắp xếp dãy $a$ gồm $n \le 10^5$ phần tử cho trước theo thứ tự tăng dần. Tư tưởng: Để sắp xếp dãy $a$, ta sẽ chia nó thành 2 dãy con, và tiến hành sắp xếp 2 dãy con này. Từ 2 dãy con đã được sắp xếp, ta "trộn" lại để được $a$ tăng dần. Code: ```cpp vector<int> merge_sort(int l, int r) { if (l == r) return vector<int>({a[l]}); int m = (l+r)/2; vector<int> left_sorted = merge_sort(l,m); vector<int> right_sorted = merge_sort(m+1,r); vector<int> result(r-l+1); merge(left_sorted.begin(), left_sorted.end(), right_sorted.begin(), right_sorted.end(), result.begin()); return result; } ``` Đánh giá độ phức tạp: Chi phí của hàm `merge` là $O(r-l+1)$ Đặt $T(n)$ là chi phí tính toán của hàm `merge_sort` với dãy có kích thước $n$. Ta có: $T(1) = 0$ $T(n) = 2.T(n/2) + n$ Trong trường hợp $n = 2^k, T(n) = n.k$. Vì vậy độ phức tạp là $O(n.\log_2(n))$ #### Cây phân đoạn - Segment Tree Có thể nói đây là một trong những ứng dụng được dùng nhiều nhất của nguyên lý "Chia để trị". Ở cấu trúc dữ liệu cây phân đoạn, mỗi nút trên cây sẽ quản lí đoạn $[l..r]$ của mảng. Nếu $l < r$, nó sẽ có 2 nút con, quản lí 2 đoạn con là nửa bên trái và nửa bên phải của $[l..r]$ (là $[l..m]$ và $[m+1..r]$). Mỗi nút sẽ lưu các thông tin cần thiết cho bài toán + Giá trị tại nút lá sẽ dễ tính được + Giá trị tại một nút sẽ được tổng hợp từ giá trị của 2 nút con Vì cấu trúc này là một cây nhị phân nên thao tác cập nhật hoặc truy vấn đều rất hiệu quả. Trong phạm vi của bài viết này, tôi sẽ không đi sâu vào Segment tree. Bạn đọc có thể tìm hiểu thêm tại: - Tài liệu giáo khoa chuyên Tin - https://vnoi.info/wiki/algo/data-structures/segment-tree-basic.md #### Lát nền Nguồn bài & lời giải: [Tài liệu giáo khoa chuyên Tin quyển 1](https://drive.google.com/file/d/0BwcTB8a10LBweWxNcExnVzF5dG8/view?resourcekey=0-WKR6p7r5Djmi--uvQnT-pg), mục 4.4, trang 93. Nhận xét: Khác với một số ví dụ ở trên (chia đôi kích thước bài toán), ở bài tập này, mỗi bài toán đã được chia thành 4 bài toán con. Bản chất của bài toán gốc và các bài toán con là giống nhau (phần nền cần lát có dạng hình vuông khuyết một góc phần tư) nên giải được bằng chia để trị.