Thuật toán đệ qui (Recursive Algorithm)

Cấu trúc dữ liệu và Giải thuật của Đỗ Xuân Lôi:

  • Chương 3. Giải thuật đệ qui
  • Mã giả được sử dụng trong bài học này và các bài học kế tiếp gọi là ngôn ngữ giả mã tựa PASCAL mục 1.3, chương 1.

1. Khái niệm đệ qui (recursive)

Ta nói một đối tượng là đệ qui nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.

2. Thuật toán và thủ tục đệ qui

Nếu lời giải của một bài toán T được thực hiện bằng lời giải của một bài toán T’, có dạng giống T, thì đó là một lời giải đệ qui. Thuật toán tương ứng với lời giải như vậy gọi là thuật toán đệ qui.

Xét bài toán tìm một từ trong một quyển tự điển, thuật toán có thể như sau:

If từ điển là một trang
  Then tìm từ trong trang này
   Else begin
            Mở từ điển vào trang giữa;
            Xác định xem nửa nào của từ điển chứa từ cần tìm;
           If từ đó nằm ở nửa trước của từ điển
	    Then tìm từ đó trong nửa trước;
	    Else tìm từ đó trong nửa sau;
	End;

Có thể hình dung một cách khái quát thuật toán trên như hình sau:

Có hai điểm chính cần lưu ý:

  • Sau mỗi lần tự điển được tách đôi thì một nửa thích hợp sẽ lại được tìm kiếm bằng một chiến thuật như đã dùng trước đó.
  • Có một trường hợp đặc biệt, khác với mọi trường hợp trước, sẽ đạt được sau nhiều lần tách đôi, đó là trường hợp tự điển chỉ còn duy nhất một trang. Lúc đó việc tách đôi ngừng lại và bài toán đã trở thành đủ nhỏ để ta có thể giải quyết trực tiếp bằng cách tìm từ mong muốn trên trang đó chẳng hạn, bằng cách tìm tuần tự. Trường hợp đặc biệt này được gọi là trường hợp suy biến (degenerate case).

Có thể coi đây là chiến thuật kiểu “chia để trị”. Bài toán được tách thành bài toán nhỏ hơn và bài toán nhỏ hơn lại được giải quyết với chiến thuật chia để trị như trước, cho tới khi xuất hiện trường hợp suy biến.

Bây giờ ta hãy thể hiện giải thuật tìm kiếm này dưới dạng một thủ tục.

Procedure SEARCH (dict, word)
{dict được coi là đầu mối để truy nhập được vào từ điển đang xét, word chỉ từ cần tìm}
1. If tự điển chỉ còn là một trang.
	Then Tìm từ word trong trang này.
	Else begin 
2. Mở tự điển vào trang giữa
    Xác định xem nửa nào của tự điển chứa từ word;
     If word nằm ở nửa trước của từ điển.
     	Then call SEARCH (dict1, word)
	Then call SEARCH (dict2, word)
	End;
{dict1 và dict2 là đầu mối để truy cập được vào nửa trước và nửa sau của tự điển}
3. Return;

Thủ tục như trên được gọi là thủ tục đệ qui. Một số đặc điểm cần chú ý:

  • Trong thủ tục đệ qui có lời gọi đến chính thủ tục đó. Ở đây, trong thủ tục SEARCH có call SEARCH
  • Mỗi lần có lời gọi lại thủ tục thì kích thước bài toán đã thu nhỏ hơn trước. Ở đây khi có call SEARCH thì kích thước tự điển chỉ còn bằng một nửa trước đó.
  • Có một trường hợp đặc biệt: trường hợp suy biến. Đó chính là trường hợp mà tự điển chỉ còn là một trang. Khi trường hợp này xảy ra thì bài toán còn lại sẽ được giải quyết theo một cách khác hẳn và gọi đệ qui cũng kết thúc. Chính tình trạng kích thước bài toán cứ giảm dần sẽ đảm bảo dẫn tới trường hợp suy biến.

3. Thiết kế thuật toán đệ qui

Khi bài toán đang xét hoặc dữ liệu đang xử lý được định nghĩa dưới dạng đệ qui thì việc thiết kế các thuật toán đệ qui tỏ ra rất thuận lợi. Có thể thấy điều này qua một số bài toán sau.

Hàm n! (n giai thừa)

Định nghĩa đệ qui của n! như sau:

Thuật toán đệ qui được viết dưới dạng thủ tục hàm như sau:

Từ thủ tục đệ qui trên chúng ta thấy:

  • Lời gọi tới chính nó ở đây nằm trong câu lệnh gán đứng sau else.
  • Ở mỗi lần gọi đệ qui đến FACTORIAL, thì giá trị của n giảm đi 1. Ví dụ, FACTORIAL (4) gọi đến FACTORIAL (3), FACTORIAL (3) gọi đến FACTORIAL (2), FACTORIAL (2) gọi đến FACTORIAL (1), FACTORIAL (1) gọi đến FACTORIAL (0) – FACTORIAL (0) chính là trường hợp suy biến, nó được tính theo cách đặc biệt FACTORIAL (0) = 1.

Mã C – Tính giai thừa

#include<stdio.h>
long int Fact(int n);
int main() {
int n;
printf("Nhập một số nguyên dương: ");
scanf("%d",&n);
printf("Giai thừa %d = %ld", n, Fact(n));
return 0;
}
long int Fact(int n) {
if (n>=1)
return n*Fact(n-1);
else
return 1;
}

Xem cách hoạt động của chương trình trên dùng công cụ Python Tutor >

Dãy số Fibonacci

Dã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 được đặt ra như sau:

  1. Các con thỏ không bào giờ chết
  2. Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái)
  3. Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới.

Giả sử bắt đầu từ một cặp mới ra đời thì đến tháng n sẽ có bao nhiêu cặp?

Ví dụ n = 6, ta thấy:

  • Tháng thứ 1: 1 cặp (cặp ban đầu)
  • Tháng thứ 2: 1 cặp (cặp ban đầu chưa đẻ)
  • Tháng thứ 3: 2 cặp (đã có thêm 1 cặp con)
  • Tháng thứ 4: 3 cặp (cặp đầu vẫn đẻ thêm)
  • Tháng thứ 5: 5 cặp (cặp con bắt đầu đẻ)
  • Tháng thứ 6: 8 cặp (cặp con vẫn đẻ tiếp)

Bây giờ ta xét tới việc tính số cặp thỏ ở tháng thứ n: F(n). Ta thấy nếu mỗi cặp thỏ ở tháng thứ (n-1) đều sinh con thì: F(n) = 2 * (n – 1)

Nhưng không phải như vậy. Trong các cặp thỏ ở tháng thứ (n – 1) chỉ có những cặp đã có ở tháng thứ (n – 2) mới sinh con ở tháng thứ n được thôi.

Do đó: F(n) = F(n – 2) + F(n – 1)

Vì vậy có thể tính F(n) theo công thức sau:

Dãy số thể hiện F(n) ứng với các giá trị của n = 1, 2, 3,…có dạng:

1              1              2              3              5              8              13           21           34           55           …

Dãy số này được gọi là dãy Fibonacci – là mô hình của rất nhiều hiện tượng tự nhiên và cũng được sử dụng nhiều trong tin học.

Thủ tục đệ qui của F(n) như sau:

Trường hợp suy biến ứng với 2 giá trị F(1) = F(2) = 1.

Không phải lúc nào tính đệ qui trong cách giải bài toán cũng thể hiện rõ nét và đơn giản như bài toán n! và dãy Fibonacci. Thế thì vấn đề gì cần lưu tâm khi thiết kế một thuật toán đệ qui? Có thể thấy câu trả lời qua việc giải đáp các câu hỏi sau:

  1. Có thể định nghĩa được bài toán dưới dạng một bài toán cùng loại, nhưng nhỏ hơn, như thế nào?
  2. Như thế nào là kích thước của bài toán được giảm đi ở mỗi lần gọi đệ qui?
  3. Trường hợp đặc biệt nào của bài toán sẽ được coi là trường hợp suy biến?

Mã C – Dãy Fibonacci

#include<stdio.h>
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n;
printf("Nhập n = ");
scanf("%d\n", &n);
printf("Kết quả: %d", fib(n));
getchar();
return 0;
}
view raw Fibonacci.c hosted with ❤ by GitHub

Xem cách hoạt động của chương trình trên dùng công cụ Python Tutor >

Bài toán Tháp Hà Nội (Tower of Hanoi)

Có n đĩa, kích thước nhỏ dần, đĩa có lỗ ở giữa. Có thể xếp chồng chúng lên nhau xuyên qua một cọc, to dưới nhỏ trên để cuối cùng có một chồng đĩa dạng như hình tháp

Yêu cầu đặt ra là:

Chuyển chồng đĩa từ cọc A sang cọc khác, chẳng hạn cọc C, theo những điều kiện sau:

  • Mỗi lần chỉ được chuyển 1 đĩa
  • Không khi nào có tình huống đĩa to ở trên đĩa nhỏ (dù là tạm thời)
  • Được phép sử dụng một cọc trung gian, chẳng hạn cọc B, để đặt tạm đĩa (gọi là cọc trung gian) khi chuyển từ cọc A sang cọc C.

Để đi tới cách giải tổng quát, trước hết xét vài trường hợp đơn giản.

  • Trường hợp 1 đĩa: Chuyển đĩa từ cọc A sang cọc C
  • Trường hợp 2 đĩa:
    • Chuyển đĩa thứ nhất từ cọc A sang cọc B
    • Chuyển đĩa thứ hai từ cọc A sang cọc C
    • Chuyển đĩa thứ nhất từ cọc B sang cọc C

Ta thấy với trường hợp n đĩa (n > 2) nếu coi (n – 1) đĩa ở trên, đóng vai trò như đĩa thứ nhất thì có thể xử lý giống như trường hợp 2 đĩa được, nghĩa là:

  • Chuyển (n – 1) đĩa từ A sang B
  • Chuyển đĩa thứ n từ A sang C
  • Chuyển (n – 1) đĩa từ B sang C

Có thể hình dung 3 bước:

Ban đầu

Bước 1

Bước 2

Bước 3

Như vậy, bài toán Tháp Hà Nội tổng quát với n đĩa được dẫn tới bài toán tương tự với kích thước nhỏ hơn, chẳng hạn từ chỗ chuyển n đĩa từ cọc A sang cọc C thành chuyển (n – 1) đĩa từ cọc A sang cọc B. Và ở mức này thì thuật toán là:

  • Chuyển (n – 2) đĩa từ A sang C
  • Chuyển 1 đĩa từ A sang B
  • Chuyển (n – 2) đĩa từ B sang C

Và cứ như thế cho tới khi trường hợp suy biến xảy ra, đó là trường hợp bài toán chuyển 1 đĩa.

Giải thuật đệ qui cho bài toán Tháp Hà Nội như sau:

Mã C – Tháp Hà Nội

#include<stdio.h>
void HANOI(int n, char coc_ban_dau, char coc_dich, char coc_trung_gian)
{
if (n == 0)
{
return;
}
HANOI(n – 1, coc_ban_dau, coc_trung_gian, coc_dich);
printf("Di chuyển đĩa %d từ cọc %c đến cọc %c\n", n, coc_ban_dau, coc_dich);
HANOI(n – 1, coc_trung_gian, coc_dich, coc_ban_dau);
}
int main()
{
int n;
scanf("%d\n", &n);
HANOI(n, 'A', 'C', 'B'); // A, B và C là tên các cọc
return 0;
}
view raw HANOI.c hosted with ❤ by GitHub

Xem cách hoạt động của chương trình trên dùng công cụ Python Tutor >

Bạn có vấn đề gì về bài học này không?

Thảo luận cùng chúng tôi >