Look up base case in Wiktionary, the free dictionary.
Base case may refer to:
- Base case [recursion], the terminating scenario in recursion that does not use recursion to produce an answer
- Base case [induction], the basis in mathematical induction, showing that a statement holds for the lowest possible value of n
This disambiguation page lists articles associated with the title Base case.
If an internal link led you here, you may wish to change the link to point directly to the intended article.
Retrieved from "//en.wikipedia.org/w/index.php?title=Base_case&oldid=826725632"
Bài viết sẽ trình bày về khái niệm đệ quy, cấu trúc của một chương trình đệ quy, cách máy tính thực thi chương trình đệ quy như thế nào
1. Đệ quy là gì?
Thử tìm kiếm từ khóa "recursion" [hay "đệ quy"] trên Google thử nhé! Kết quả bạn thu được như sau:
Có thể lần đầu tiên khi thấy dòng chữ "Có phải bạn muốn tìm" bạn sẽ suy nghĩ rằng mình đã gõ sai chính tả đâu đó, bạn click vào từ khóa "recursion" mà Google đề xuất. Nhưng kết quả bạn thu được vẫn thế, dòng chữ "Có phải bạn muốn tìm" vẫn tiếp tục hiện ra. Thực ra đây cũng là một ví dụ của đệ quy. Đệ quy xảy ra khi một sự vật được định nghĩa theo chính nó hoặc thuộc loại của nó. Ví dụ chúng ta có thể định nghĩa số tự nhiên như sau:
- 0 là số tự nhiên.
- n là số tự nhiên nếu [n-1] là số tự nhiên.
Trong định nghĩa trên ta thấy rằng trong định nghĩa số tự nhiên lại dùng định nghĩa số tự nhiên, đây chính là đệ quy. Trong lập trình, đệ quy có nghĩa là hàm gọi lại chính nó trong thân hàm.
void Recursion[] { .... Recursion[]; .... }2. Cấu trúc một chương trình đệ quy
Một chương trình đệ quy thông thường sẽ có cấu trúc như sau:
{ if[điều kiện dừng đệ quy] // phần cơ sở // Làm gì đó else { .... // Thực hiện gọi đệ quy .... } }Một ví dụ của đệ quy là việc tính giai thừa bởi lẽ trong định nghĩa của giai thừa cũng có chứa yếu tố đệ quy:
- 0! = 1! = 1
- n! = n*[n-1]!
Code của hàm tính giai thừa có thể được viết như sau:
int fact[int n] { if [n == 0 || n == 1] return 1; return n * fact[n - 1]; }Qua ví dụ trên ta có thể thấy rằng một trong những ưu điểm của đệ quy đó là code rất dễ hiểu cho người đọc vì nó rất sát với công thức truy hồi mà chúng ta tìm ra. Sơ đồ gọi hàm với n = 5 có thể được diễn tả như hình sau:
3. Một chương trình đệ quy sẽ hoạt động như thế nào?
Đây là ý mà mình muốn nhấn mạnh trong bài viết lần này. Một trong những câu nói đùa của dân lập trình viên với nhau đó là muốn hiểu đệ quy là gì trước hết phải hiểu đệ quy là gì,... Tuy nhiên, theo mình muốn hiểu được cơ chế hoạt động của chương trình đệ quy ta cần phải hiểu được luồng chạy và cơ chế lưu stack của chương trình, chương trình đệ quy sẽ kết thúc quá trình hoạt động của nó khi không còn câu lệnh nào được thực hiện và stack đã rỗng. Nói về stack thì sau lệnh gọi đệ quy, các câu lệnh chưa được thực thi dưới đó sẽ được lưu vào stack [theo nguyên tắc LIFO - Last In First Out] với các giá trị biến và tham số hiện hành. Bên cạnh đó, có 3 câu hỏi mà mình nghĩ các bạn nên suy nghĩ trước khi sử dụng đệ quy cho một vấn đề, đó là:
- Phần cơ sở [base case] của chương trình là gì?
- Phần đệ quy của chương trình là gì?
- Với phần đệ quy như vậy liệu trong quá trình thực thi chương trình có đạt được về phần cơ sở để giải quyết vấn đề hay không? Bởi nếu không chương trình sẽ gặp hiện tượng tràn stack [stack overflow].
Một trong những bài toán kinh điển có thể được giải quyết bởi đệ quy là bài toán tháp Hà Nội.
[Link ảnh: //genk.mediacdn.vn/2017/photo-1-1488855314632.png]
Giả thiết đề bài là có n đĩa ở cột 1[các đĩa từ dưới lên trên được xếp theo quy tắc từ lớn đến nhỏ] cần chuyển hết sang cột 2 với các quy tắc sau:
- Mỗi lần chỉ được di chuyển 1 đĩa.
- Các đĩa lớn không được đặt trên các đĩa nhỏ.
- Có thể dùng cột 3 làm cột trung gian trong quá trình chuyển đĩa.
Ý tưởng của bài toán như sau:
- Nếu chỉ có 1 đĩa ở cột 1 ta chỉ đơn giản là chuyển đĩa đó từ cột 1 sang cột 2 [base case].
- Nếu số đĩa lớn hơn 1 việc ta cần làm chia ra 3 bước như sau:
- Chuyển n - 1 đĩa từ cột 1 sang cột 3, lấy cột 2 làm trung gian [phần đệ quy].
- Chuyển 1 đĩa từ cột 1 sang cột 2.
- Chuyển n - 1 đĩa từ cột 3 sang cột 2, lấy cột 1 làm trung gian [phần đệ quy].
Đoạn code giải quyết vấn đề trên có thể được viết như sau:
void HaNoiTower[int n, int a, int b, int c] { if [n == 1] cout