Hệ thức truy hồi là gì: từ tháp Hà Nội, dãy Fibonacci tới công thức nghiệm

Hệ thức truy hồi là công thức tính số hạng thứ n của một dãy theo các số hạng đứng trước nó, kèm theo vài giá trị ban đầu. Dãy Fibonacci là ví dụ quen nhất: F(n) = F(n − 1) + F(n − 2), với F(1) = F(2) = 1. Giải hệ thức truy hồi nghĩa là tìm công thức tính thẳng số hạng thứ n mà không phải tính lần lượt mọi số hạng trước, gọi là công thức dạng đóng.

Truy hồi là cách tự nhiên để mô tả các bài toán làm từng bước: chuyển tháp, leo cầu thang, chia nhỏ bài toán trong thuật toán. Bài dựng hệ thức từ các bài kinh điển, giải lớp hệ thức tuyến tính hệ số hằng bằng phương trình đặc trưng với ví dụ tính tay, rồi nói về mối liên hệ với đệ quy trong lập trình và những chỗ AI hay giải sai.

Tháp Hà Nội: dựng hệ thức từ cách giải bài toán

Trò chơi tháp Hà Nội, được nhà toán học Pháp Édouard Lucas giới thiệu vào cuối thế kỷ 19, gồm ba cọc và n đĩa to nhỏ khác nhau xếp ở cọc đầu, đĩa to dưới, đĩa nhỏ trên. Cần chuyển cả chồng sang cọc khác, mỗi lần một đĩa, không bao giờ đặt đĩa to lên đĩa nhỏ. Hỏi cần ít nhất bao nhiêu lần chuyển?

Gọi T(n) là số lần chuyển ít nhất cho n đĩa. Để chuyển được đĩa to nhất, trước hết phải dọn n − 1 đĩa phía trên sang cọc trung gian, tốn T(n − 1) lần. Sau đó chuyển đĩa to nhất sang cọc đích, một lần. Cuối cùng chuyển n − 1 đĩa từ cọc trung gian về đè lên, thêm T(n − 1) lần. Vậy T(n) = 2T(n − 1) + 1, với T(1) = 1. Tính dần: T(2) = 3, T(3) = 7, T(4) = 15. Nhìn dãy 1, 3, 7, 15 dễ đoán T(n) = 2 mũ n trừ 1.

Đoán chưa đủ, cần chứng minh, và quy nạp là công cụ đi kèm tự nhiên với truy hồi: nếu T(n − 1) = 2 mũ (n − 1) trừ 1 thì T(n) = 2 nhân (2 mũ (n − 1) − 1) + 1 = 2 mũ n − 2 + 1 = 2 mũ n − 1. Hệ quả: với 64 đĩa, số lần chuyển là 2 mũ 64 trừ 1, khoảng 1,8 nhân 10 mũ 19. Mỗi giây chuyển một đĩa thì mất khoảng 585 tỷ năm. Một hệ thức nhỏ gọn có thể sinh ra con số khổng lồ, điều người học thuật toán sẽ gặp lại khi bàn về độ phức tạp hàm mũ.

Thêm các bài dựng hệ thức: cầu thang, chuỗi nhị phân, chia đôi

Kỹ năng quan trọng nhất không phải giải hệ thức mà là dựng được nó: nhìn vào bước cuối cùng, hoặc bước đầu tiên, rồi chia trường hợp sao cho các trường hợp tách rời nhau.

• Leo cầu thang. Mỗi lần bước 1 hoặc 2 bậc, có bao nhiêu cách leo n bậc? Xét bước cuối: nếu bước cuối là 1 bậc thì trước đó đã leo n − 1 bậc; nếu là 2 bậc thì trước đó đã leo n − 2 bậc. Hai trường hợp tách rời, nên a(n) = a(n − 1) + a(n − 2), với a(1) = 1, a(2) = 2. Dãy là 1, 2, 3, 5, 8, 13, chính là Fibonacci lệch một chỉ số. Cầu thang 5 bậc có 8 cách.
• Chuỗi nhị phân không có hai số 1 liền nhau. Gọi b(n) là số chuỗi độ dài n như vậy. Xét ký tự đầu: nếu là 0, phần còn lại là chuỗi hợp lệ độ dài n − 1; nếu là 1, ký tự kế phải là 0, phần còn lại là chuỗi hợp lệ độ dài n − 2. Vậy b(n) = b(n − 1) + b(n − 2), b(1) = 2, b(2) = 3. Với n = 3 có 5 chuỗi: 000, 001, 010, 100, 101.
• Lãi gộp theo kỳ, nhắc để thấy truy hồi cấp một: số dư sau kỳ n bằng số dư kỳ trước nhân với (1 + lãi suất kỳ). Dạng này có lời giải là hàm mũ; phần tài chính thuộc danh mục toán ứng dụng của trang.
• Chia đôi bài toán. Thuật toán sắp xếp trộn chia dãy n phần tử làm hai nửa, sắp xếp từng nửa rồi trộn lại, nên thời gian chạy thoả T(n) = 2T(n/2) + cn với c là hằng số. Dạng chia để trị này dẫn tới kết quả n log n, nền của phân tích thuật toán.

Hai bài đầu cho hệ thức cùng dạng nhưng điều kiện ban đầu khác, nên dãy số khác nhau. Vì vậy khi dựng hệ thức, luôn tính tay vài giá trị nhỏ bằng cách liệt kê rồi đối chiếu với hệ thức: khớp ở n = 3 và n = 4 thì mới yên tâm đi tiếp.

Giải hệ thức tuyến tính bậc hai bằng phương trình đặc trưng

Lớp hệ thức giải được bằng công thức gọn nhất là tuyến tính, thuần nhất, hệ số hằng: a(n) = c1 a(n − 1) + c2 a(n − 2). Quy trình, minh hoạ với a(n) = 5a(n − 1) − 6a(n − 2), a(0) = 2, a(1) = 5:

1. Thử nghiệm dạng a(n) = r mũ n. Thay vào và chia hai vế cho r mũ (n − 2), được phương trình đặc trưng r bình phương = 5r − 6, tức r bình phương − 5r + 6 = 0.
2. Giải phương trình đặc trưng: hai nghiệm r = 2 và r = 3.
3. Hai nghiệm phân biệt nên nghiệm tổng quát là a(n) = α nhân 2 mũ n + β nhân 3 mũ n, với α, β là hằng số cần tìm.
4. Dùng điều kiện ban đầu: n = 0 cho α + β = 2; n = 1 cho 2α + 3β = 5. Giải được β = 1, α = 1. Vậy a(n) = 2 mũ n + 3 mũ n.
5. Kiểm bằng hệ thức gốc: a(2) = 5 nhân 5 − 6 nhân 2 = 13, công thức cho 4 + 9 = 13. Thêm một bước: a(3) = 5 nhân 13 − 6 nhân 5 = 35, công thức cho 8 + 27 = 35. Khớp.

Nếu phương trình đặc trưng có nghiệm kép r, nghiệm tổng quát đổi thành (α + βn) nhân r mũ n. Áp đúng quy trình cho Fibonacci, phương trình r bình phương = r + 1 có hai nghiệm (1 + căn 5)/2, chính là tỷ lệ vàng khoảng 1,618, và (1 − căn 5)/2. Kết quả là công thức Binet: F(n) bằng hiệu luỹ thừa bậc n của hai nghiệm đó, chia cho căn 5. Một dãy toàn số nguyên lại được viết bằng số vô tỷ, và các phần vô tỷ triệt tiêu nhau một cách chính xác.

Truy hồi và đệ quy trong lập trình: vì sao cách viết ngây thơ chạy chậm

Một hệ thức truy hồi chuyển thành hàm đệ quy gần như nguyên văn: hàm tính F(n) gọi lại chính nó với n − 1 và n − 2. Cách viết này đúng nhưng chậm khủng khiếp, vì cùng một giá trị bị tính đi tính lại. Để tính F(5), máy gọi F(4) và F(3); F(4) lại gọi F(3) và F(2); F(3) bị tính hai lần, F(2) ba lần. Số lần gọi hàm tăng theo hàm mũ, với cơ số xấp xỉ chính tỷ lệ vàng, nên tính F(50) theo cách này có thể mất rất lâu trên máy tính cá nhân.

Cách sửa là ghi nhớ kết quả đã tính, gọi là memoization, hoặc tính từ dưới lên: bắt đầu từ F(1), F(2), lần lượt tính F(3), F(4) cho tới F(n), mỗi giá trị đúng một lần. Số phép tính giảm từ hàm mũ xuống tuyến tính. Ý tưởng “tính mỗi bài toán con một lần rồi dùng lại” chính là quy hoạch động, một trong những kỹ thuật thuật toán quan trọng nhất, và hệ thức truy hồi là ngôn ngữ để mô tả nó.

Với người học toán, đây là lý do công thức dạng đóng có giá trị: nó cho phép tính thẳng mà không cần lặp. Nhưng trong lập trình thực tế, công thức Binet lại kém vòng lặp ở n lớn, vì số thực dấu phẩy động có độ chính xác hữu hạn và sai số làm tròn sẽ cho kết quả sai từ một ngưỡng nào đó. Biết cả hai cách và biết giới hạn của từng cách là điều phân biệt người hiểu toán với người chỉ thuộc công thức.

Những lỗi hay gặp khi làm bài truy hồi

Chia trường hợp chồng nhau khi dựng hệ thức. Trong bài leo cầu thang, hai trường hợp “bước cuối 1 bậc” và “bước cuối 2 bậc” tách rời hoàn toàn. Nếu chia theo tiêu chí khác mà một cách leo rơi vào cả hai nhóm, hệ thức sẽ đếm thừa.

Sai điều kiện ban đầu. Cùng hệ thức dạng Fibonacci, điều kiện ban đầu khác cho dãy khác. Bài leo cầu thang có a(1) = 1, a(2) = 2, không phải 1 và 1. Tính tay hai giá trị đầu bằng liệt kê trước khi dùng.

Lệch quy ước chỉ số. Có giáo trình bắt đầu Fibonacci từ F(0) = 0, có giáo trình từ F(1) = 1. Khi so đáp án với sách hoặc với AI, kiểm xem hai bên có cùng quy ước không.

Áp phương trình đặc trưng cho hệ thức không thuần nhất. Tháp Hà Nội có số hạng tự do cộng 1, nên phải tìm thêm một nghiệm riêng hoặc dùng mẹo đổi biến: đặt U(n) = T(n) + 1 thì U(n) = 2U(n − 1), một cấp số nhân quen thuộc.

Đoán công thức từ vài số hạng mà không chứng minh. Dãy 1, 2, 4, 8, 16 trông như luỹ thừa của 2, nhưng trong bài toán chia hình tròn bằng các dây cung nối n điểm trên đường tròn, số hạng kế tiếp là 31 chứ không phải 32. Đoán là bước tốt, nhưng phải có quy nạp đi kèm.

Dùng AI học truy hồi: dựng thì tự làm, kiểm thì nhờ máy

Chatbot giải phương trình đặc trưng khá ổn, nhưng hay sai ở hai đầu của bài: dựng hệ thức từ đề bài lời văn, và dùng điều kiện ban đầu. Phân việc như sau:

1. Tự dựng hệ thức từ đề, ghi rõ đã chia trường hợp theo bước nào, rồi nhờ AI phản biện: “Đây là hệ thức mình dựng cho bài đếm này và lý do chia trường hợp. Có trường hợp nào bị đếm hai lần hoặc bỏ sót không? Đừng giải hệ thức.”
2. Tự tính tay ba bốn số hạng đầu bằng liệt kê, so với giá trị hệ thức cho ra.
3. Cho AI giải phần đại số, yêu cầu ghi rõ phương trình đặc trưng, các nghiệm, hệ phương trình tìm hằng số.
4. Kiểm công thức cuối bằng cách thay n = 2, 3, 4 vào cả công thức lẫn hệ thức gốc. Hai bên phải khớp từng số.
5. Nhờ AI viết đoạn chương trình tính dãy bằng vòng lặp tới n = 20 và in cạnh giá trị của công thức, chạy để thấy khớp. Đây là cách kiểm nhanh nhất cho mọi hệ thức.

Ở bài nộp lấy điểm, phần dựng hệ thức là phần được chấm nhiều nhất và cũng là phần bạn cần tự làm. AI chỉ nên đứng ở vai người phản biện và máy tính kiểm.

Câu hỏi thường gặp

Hệ thức truy hồi và đệ quy có phải là một không?

Gần nhau nhưng không trùng. Hệ thức truy hồi là đối tượng toán học, mô tả quan hệ giữa các số hạng của một dãy. Đệ quy là kỹ thuật lập trình, một hàm gọi lại chính nó. Một hệ thức truy hồi có thể cài đặt bằng đệ quy, bằng vòng lặp, hoặc tính thẳng bằng công thức dạng đóng nếu tìm được.

Mọi hệ thức truy hồi đều có công thức dạng đóng không?

Không. Lớp tuyến tính hệ số hằng luôn giải được bằng phương trình đặc trưng, nhưng nhiều hệ thức phi tuyến không có công thức dạng đóng gọn, ví dụ ánh xạ logistic dùng trong mô hình dân số có thể cho hành vi hỗn loạn. Khi đó người ta tính số, ước lượng tốc độ tăng, hoặc nghiên cứu tính chất định tính.

Hàm sinh liên quan gì tới hệ thức truy hồi?

Hàm sinh biến một dãy số thành hệ số của một chuỗi luỹ thừa, và biến hệ thức truy hồi thành một phương trình đại số với chuỗi đó. Giải phương trình rồi khai triển lại cho công thức số hạng tổng quát. Phương pháp này mạnh hơn phương trình đặc trưng, xử lý được cả hệ thức không thuần nhất và nhiều bài đếm tổ hợp.

Vì sao tháp Hà Nội hay được dùng để dạy đệ quy?

Vì lời giải tự nhiên nhất của nó chính là đệ quy: chuyển n − 1 đĩa, chuyển đĩa lớn, chuyển lại n − 1 đĩa. Chương trình chỉ vài dòng, lại cho thấy rõ số bước tăng theo hàm mũ. Người học thấy cùng lúc vẻ gọn của đệ quy và cái giá về thời gian của nó.

Định lý thợ (master theorem) là gì?

Đó là kết quả cho phép đọc nhanh nghiệm tiệm cận của các hệ thức chia để trị dạng T(n) = aT(n/b) + f(n), rất hay gặp khi phân tích thuật toán. Nó so sánh f(n) với n mũ (log cơ số b của a) để kết luận độ lớn của T(n). Với sắp xếp trộn, a = b = 2 và f(n) tuyến tính, kết quả là n log n.