Giới thiệu về thuật toán đệ quy – Recursion Algorithm (Phần 2)

Trong phần 1 mình đã giới thiệu về khái niệm cũng như đặc điểm của thuật toán đệ quy. Hôm nay mình sẽ giới thiệu cho các bạn một số ví dụ kinh điển sử dụng thuật toán đệ quy.

1. Bài toán tính giai thừa

Cho n là một số tự nhiên (n>=0). Hãy tính giai thừa của n (n!) biết rằng 0!=1 và n!=(n-1)! x n.

Phân tích :

– Theo giả thiết, ta có : n! = (n-1)! x n. Như vậy :

  • Để tính n! ta cần phải tính (n-1)!
  • Để tính (n-1)! ta phải tính (n-2)!

– Cứ như vậy, cho tới khi gặp trường hợp 0!. Khi đó ta lập tức có được kết quả là 1, không cần phải tính thông qua một kết quả trung gian khác.

2. Bài toán “Tháp Hà Nội” (Tower of Ha Noi)

Đây là một bài toán rất nổi tiếng và kinh điển, rất thích hợp để minh họa cho thuật toán đệ quy. Sau đây là nội dung bài toán :

Có 3 chiếc cọc được đánh dấu lần lượt là A, B, C và n chiếc đĩa. Các đĩa này có kích thước khác nhau và mỗi đĩa đều có một lỗ ở giữa để cắm vào cọc. Ban đầu, các đĩa đều nằm ở cọc A, trong đó, đĩa nhỏ luôn nằm trên đĩa lớn hơn.

Yêu cầu : chuyển n đĩa từ cọc A sang cọc đích C với các điều kiện sau :

+ Mỗi lần chỉ chuyển được 1 đĩa

+ Trong quá trình chuyển, đĩa nhỏ phải luôn nằm trên đĩa lớn hơn.

+ Cho phép sử dụng cọc B làm cọc trung gian

Phân tích : ta sẽ xét các trường hợp của n

– Trường hợp đơn giản nhất, n=1, ta chỉ cần chuyển 1 đĩa từ cọc A sang cọc C.

– Nhiều hơn một chút, n=2, ta chuyển đĩa nhỏ nhất sang cọc B, chuyển đĩa còn lại sang cọc C, và cuối cùng chuyển đĩa nhỏ ở cọc B sang cọc C.

– Bây giờ ta xét n đĩa (n>2). Giả sử ta đã có cách chuyển n-1 đĩa từ một cọc sang một cọc khác. Như vậy, để chuyển n đĩa từ cọc nguồn sang cọc đích, ta cần chuyển n-1 đĩa từ cọc nguồn sang cọc trung gian. Sau đó chuyển đĩa lớn nhất từ cọc nguồn sang cọc đích. Cuối cùng, chuyển n-1 từ cọc trung gian về cọc đích.

Trên đây chỉ là những bài toán đệ quy đơn giản. Còn rất nhiều bài toán và kỹ thuật khác sử dụng phương pháp đệ quy. Mong rằng những gì mình chia sẻ có thể giúp ích cho mọi người ! 🙂

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *