Đệ quy, hay chuyện một hàm chờ chính nó
Đệ quy, hay chuyện một hàm chờ chính nó
Tháp Hà Nội 20 tầng cần 1.048.575 lời gọi mà ngăn xếp chỉ sâu 20 khung, nên nó chạy êm. Giai thừa của 99.999 chỉ cần 100.000 lời gọi, ít hơn mười lần, và nó chết. Bài này bắt bạn đếm hai con số đó tách nhau ra, vì chỉ một trong hai là thứ giết chương trình.
Chương này mang tên đệ quy, nhưng trước khi nói về quy hoạch động thì phải trả lời một câu hỏi thô hơn: một hàm tự gọi chính nó thì máy làm gì?
Câu trả lời không nằm ở công thức truy hồi. Nó nằm ở một cấu trúc rất vật lý gọi là ngăn xếp lời gọi. Mỗi lần một hàm được gọi mà chưa xong, máy giữ lại một khung cho lần gọi đó: tham số riêng, biến cục bộ riêng, và địa chỉ để biết phải trả kết quả về đâu. Khung ấy không được thả ra khi hàm gọi con, vì nó còn dở việc. Nó đứng đó chờ.
Từ đó sinh ra hai đại lượng mà người mới hay gộp làm một, và gộp sai:
- tổng số lời gọi, tức máy phải làm bao nhiêu lượt việc từ đầu tới cuối;
- độ sâu tối đa, tức nhiều nhất bao nhiêu khung cùng nằm trên ngăn xếp tại một thời điểm.
Cái thứ nhất quyết định chương trình chạy nhanh hay chậm. Cái thứ hai quyết định chương trình sống hay chết, vì ngăn xếp có trần, và chạm trần thì chương trình không chậm đi, nó dừng luôn.
Sim dưới đây chạy thật bốn quy trình đệ quy, ghi lại từng bước, rồi đếm cả ba con số cho bạn: lời gọi, việc thật, và độ sâu. Nó cũng có một công tắc mà tôi khuyên bạn bật ngay: bỏ ca cơ sở.
1 · Có dừng hay không, và vì sao ✎ sửa được
void hanoi(int n, char from, char to, char via) {
if (n <= 1) { // base case
if (n == 1) move(1, from, to);
return;
}
hanoi(n - 1, from, via, to); // call 1: NOT in tail position
move(n, from, to); // work between the two calls
hanoi(n - 1, via, to, from); // call 2: in tail position
}2 · Ba con số, và chỉ một trong ba giết bạn
3 · Ngăn xếp tại một thời điểm ✎ sửa được
hanoi(1, A→B, đệm C)đang chạyhanoi(2, A→C, đệm B)đóng băng, chờ con trả vềhanoi(3, A→B, đệm C)đóng băng, chờ con trả vềhanoi(4, A→C, đệm B)đóng băng, chờ con trả về4 · Đệ quy đuôi hay không, đo chứ không đoán
5 · Ở cỡ không chạy nổi thì đếm bằng công thức ✎ sửa được
| n | số lời gọi (tính chính xác) | độ sâu tối đa | lọt trần không |
|---|---|---|---|
| 4 | 15 | 4 | ✔ lọt |
| 10 | 1.023 | 10 | ✔ lọt |
| 20 | 1.048.575 | 20 | ✔ lọt |
| 30 | 1.073.741.823 | 30 | ✔ lọt |
| 40 | 1.099.511.627.775 | 40 | ✔ lọt |
| 53 | 9.007.199.254.740.991 | 53 | ✔ lọt |
| 64 | 18.446.744.073.709.551.615 (số nguyên thường đã không giữ nổi con số này) | 64 | ✔ lọt |
| lượt chạy | lời gọi | độ sâu | lọt trần không |
|---|---|---|---|
| Tháp Hà Nội, n = 20Hơn một triệu lời gọi, mà ngăn xếp chưa bao giờ quá 20 khung. | 1.048.575 | 20 | ✔ lọt |
| Tổng mảng chia đôi, n = 500.001Cũng hơn một triệu lời gọi, và độ sâu chỉ 20 khung vì mỗi tầng chia đôi. | 1.000.001 | 20 | ✔ lọt |
| Giai thừa, nhân sau khi gọi, n = 99.999Ít lời gọi hơn mười lần, nhưng độ sâu bằng đúng số lời gọi, nên chính nó là cái chết. | 100.000 | 100.000 | ✖ tràn |
- Nó đếm lời gọi, khung và việc. Nó không đo giây. Một lời gọi hàm đắt hơn một vòng lặp, nhưng đắt hơn bao nhiêu thì phụ thuộc máy, ngôn ngữ và cỡ khung, và không con số nào ở đây đo cái đó.
- Trần độ sâu là số minh hoạ do bạn đặt, không phải hằng của chuẩn nào. Cột "lọt trần không" chỉ so độ sâu với con số bạn vừa gõ, nó không dự đoán máy bạn sập ở đâu.
- Khi bỏ ca cơ sở, sim không chứng minh hàm không dừng theo nghĩa toán học. Nó ghi được rằng qua 1.500 khung liên tiếp không có khung nào trả về, và nói thẳng là nó dừng ghi vì chạm trần. Phần chứng minh nằm ở chỗ bạn đọc đoạn mã và thấy không còn nhánh nào trả về.
- Mảng để tính tổng là 1, 2, ..., n chứ không phải số ngẫu nhiên, để bạn đối chiếu đáp số với công thức
n(n+1)/2bằng tay. Đổi dữ liệu thì số lời gọi và độ sâu không đổi, chỉ đáp số đổi. - Bốn quy trình ở đây đều tự viết, không chép số của ai, nên không có dòng nguồn nào để dẫn. Cổng kiểm số canh phép tính: mỗi cấu hình phải cho ra đúng con số nào.
Ca cơ sở không phải một thủ tục hình thức
Ở trạng thái mở bài, sim chạy Tháp Hà Nội 4 tầng. Nó dừng, và nó báo vì sao nó dừng: có 8 khung chạm ca cơ sở rồi trả về mà không gọi tiếp.
Giờ bấm công tắc bỏ ca cơ sở. Không đổi gì khác. Kết quả là:
- không còn khung nào chạm ca cơ sở, con số đó tụt về 0;
- tham số đi 4, 3, 2, 1, 0 rồi âm, và cứ âm mãi;
- không lời gọi nào trả về, nên 0 bước chuyển đĩa được thực hiện. Ở Tháp Hà Nội, bước chuyển nằm sau lời gọi thứ nhất, mà lời gọi ấy không bao giờ trả về, nên việc thật không tới lượt. Đổi sang giai thừa đuôi rồi bỏ ca cơ sở thì con số này lại không bằng 0, vì ở đó phép nhân nằm trước lời gọi. Cùng một kiểu treo, mà một bên không làm gì còn một bên làm việc suốt, và cái quyết định là vị trí của việc so với lời gọi. Mục 4 sẽ quay lại đúng chỗ này;
- sim phải tự dừng ghi ở trần 1.500 khung, và nó nói thẳng ra là nó dừng vì chạm trần chứ không phải vì hàm kết thúc.
Đây là chỗ tôi muốn bạn để ý một chi tiết về sự trung thực. Sim không chứng minh hàm không dừng theo nghĩa toán học; nó chỉ đo được rằng qua 1.500 khung liên tiếp không có khung nào trả về, và nó nói rõ điều đó. Phần chứng minh nằm ở chỗ bạn đọc đoạn mã đang hiện trên sim và thấy không còn nhánh nào trả về được nữa.
Có ca cơ sở vẫn chưa đủ
Sách nào cũng dạy hai điều kiện: phải có ca cơ sở, và tham số phải tiến về phía nó. Nhưng có một cách hỏng thứ ba mà hai điều kiện ấy không chặn được, và sim dựng lại được nó bằng hai núm.
Chọn giai thừa, nhân sau khi gọi, đặt n = 7, bước giảm tham số là 2, ca cơ sở viết là n == 0.
Ca cơ sở còn nguyên. Tham số giảm đều, mỗi bước bớt 2. Và hàm không bao giờ dừng: tham số đi 7, 5, 3, 1, rồi -1, -3, và nó nhảy qua số 0 chứ không bao giờ bằng đúng 0. Sim đo được điều đó và phân biệt được ba ca khác nhau: nó báo tham số vẫn giảm chứ không đứng yên, và báo giá trị nhỏ nhất tham số đã xuống tới.
Bây giờ đổi đúng một thứ: ca cơ sở thành n <= 0. Hàm dừng ngay, sau 5 khung, cho 7, 5, 3, 1 và -1.
Đó là toàn bộ khoảng cách giữa một hàm chạy được và một hàm treo máy: == so với <=. Và điều làm nó nguy hiểm là ở bước giảm bằng 1, tức cách viết bình thường của mọi người, hai cách viết cho ra y hệt nhau. Lỗi ngủ yên trong mã của bạn cho tới ngày ai đó sửa bước nhảy.
Với n = 8 thì bước 2 lại dừng bình thường, cũng đúng 5 khung, cho 8, 6, 4, 2, 0. Cùng một đoạn mã, số chẵn thì chạy, số lẻ thì treo. Bạn thử cả hai rồi hãy tin.
Viết ca cơ sở bằng phép so bao trùm (n <= 0, hi - lo <= 1) chứ đừng viết bằng phép so bằng đúng (n == 0), trừ khi bạn chắc chắn tham số không thể vượt qua mốc đó. Phép so bao trùm không tốn thêm gì, và nó bắt được cả những đầu vào bạn chưa nghĩ tới lúc viết.
Tháp Hà Nội: 2^n - 1 bước, mà chỉ n khung
Chọn Tháp Hà Nội và kéo n. Đây là ví dụ sạch nhất trong cả môn để tách số lời gọi ra khỏi độ sâu, vì cả hai đều là công thức gọn mà lại thuộc hai bậc tăng trưởng hoàn toàn khác nhau.
Ba cọc, n cái đĩa to nhỏ khác nhau xếp chồng trên cọc A, luật là mỗi lần chuyển một đĩa và không được đặt đĩa lớn lên đĩa nhỏ. Lời giải đệ quy chỉ có ba dòng: chuyển n - 1 đĩa trên sang cọc đệm, chuyển đĩa dưới cùng sang đích, rồi chuyển n - 1 đĩa kia từ cọc đệm sang đích.
Ở n = 4, sim đếm được:
- 15 bước chuyển đĩa, đúng bằng
2^4 - 1; - 15 lời gọi, cũng bằng
2^4 - 1, và đây không phải trùng hợp: mỗi lời gọi làm đúng một bước chuyển, nên hai con số này bằng nhau ở mọin; - độ sâu tối đa 4 khung, đúng bằng
n; - 8 khung chạm ca cơ sở, đúng bằng
2^3.
Kéo lên n = 10 thì lời gọi thành 1.023 còn độ sâu vẫn chỉ 10. Một con số nhân đôi mỗi lần thêm một tầng, một con số cộng thêm một. Đó là hai thế giới.
Cột "số lời gọi" trong bảng ở mục 5 chạy tới 64 tầng, và nó phải tính bằng số nguyên lớn chứ không phải số thường. Lý do là một mốc mà bài quy hoạch động đã mổ kỹ: số nguyên giữ đúng được lớn nhất của JavaScript là 2^53 - 1, tức 9.007.199.254.740.991, và đó đúng bằng số bước của tháp 53 tầng. Từ 54 tầng trở lên, con số bước không còn giữ chính xác nổi. Mốc 54 ấy là phần tính tự dò ra bằng cách so số thường với phép tính chính xác, không phải tôi gõ vào.
Bản truyền thuyết 64 tầng cần 18.446.744.073.709.551.615 bước. Mỗi giây một bước thì hết 584.542.046.090 năm, quy ước một năm 365,25 ngày. Mà ngăn xếp thì vẫn chỉ cần 64 khung. Nói cách khác: bài toán này bất khả thi về thời gian và hoàn toàn thoải mái về bộ nhớ, và không có con số nào trong hai con số đó nói hộ được con số kia.
Con số n đó là của cách bạn viết ca cơ sở
Đừng nhớ "độ sâu Tháp Hà Nội bằng n" như một tính chất của bài toán. Nó là tính chất của cách viết.
Sim dừng ngay khi còn một đĩa, tức ca cơ sở là n <= 1. Nhiều sách viết ca cơ sở là tháp rỗng và để hàm đệ quy xuống tận đó. Cách ấy giải cùng bài toán, ra cùng 15 bước ở n = 4, thậm chí cùng thứ tự từng bước một, nhưng mỗi nhánh xuống sâu thêm một tầng nữa, nên:
- độ sâu thành 5 khung ở
n = 4chứ không phải 4, và lệch đúng một khung ở mọin; - số lời gọi thành 31 chứ không phải 15, tức
2^(n+1) - 1thay vì2^n - 1, vì những lá chẳng làm gì vẫn tốn mỗi lá một khung.
Cùng một lời giải, cùng một đáp số, mà hai con số kế toán khác nhau chỉ vì bạn để đệ quy đi sâu thêm một bậc. Cho nên hãy nhớ định nghĩa thay cho công thức: độ sâu bằng số tầng lời gọi lồng nhau ở lúc lồng sâu nhất.
Ba lượt chạy, và cái ít lời gọi nhất là cái chết
Đây là bảng tôi muốn bạn đọc kỹ nhất trong bài. Nó ở cuối mục 5, và nó dùng công thức chứ không chạy thật, vì không trang web nào ghi nổi một triệu bước. Cả ba công thức ấy đã được cổng kiểm số đối chiếu với lượt chạy thật trên toàn bộ dải n mà sim cho phép, nên chúng là phần mở rộng của cái sim đang đếm, không phải một lời khẳng định khác.
| lượt chạy | lời gọi | độ sâu | lọt trần 10.000 khung không |
|---|---|---|---|
| Tháp Hà Nội, 20 tầng | 1.048.575 | 20 | lọt |
| tổng mảng chia đôi, 500.001 phần tử | 1.000.001 | 20 | lọt |
giai thừa, n = 99.999 | 100.000 | 100.000 | tràn |
Hai dòng đầu gọi hơn một triệu lần và ngăn xếp không bao giờ quá 20 khung. Dòng cuối gọi ít hơn mười lần và nó là dòng duy nhất tràn.
Nếu bạn chỉ nhìn cột lời gọi, bạn sẽ đi tối ưu sai chỗ hoàn toàn. Cột quyết định sống chết là cột giữa.
Vì sao ba lượt chạy này khác nhau đến thế thì nằm ở dáng của cây gọi:
- giai thừa gọi đúng một nhánh, và nhánh đó dài bằng
n. Nên độ sâu bằng đúng số lời gọi, ở mọin. Ởn = 8: 9 lời gọi, độ sâu 9, 8 phép nhân, trả về 40.320. Hai con số đó dán chặt vào nhau, nên hàm này chết đúng lúc nó bắt đầu tốn việc. - Tháp Hà Nội gọi hai nhánh, nhưng hai nhánh ấy kế tiếp nhau chứ không lồng vào nhau: khi nhánh phải chạy thì nhánh trái đã trả về và khung của nó đã được gỡ. Nên số lời gọi nhân đôi mỗi tầng còn độ sâu chỉ cộng thêm một.
- tổng mảng chia đôi gọi hai nhánh trên hai nửa, nên mỗi tầng chia đôi bài toán. Ở 8 phần tử: 15 lời gọi, độ sâu 4, 7 phép cộng, tổng bằng 36. Ở 64 phần tử: 127 lời gọi, độ sâu chỉ 7, tổng 2.080. Ở một triệu phần tử: 1.999.999 lời gọi, độ sâu 21.
Độ sâu của tổng mảng tăng theo logarit, nên nó nhảy bậc chứ không tăng đều, và mốc nhảy nằm ở luỹ thừa của hai. Kéo n từ 8 lên 9 thì độ sâu đi từ 4 lên 5; kéo từ 5 lên 6 thì nó không đổi. Cái này dễ bị nhìn thành núm chết, nên nói rõ: núm vẫn sống, chỉ là đầu ra có độ chia thô hơn bước kéo.
Đệ quy đuôi, và vì sao nó chuyển sang vòng lặp được
Người ta hay nói "mọi đệ quy đều viết lại được bằng vòng lặp". Câu đó đúng mà vô ích, vì nó không nói cho bạn cái giá. Cái giá phụ thuộc một tính chất rất cụ thể: lời gọi con có phải việc cuối cùng của khung cha hay không.
Sim đo tính chất đó chứ không dán nhãn. Mỗi khung ghi lại thứ tự các việc nó làm, và lúc trả về thì từng lời gọi nó đã phát ra được xếp loại: nếu lời gọi là việc cuối cùng trong danh sách thì nó ở vị trí đuôi, còn nếu sau nó còn việc gì nữa thì không.
Bật hai bản giai thừa lên rồi so, ở n = 8:
- giai thừa, nhân sau khi gọi:
return n * fact(n-1). Cả 8 lời gọi đều không ở vị trí đuôi, vì sau khi lời gọi con trả về thì khung cha còn một phép nhân phải làm. Độ sâu bản đệ quy là 9, và bản vòng lặp tương đương vẫn phải 9. - giai thừa đuôi, nhân trước khi gọi:
return factTail(n-1, acc*n). Cả 8 lời gọi đều ở vị trí đuôi, 0 lời gọi không đuôi. Độ sâu bản đệ quy vẫn là 9, nhưng bản vòng lặp chỉ cần 1.
Hai bản này gọi bằng nhau, sâu bằng nhau, làm số phép nhân bằng nhau, và trả về cùng 40.320. Cổng kiểm số đã đối chiếu cả bốn thứ đó trên toàn dải. Thứ duy nhất khác nhau giữa chúng là vị trí phép nhân, và chính nó quyết định chuyện bản vòng lặp có phải mang theo ngăn xếp hay không.
Lý do rất cơ học: nếu sau khi con trả về mà cha không còn việc, thì cha chẳng cần tồn tại nữa lúc con đang chạy. Khung của cha dùng lại được cho con, và cả chuỗi lời gọi biến thành một vòng lặp phẳng ở độ sâu 1. Còn nếu cha còn việc đang chờ, việc ấy phải nằm ở đâu đó: bạn viết vòng lặp bằng tay thì bạn phải tự mang một ngăn xếp sâu y như vậy. Đó là đổi chỗ chứa, không phải bớt chỗ.
Hai quy trình còn lại đều không phải đệ quy đuôi, và sim đếm ra cụ thể:
- Tháp Hà Nội ở
n = 4: 7 lời gọi không đuôi và 7 lời gọi đuôi. Lời gọi thứ hai của mỗi khung ở vị trí đuôi, lời gọi thứ nhất thì không, vì sau nó còn một bước chuyển đĩa và cả một lời gọi nữa. - tổng mảng chia đôi ở 8 phần tử: 14 lời gọi không đuôi, tức
2(n-1), và 0 lời gọi đuôi. Phép cộng nằm sau cả hai nửa, nên không nửa nào là việc cuối cùng.
Có một ca biên vui mà sim cũng đo đúng: tháp 1 tầng được xếp là đệ quy đuôi. Không phải vì nó đặc biệt, mà vì nó không phát ra lời gọi nào cả, nên tập lời gọi không đuôi rỗng. Đây là chỗ dễ thấy nhất rằng con số kia là kết quả đo, không phải cái tên dán lên thuật toán.
Đếm khung không phải đo giây
Chỗ này phải nói rõ, cùng tinh thần với bài đếm chi phí: sim đếm việc và khung, nó không đo giây.
- Một lời gọi hàm đắt hơn một vòng lặp. Nó phải đẩy tham số, lưu địa chỉ trở về, cấp khung mới, rồi tháo tất cả ra. Nhưng đắt hơn bao nhiêu thì phụ thuộc máy, ngôn ngữ và cỡ khung, và không con số nào ở đây đo cái đó.
- Trần độ sâu trong sim là số bạn đặt, không phải hằng của chuẩn nào. Mặc định 10.000 chỉ là một số minh hoạ. Trần thật xê dịch từ vài nghìn tới vài trăm nghìn khung tuỳ máy, ngôn ngữ, cỡ mỗi khung và cả cờ biên dịch. Cột "lọt trần không" chỉ so độ sâu với con số bạn vừa gõ. Bạn kiểm được nó bằng chính bảng đó: giai thừa của 1.000 sâu 1.001 khung nên lọt trần 10.000, còn giai thừa của 10.000 sâu 10.001 khung nên tràn. Lệch một khung là đổi kết luận, và đó chính là lý do một cái trần đoán bừa thì vô dụng.
- Sim có trần ghi riêng của nó, tối đa 4.000 bước và 1.500 khung, và nó luôn nói khi chạm trần chứ không cắt lặng lẽ. Không cấu hình hợp lệ nào bị cắt: tháp 10 tầng, cấu hình dài nhất mà sim cho phép, ghi 3.581 bước, vẫn dưới trần.
- Giá trị trả về của giai thừa chỉ chính xác tới
n = 22. Từ 23 trở lên số vẫn hiện ra đầy đủ chữ số và đã sai, không cảnh báo gì. Mốc 22 đó là phần tính tự dò ra. Ba cột lời gọi, độ sâu và phép nhân thì vẫn đúng ở mọin, vì chúng là số nhỏ.
Vậy đếm để làm gì? Để bạn có một con số kiểm được thay cho một cảm giác. Không cảm giác nào cho bạn biết rằng một triệu lời gọi có thể an toàn hơn một trăm nghìn, hay rằng đổi == thành <= là khoảng cách giữa chạy và treo.
Đệ quy hỏng theo ba cách, không phải hai: thiếu ca cơ sở, tham số không tiến về ca cơ sở, và tham số nhảy qua ca cơ sở. Ca thứ ba là ca ngủ yên lâu nhất, vì ở bước giảm bằng 1 thì n == 0 và n <= 0 cho ra y hệt nhau, còn ở bước giảm bằng 2 thì n = 7 treo máy trong khi n = 8 chạy bình thường. Về chi phí, hãy tách hai con số ra và đọc cả hai: Tháp Hà Nội 20 tầng gọi 1.048.575 lần mà chỉ sâu 20 khung nên nó chạy êm, còn giai thừa của 99.999 gọi 100.000 lần, ít hơn mười lần, và nó tràn ngăn xếp vì độ sâu của nó bằng đúng số lời gọi. Muốn ngăn xếp nông thì hãy làm bài con nhỏ đi theo kiểu chia đôi, như tổng mảng: một triệu phần tử vẫn chỉ 21 khung. Còn muốn bỏ ngăn xếp hẳn thì phải đo xem lời gọi có ở vị trí đuôi hay không, vì chỉ khi đó khung cha mới dùng lại được và vòng lặp mới thật sự rẻ hơn; đệ quy không đuôi chuyển sang vòng lặp chỉ là đổi chỗ chứa cái ngăn xếp, không phải bỏ nó.
Đọc thêm để nối bài này vào phần còn lại của môn: quy hoạch động là bài kế tiếp trong chương, và nó xử lý một dạng lãng phí khác hẳn, cụ thể là các nhánh cùng tính lại một bài con; ngăn xếp và hàng đợi cho biết cái ngăn xếp lời gọi ở đây thật ra là cấu trúc gì và vì sao nó có trần; sắp xếp trộn là một bài chia đôi thật, cùng dáng với tổng mảng ở đây; bậc tăng trưởng giải thích vì sao 2^n với n là hai thế giới; còn đệ quy trong C là chỗ bạn viết ra chính những hàm đang bị mổ ở đây.
- 1Tháp Hà Nội 20 tầng cần 1.048.575 lời gọi với độ sâu 20 khung. Giai thừa của 99.999 cần 100.000 lời gọi với độ sâu 100.000 khung. Cái nào tràn ngăn xếp, và vì sao?
- 2Một hàm giai thừa có ca cơ sở là if (n == 0) return 1; và bước đệ quy gọi fact(n - 2). Gọi nó với n = 7. Chuyện gì xảy ra?
- 3Hai bản giai thừa trong sim gọi bằng nhau, sâu bằng nhau, làm cùng số phép nhân và trả về cùng đáp số. Vậy khác nhau ở đâu, và cái khác đó dùng làm gì?