Tổng quan
Tháp Hà Nội (Tower of Hanoi) là một câu đố kinh điển gồm ba cọc và một chồng đĩa kích thước khác nhau. Ban đầu tất cả các đĩa nằm trên một cọc theo thứ tự lớn dần, và mục tiêu là chuyển toàn bộ chồng đĩa sang một cọc khác mà không bao giờ đặt đĩa lớn lên đĩa nhỏ và mỗi lần chỉ di chuyển một đĩa.
Đây là minh họa thuần túy nhất về đệ quy: để chuyển n đĩa từ cọc nguồn sang cọc đích, trước tiên bạn chuyển n−1 đĩa trên cùng sang cọc trung gian, chuyển đĩa lớn nhất sang cọc đích, rồi chuyển n−1 đĩa đó lên trên. Mỗi bài toán con là một bản sao nhỏ hơn của bài toán gốc, khiến lời giải đệ quy vừa ngắn gọn vừa tinh tế.
Tháp Hà Nội hoạt động thế nào?
- Phát biểu mục tiêu: chuyển n đĩa từ cọc nguồn sang cọc đích, dùng cọc thứ ba làm trung gian.
- Trường hợp cơ sở: nếu chỉ còn một đĩa, chuyển thẳng nó từ cọc nguồn sang cọc đích — không cần đệ quy.
- Đệ quy chuyển n−1 đĩa trên cùng từ cọc nguồn sang cọc trung gian, giữ nguyên đĩa lớn nhất ở đáy.
- Chuyển đĩa lớn nhất từ cọc nguồn thẳng sang cọc đích.
- Đệ quy chuyển n−1 đĩa từ cọc trung gian sang cọc đích, hoàn thành chồng đĩa đúng thứ tự.
Khi nào nên dùng?
- Dạy đệ quy, tư duy chia-để-trị và cách một bài toán quy về các bản sao nhỏ hơn của chính nó.
- Minh họa ngăn xếp lời gọi và độ sâu đệ quy, vì ngăn xếp lớn đến độ sâu n.
- Một bài toán chuẩn để so sánh cài đặt đệ quy và cài đặt lặp tương đương.
- Mô hình hóa các bài toán chuyển đổi có thứ tự khi ràng buộc cấm một số cấu hình trung gian.
Phân tích độ phức tạp
Giải n đĩa cần đúng 2^n − 1 nước đi, và điều này được chứng minh là tối ưu, nên thời gian chạy là O(2^n) — tăng gấp đôi mỗi khi thêm một đĩa. Đệ quy đạt độ sâu n, cho O(n) bộ nhớ trên ngăn xếp lời gọi. Khác với quay lui dựa trên tìm kiếm, không nhánh nào bị loại bỏ: mỗi lời gọi đệ quy đều đóng góp vào đáp án cuối cùng.
Câu hỏi thường gặp
Vì sao luôn cần 2^n − 1 nước đi?
Gọi T(n) là số nước đi cần cho n đĩa. Mỗi lời giải chuyển n−1 đĩa hai lần cộng đĩa lớn nhất một lần, nên T(n) = 2·T(n−1) + 1 với T(1) = 1, giải ra đúng bằng 2^n − 1. Con số này là tối ưu — không chiến lược hợp lệ nào ít nước đi hơn.
Tháp Hà Nội là quay lui hay đệ quy thuần?
Đây là đệ quy thuần, không phải quay lui. Không có ngõ cụt nào phải hoàn tác: mỗi nước đi đều thuộc lời giải tối ưu, nên thuật toán không bao giờ phải loại bỏ một nhánh và thử lựa chọn khác.
Có thể giải mà không dùng đệ quy không?
Có. Có một phiên bản lặp dựa trên một quy luật di chuyển đơn giản (và thậm chí một cách diễn giải bằng bộ đếm nhị phân), nhưng công thức đệ quy là cách diễn đạt rõ ràng nhất ý tưởng chia-để-trị nền tảng.