Đây là một quyển sách toán lớp 3, ở trong bìa sách có ba học sinh, trong đó có một học sinh lại cầm một quyển sách toán lớp ba khác. Và trong quyển sách đó lại có ba học sinh, và cũng có một học sinh cầm một quyển sách lớp 3. Đây chính là ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào - khái niệm "đệ quy". Show  Đệ quy là gì ?Đệ quy có nghĩa là một hàm tự gọi lại chính nó. Ví dụ: void hello(int count) { count++; if (count <= 5) { printf("hello %d\n", count); hello(count); } }Thành phần của một hàm đệ quy.Một hàm đệ quy gồm 2 phần:
Ví dụ: void hello(int count) { count++; if (count <= 5) // điều kiện dừng { printf("hello %d\n", count); hello(count); } }Như ví dụ trên, nếu chúng ta không cài đặt điều kiện dừng thì chương trình sẽ chạy mãi mãi. Bộ nhớ Stack.Nguyên tắc hoạt động của bộ nhớ Stack là LIFO (Last in - First out hay còn gọi là vào sau - ra trước ). Khi một biến được khai báo trong hàm, nó sẽ được đẩy vào Stack, khi hàm đó kết thúc thì tất cả những biến đó sẽ được đẩy ra, giải phóng khỏi Stack. Hình dưới là minh họa cách hoạt động của bộ nhớ Stack. Ưu điểm:Thuận lợi cho việc biểu diễn bài toán, như ở ví dụ trên, nhìn vào hàm là chúng ta có thể thấy ngay nó biểu diễn dãy số fibonacci, hay tính giai thừa. Nhược điểm:Tốn nhiều bộ nhớ, nếu không phần cơ sở ( điểm dừng) thì sẽ gây ra việc tràn bộ nhớ stack. Bên cạnh đó việc sử dụng đệ quy tốn nhiều thời gian hơn vòng lặp. Các ví dụ.Tính tổng các số từ 1 đến n. #include <stdio.h> int sum(int n){ if(n == 0) // điều kiện dừng (phần cơ sở) return 0; return n + sum(n-1); } int main(){ int sum = sum(5); printf("Sum = %d", sum); }Kết quả.
Giải thích hàm đệ quy Với n = 5 5 + sum(4) 5 + 4 + sum(3) 5 + 4 + 3 + sum(2) 5 + 4 + 3 + 2 + sum(1) 5 + 4 + 3 + 2 + 1 + 0 Dãy Fibonacci. #include <stdio.h> int fibonacci(int n) { if ((n == 1) || (n == 2)) return 1; return fibonacci(n-1) + fibonacci(n-2); } int main() { printf("%d", fibonacci(30)); } Kết quả. Tính giai thừa #include <stdio.h> int factorial(int n) { if (n == 1) return 1; else return factorial(n-1)*n; } int main() { printf("%d", factorial(5)); }Kết quả. Tạm kếtĐệ quy là một phương pháp cơ bản trong kỹ thuật lập trình. Trong lập trình Web hay Winform thường thì không sử dụng đệ quy nhưng nên học kỹ thuật này, vì nó không quá khó để nắm bắt. Việc sử dụng đệ quy vào các bài toán thì nên cân nhắc, mặc dù đệ quy khiến code chúng ta dễ đọc, nhưng rất khó cho việc debug. Trên đây là khái niệm về đệ quy, hy vọng giúp ích cho mọi người mới tìm hiểu về kỹ thuật này, nếu có câu hỏi hay góp ý gì thì hãy bình luận ở bên dưới nhé. Chúc mọi người học tốt. Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó bằng quy nạp. Ví dụ: Đặt hai chiếc gương cầu đối diện nhau. Trong chiếc gương thứ nhất chứa hình chiếc gương thứ hai. Chiếc gương thứ hai lại chứa hình chiếc gương thứ nhất nên tất nhiên nó chứa lại hình ảnh của chính nó trong chiếc gương thứ nhất… Ở một góc nhìn hợp lý, ta có thể thấy một dãy ảnh vô hạn của cả hai chiếc gương. Một ví dụ khác là nếu người ta phát hình trực tiếp phát thanh viên ngồi bên máy vô tuyến truyền hình, trên màn hình của máy này lại có chính hình ảnh của phát thanh viên đó ngồi bên máy vô tuyến truyền hình và cứ như thế… Trong toán học, ta cũng hay gặp các định nghĩa đệ quy: Giai thừa của n (n!): Nếu n = 0 thì n! = 1; nếu n > 0 thì n! = n.(n-1)! Ký hiệu số phần tử của một tập hợp hữu hạn S là |S|: Nếu S = Ø thì |S| = 0; Nếu S ≠ Ø thì tất có một phần tử x ϵ S, khi đó |S| = |S\{x}| + 1. Đây là phương pháp định nghĩa tập các số tự nhiên. GIẢI THUẬT ĐỆ QUYNếu lời giải của một bài toán P được thực hiện bằng lời giải của bài toán P' có dạng giống như P thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy. Mới nghe thì có vẻ hơi lạ nhưng điểm mấu chốt cần lưu ý là: P' tuy có dạng giống như P, nhưng theo một nghĩa nào đó, nó phải "nhỏ" hơn P, dễ giải hơn P và việc giải nó không cần dùng đến P. Trong Pascal, ta đã thấy nhiều ví dụ của các hàm và thủ tục có chứa lời gọi đệ quy tới chính nó, bây giờ, ta tóm tắt lại các phép đệ quy trực tiếp và tương hỗ được viết như thế nào: Định nghĩa một hàm đệ quy hay thủ tục đệ quy gồm hai phần: Phần neo (anchor): Phần này được thực hiện khi mà công việc quá đơn giản, có thể giải trực tiếp chứ không cần phải nhờ đến một bài toán con nào cả. Phần đệ quy: Trong trường hợp bài toán chưa thể giải được bằng phần neo, ta xác định những bài toán con và gọi đệ quy giải những bài toán con đó. Khi đã có lời giải (đáp số) của những bài toán con rồi thì phối hợp chúng lại để giải bài toán đang quan tâm. Phần đệ quy thể hiện tính "quy nạp" của lời giải. Phần neo cũng rất quan trọng bởi nó quyết định tới tính hữu hạn dừng của lời giải. VÍ DỤ VỀ GIẢI THUẬT ĐỆ QUYfunction Factorial(n: Integer): Integer; {Nhận vào số tự nhiên n và trả về n!} begin if n = 0 then Factorial := 1 {Phần neo} else Factorial := n * Factorial(n - 1); {Phần đệ quy} end; Ở đây, phần neo định nghĩa kết quả hàm tại n = 0, còn phần đệ quy (ứng với n > 0) sẽ định nghĩa kết quả hàm qua giá trị của n và giai thừa của n - 1. Ví dụ: Dùng hàm này để tính 3!, trước hết nó phải đi tính 2! bởi 3! được tính bằng tích của 3 * 2!. Tương tự để tính 2!, nó lại đi tính 1! bởi 2! được tính bằng 2 * 1!. Áp dụng bước quy nạp này thêm một lần nữa, 1! = 1 * 0!, và ta đạt tới trường hợp của phần neo, đến đây từ giá trị 1 của 0!, nó tính được 1! = 1*1 = 1; từ giá trị của 1! nó tính được 2!; từ giá trị của 2! nó tính được 3!; cuối cùng cho kết quả là 6: 3! = 3 * 2! ↓ 2! = 2 * 1! ↓ 1! = 1 * 0! ↓ 0! = 1 Dãy số FibonacciDãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán đặt ra như sau:
Giữa tháng thứ 1:1 cặp (ab) (cặp ban đầu) Giữa tháng thứ 2:1 cặp (ab) (cặp ban đầu vẫn chưa đẻ) Giữa tháng thứ 3:2 cặp (AB)(cd) (cặp ban đầu đẻ ra thêm 1 cặp con) Giữa tháng thứ 4:3 cặp (AB)(cd)(ef) (cặp ban đầu tiếp tục đẻ) Giữa tháng thứ 5:5 cặp (AB)(CD)(ef)(gh)(ik) (cả cặp (AB) và (CD) cùng đẻ) Bây giờ, ta xét tới việc tính số cặp thỏ ở tháng thứ n: F(n) Nếu mỗi cặp thỏ ở tháng thứ n - 1 đều sinh ra một cặp thỏ con thì số cặp thỏ ở tháng thứ n sẽ là: F(n) = 2 * F(n - 1) Nhưng vấn đề không phải như vậy, trong các cặp thỏ ở tháng thứ n - 1, chỉ có những cặp thỏ đã có ở tháng thứ n - 2 mới sinh con ở tháng thứ n được thôi. Do đó F(n) = F(n - 1) + F(n - 2) (= số cũ + số sinh ra). Vậy có thể tính được F(n) theo công thức sau: F(n) = 1 nếu n ≤ 2 F(n) = F(n - 1) + F(n - 2) nếu n > 2 function F(n: Integer): Integer; {Tính số cặp thỏ ở tháng thứ n} begin if n £ 2 then F := 1 {Phần neo} else F := F(n - 1) + F(n - 2); {Phần đệ quy} end; Giả thuyết của CollatzCollatz đưa ra giả thuyết rằng: với một số nguyên dương X, nếu X chẵn thì ta gán X := X div 2; nếu X lẻ thì ta gán X := X * 3 + 1. Thì sau một số hữu hạn bước, ta sẽ có X = 1. Ví dụ: X = 10, các bước tiến hành như sau:
Cứ cho giả thuyết Collatz là đúng đắn, vấn đề đặt ra là: Cho trước số 1 cùng với hai phép toán * 2 và div 3, hãy sử dụng một cách hợp lý hai phép toán đó để biến số 1 thành một giá trị nguyên dương X cho trước. Ví dụ: X = 10 ta có 1 * 2 * 2 * 2 * 2 div 3 * 2 = 10. Dễ thấy rằng lời giải của bài toán gần như thứ tự ngược của phép biến đổi Collatz: Để biểu diễn số X > 1 bằng một biểu thức bắt đầu bằng số 1 và hai phép toán "* 2", "div 3". Ta chia hai trường hợp: Nếu X chẵn, thì ta tìm cách biểu diễn số X div 2 và viết thêm phép toán * 2 vào cuối Nếu X lẻ, thì ta tìm cách biểu diễn số X * 3 + 1 và viết thêm phép toán div 3 vào cuối procedure Solve(X: Integer); {In ra cách biểu diễn số X} begin if X = 1 then Write(X) {Phần neo} else {Phần đệ quy} if X mod 2 = 0 then {X chẵn} begin Solve(X div 2); {Tìm cách biểu diễn số X div 2} Write(' * 2'); {Sau đó viết thêm phép toán * 2} end else {X lẻ} begin Solve(X * 3 + 1); {Tìm cách biểu diễn số X * 3 + 1} Write(' div 3'); {Sau đó viết thêm phép toán div 3} end; end; Trên đây là cách viết đệ quy trực tiếp, còn có một cách viết đệ quy tương hỗ như sau: procedure Solve(X: Integer); forward; {Thủ tục tìm cách biểu diễn số X: Khai báo trước, đặc tả sau} procedure SolveOdd(X: Integer); {Thủ tục tìm cách biểu diễn số X > 1 trong trường hợp X lẻ} begin Solve(X * 3 + 1); Write(' div 3'); end; procedure SolveEven(X: Integer); {Thủ tục tìm cách biểu diễn số X trong trường hợp X chẵn} begin Solve(X div 2); Write(' * 2'); end; procedure Solve(X: Integer); {Phần đặc tả của thủ tục Solve đã khai báo trước ở trên} begin if X = 1 then Write(X) else if X mod 2 = 1 then SolveOdd(X) else SolveEven(X); end; Trong cả hai cách viết, để tìm biểu diễn số X theo yêu cầu chỉ cần gọi Solve(X) là xong. Tuy nhiên trong cách viết đệ quy trực tiếp, thủ tục Solve có lời gọi tới chính nó, còn trong cách viết đệ quy tương hỗ, thủ tục Solve chứa lời gọi tới thủ tục SolveOdd và SolveEven, hai thủ tục này lại chứa trong nó lời gọi ngược về thủ tục Solve. Đối với những bài toán nêu trên, việc thiết kế các giải thuật đệ quy tương ứng khá thuận lợi vì cả hai đều thuộc dạng tính giá trị hàm mà định nghĩa quy nạp của hàm đó được xác định dễ dàng. Nhưng không phải lúc nào phép giải đệ quy cũng có thể nhìn nhận và thiết kế dễ dàng như vậy. Thế thì vấn đề gì cần lưu tâm trong phép giải đệ quy?. Có thể tìm thấy câu trả lời qua việc giải đáp các câu hỏi sau:
Bài toán Tháp Hà Nội Đây là một bài toán mang tính chất một trò chơi, tương truyền rằng tại ngôi đền Benares có ba cái cọc kim cương. Khi khai sinh ra thế giới, thượng đế đặt n cái đĩa bằng vàng chồng lên nhau theo thứ tự giảm dần của đường kính tính từ dưới lên, đĩa to nhất được đặt trên một chiếc cọc. Tháp Hà Nội Các nhà sư lần lượt chuyển các đĩa sang cọc khác theo luật:
Ngày tận thế sẽ đến khi toàn bộ chồng đĩa được chuyển sang một cọc khác. Trong trường hợp có 2 đĩa, cách làm có thể mô tả như sau: Chuyển đĩa nhỏ sang cọc 3, đĩa lớn sang cọc 2 rồi chuyển đĩa nhỏ từ cọc 3 sang cọc 2. Những người mới bắt đầu có thể giải quyết bài toán một cách dễ dàng khi số đĩa là ít, nhưng họ sẽ gặp rất nhiều khó khăn khi số các đĩa nhiều hơn. Tuy nhiên, với tư duy quy nạp toán học và một máy tính thì công việc trở nên khá dễ dàng: Có n đĩa.
Cách làm đó được thể hiện trong thủ tục đệ quy dưới đây: procedure Move(n, x, y: Integer); {Thủ tục chuyển n đĩa từ cọc x sang cọc y} begin if n = 1 then WriteLn('Chuyển 1 đĩa từ ', x, ' sang ', y) else {Để chuyển n > 1 đĩa từ cọc x sang cọc y, ta chia làm 3 công đoạn} begin Move(n - 1, x, 6 - x - y); {Chuyển n - 1 đĩa từ cọc x sang cọc trung gian} Move(1, x, y); {Chuyển đĩa to nhất từ x sang y} Move(n - 1, 6 - x - y, y); {Chuyển n - 1 đĩa từ cọc trung gian sang cọc y} end; end; Chương trình chính rất đơn giản, chỉ gồm có 2 việc: Nhập vào số n và gọi Move(n, 1, 2). Qua các ví dụ trên, ta có thể thấy đệ quy là một công cụ mạnh để giải các bài toán. Có những bài toán mà bên cạnh giải thuật đệ quy vẫn có những giải thuật lặp khá đơn giản và hữu hiệu. Chẳng hạn bài toán tính giai thừa hay tính số Fibonacci. Tuy vậy, đệ quy vẫn có vai trò xứng đáng của nó, có nhiều bài toán mà việc thiết kế giải thuật đệ quy đơn giản hơn nhiều so với lời giải lặp và trong một số trường hợp chương trình đệ quy hoạt động nhanh hơn chương trình viết không có đệ quy. Giải thuật cho bài Tháp Hà Nội và thuật toán sắp xếp kiểu phân đoạn (QuickSort) mà ta sẽ nói tới trong các bài sau là những ví dụ. Có một mối quan hệ khăng khít giữa đệ quy và quy nạp toán học. Cách giải đệ quy cho một bài toán dựa trên việc định rõ lời giải cho trường hợp suy biến (neo) rồi thiết kế làm sao để lời giải của bài toán được suy ra từ lời giải của bài toán nhỏ hơn cùng loại như thế. Tương tự như vậy, quy nạp toán học chứng minh một tính chất nào đó ứng với số tự nhiên cũng bằng cách chứng minh tính chất đó đúng với một số trường hợp cơ sở (thường người ta chứng minh nó đúng với 0 hay đúng với 1) và sau đó chứng minh tính chất đó sẽ đúng với n bất kỳ nếu nó đã đúng với mọi số tự nhiên nhỏ hơn n. Do đó ta không lấy làm ngạc nhiên khi thấy quy nạp toán học được dùng để chứng minh các tính chất có liên quan tới giải thuật đệ quy. Chẳng hạn: Chứng minh số phép chuyển đĩa để giải bài toán Tháp Hà Nội với n đĩa là 2n-1: Rõ ràng là tính chất này đúng với n = 1, bởi ta cần 21 - 1 = 1 lần chuyển đĩa để thực hiện yêu cầu. Với n > 1; Giả sử rằng để chuyển n - 1 đĩa giữa hai cọc ta cần 2n-1 - 1 phép chuyển đĩa, khi đó để chuyển n đĩa từ cọc x sang cọc y, nhìn vào giải thuật đệ quy ta có thể thấy rằng trong trường hợp này nó cần (2n-1 - 1) + 1 + (2n-1 - 1) = 2n - 1 phép chuyển đĩa. Tính chất được chứng minh đúng với n Vậy thì công thức này sẽ đúng với mọi n. Thật đáng tiếc nếu như chúng ta phải lập trình với một công cụ không cho phép đệ quy, nhưng như vậy không có nghĩa là ta bó tay trước một bài toán mang tính đệ quy. Mọi giải thuật đệ quy đều có cách thay thế bằng một giải thuật không đệ quy (khử đệ quy), có thể nói được như vậy bởi tất cả các chương trình con đệ quy sẽ đều được trình dịch chuyển thành những mã lệnh không đệ quy trước khi giao cho máy tính thực hiện. Việc tìm hiểu cách khử đệ quy một cách "máy móc" như các chương trình dịch thì chỉ cần hiểu rõ cơ chế xếp chồng của các thủ tục trong một dây chuyền gọi đệ quy là có thể làm được. Nhưng muốn khử đệ quy một cách tinh tế thì phải tuỳ thuộc vào từng bài toán mà khử đệ quy cho khéo. Không phải tìm đâu xa, những kỹ thuật giải công thức truy hồi bằng quy hoạch động là ví dụ cho thấy tính nghệ thuật trong những cách tiếp cận bài toán mang bản chất đệ quy để tìm ra một giải thuật không đệ quy đầy hiệu quả. Viết một hàm đệ quy tính ước số chung lớn nhất của hai số tự nhiên a, b không đồng thời bằng 0, chỉ rõ đâu là phần neo, đâu là phần đệ quy. Bài 2Viết một hàm đệ quy tính Ck theo công thức truy hồi sau:
Chứng minh rằng hàm đó cho ra đúng giá trị: Cnk = n! / k!(n - k)! Bài 3Nêu rõ các bước thực hiện của giải thuật cho bài Tháp Hà Nội trong trường hợp n = 3. Viết chương trình giải bài toán Tháp Hà Nội không đệ quy. |
