Ở bài về đệ quy và ngăn xếp ta đã thấy mỗi lời gọi đệ quy chồng thêm một khung lên ngăn xếp, và quá sâu thì tràn. Có một mẹo được nhắc tới như liều thuốc chữa: viết hàm ở dạng đệ quy đuôi, trình biên dịch sẽ biến nó thành vòng lặp, hết lo tràn. Nghe gọn gàng. Nhưng "trình biên dịch sẽ" là một lời hứa có điều kiện, và bài này đo xem điều kiện đó là gì — bằng cách cho cùng một hàm tràn ở chỗ này và chạy thênh thang ở chỗ kia.
Đệ quy đuôi là gì, và vì sao nó có thể thành vòng lặp
Một lời gọi đệ quy là ở đuôi (tail call) khi nó là thao tác cuối cùng của hàm — sau khi nó trả về, không còn việc gì để làm nữa, giá trị nó trả về chính là giá trị hàm ngoài trả về. Ví dụ, tính tổng bằng một biến tích lũy (accumulator):
long tail_sum(long n, long acc){
if (n == 0) return acc;
return tail_sum(n-1, acc + n); // lời gọi là thao tác CUỐI: đệ quy đuôi
}
So với dạng "ngây thơ" hơn, nơi phép cộng xảy ra sau khi lời gọi trả về:
long naive_sum(long n){
if (n == 0) return 0;
return n + naive_sum(n-1); // còn phải CỘNG n sau khi lời gọi trả về
}
Điểm mấu chốt: với tail_sum, khi gọi vào lời đệ quy, cái khung hiện tại không còn cần gì nữa — không có phép tính nào chờ kết quả. Nên thay vì đẩy một khung mới lên ngăn xếp, trình biên dịch có thể tái sử dụng chính khung đang có: cập nhật tham số rồi nhảy về đầu hàm. Đệ quy biến thành vòng lặp. Đây là tail-call optimization (TCO). Kết quả kỳ vọng: chạy sâu tùy ý mà ngăn xếp không lớn lên, và nhanh ngang một vòng for viết tay.
Đo: cùng một hàm, tràn hay không tùy cờ biên dịch
Tôi cho các hàm này chạy ở những độ sâu tăng dần, mỗi lần trong một tiến trình con để bắt được đúng lúc nó tràn ngăn xếp (nhận tín hiệu SIGSEGV), với ngăn xếp mặc định 8 MB. Rồi biên dịch cùng file hai lần: một lần -O0 (tắt tối ưu), một lần -O2.
Độ sâu 1 triệu, ai TRÀN ngăn xếp? | gcc -O0 | gcc -O2
đệ quy ĐUÔI (accumulator) | TRÀN | chạy xong (tới 100 triệu)
naive n + sum(n-1) | TRÀN | chạy xong (tới 100 triệu)
đệ quy KHÔNG-đuôi thật (biến sau gọi) | TRÀN | TRÀN
Nhìn cột -O0: cả ba đều tràn ở 1 triệu. Ở mức không tối ưu, hàm đệ quy đuôi của tôi cũng chồng khung y như mọi hàm đệ quy khác — nó không được biến thành vòng lặp. Cùng hàm ấy, biên dịch -O2, chạy tới 100 triệu tầng sâu ngon lành vì nó đã thành một vòng lặp, ngăn xếp không hề lớn. Cùng một dòng mã C, tràn hay không tràn hoàn toàn do cờ biên dịch quyết định.
Một lần tôi đo hớ: "đệ quy đuôi thì an toàn" chỉ đúng có điều kiện
Định kiến tôi mang vào bài là: "hễ viết ở dạng đệ quy đuôi thì tự động an toàn khỏi tràn ngăn xếp". Bảng trên bác bỏ nó ngay ở cột đầu: TCO chỉ xảy ra khi ta bật tối ưu. Ở -O0, đệ quy đuôi tràn hệt như đệ quy thường. An toàn không đến từ cách viết hàm, mà từ việc trình biên dịch thật sự thực hiện phép biến đổi — và đó là hai chuyện khác nhau.
Tệ hơn cho niềm tin đó: chuẩn C không bắt buộc TCO. GCC và Clang làm nó ở -O2, nhưng đó là ân huệ của trình biên dịch, không phải bảo đảm của ngôn ngữ; một trình biên dịch khác, hay cùng trình đó ở mức tối ưu thấp, có quyền không làm. Và bước ra khỏi C thì bức tranh còn dứt khoát hơn. Tôi đo trong CPython:
Python (CPython 3.12): recursionlimit mặc định = 1000
tail(100000) với accumulator -> RecursionError (tràn)
CPython không bao giờ làm TCO — một quyết định thiết kế có chủ đích (để giữ nguyên vẹn dấu vết ngăn xếp cho việc gỡ lỗi). Nên trong Python, viết hàm ở dạng đệ quy đuôi chẳng giúp gì cả: nó vẫn đổ RecursionError khi vượt giới hạn ~1000 khung, y như mọi đệ quy khác. Kết luận đo được: "đệ quy đuôi an toàn khỏi tràn ngăn xếp" là một câu có điều kiện — điều kiện là ngôn ngữ hoặc trình biên dịch bạn đang dùng có thật sự làm TCO hay không. Trong Scheme hay Haskell, nơi TCO được ngôn ngữ bảo đảm, câu đó đúng tuyệt đối. Trong C bật -O2, đúng. Trong C -O0, hay trong Python/Java (JVM cũng không TCO), sai.
Đo hớ thứ hai: không chỉ dạng "đuôi" mới được khử
Có một bất ngờ ngược lại làm tôi phải sửa cả cách hiểu. Tôi tưởng chỉ hàm viết đúng dạng đuôi mới được biến thành vòng lặp. Nhưng nhìn lại bảng: ở -O2, hàm naive_sum (dạng n + sum(n-1), không phải đuôi) cũng chạy tới 100 triệu — nó cũng được biến thành vòng lặp. GCC có một phép tối ưu mạnh hơn TCO thuần: khử đệ quy tích lũy (accumulator recursion elimination). Nó nhận ra rằng "cộng dồn sau mỗi lời gọi" là một phép kết hợp được, và tự viết lại thành vòng lặp có biến tích lũy — dù mã nguồn không hề ở dạng đuôi.
Vậy có phải cứ -O2 là mọi đệ quy đều thành vòng lặp? Không. Cột cuối trả lời: hàm không-đuôi thật sự — hàm giữ một biến cục bộ rồi dùng nó sau khi lời gọi đệ quy trả về (kết quả không thể gấp lại thành một phép tích lũy đơn giản) — vẫn tràn ngay cả ở -O2. Đây mới là ranh giới thật: không phải "đuôi hay không-đuôi theo cú pháp", mà là "trình biên dịch có gấp được phần việc-sau-lời-gọi vào một vòng lặp hay không". Việc còn lại mà không gấp được thì bắt buộc phải giữ trên ngăn xếp, và ngăn xếp thì có đáy.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, rất thực tế: đừng dựa vào TCO để tránh tràn ngăn xếp trừ khi ngôn ngữ của bạn bảo đảm nó. Nếu bạn viết C và cần một hàm đệ quy sâu, đừng cho rằng -O2 sẽ cứu — nó thường cứu, nhưng một bản build gỡ lỗi (-O0, cực phổ biến khi phát triển) sẽ tràn, và bạn gặp lỗi chỉ ở môi trường dev hoặc chỉ ở production tùy cờ. Trong Python/Java thì TCO không tồn tại, chấm hết. Với độ sâu lớn không chặn trên được, hãy tự khử đệ quy: chuyển sang vòng lặp, hoặc dùng một ngăn xếp tường minh trên heap (như bài đệ quy và ngăn xếp đã làm với DFS). Heap lớn hơn ngăn xếp nhiều và bạn kiểm soát được.
Hệ quả thứ hai: khi TCO có hiệu lực, đệ quy đuôi không hề chậm hơn vòng lặp. Đo cho thấy hàm đệ quy đuôi ở -O2 sinh ra đúng vòng lặp mà bạn sẽ viết tay, chạy cùng tốc độ. Nên trong các ngôn ngữ bảo đảm TCO (Scheme, Haskell, Scala với @tailrec, Kotlin tailrec), viết đệ quy đuôi là một phong cách sạch mà không trả giá hiệu năng — miễn là bạn biết chắc nó là đuôi. Từ khóa tailrec của Kotlin/Scala đáng giá đúng ở chỗ này: nó báo lỗi biên dịch nếu hàm không thật sự ở dạng đuôi, biến "hy vọng compiler làm TCO" thành "được bảo đảm hoặc không cho biên dịch".
Hệ quả thứ ba là bài học đo lường quen thuộc của sê-ri: một tối ưu vô hình là một giả định nguy hiểm. TCO không để lại dấu vết trong mã nguồn; hàm trông y hệt dù nó được khử thành vòng lặp hay không. Cách duy nhất để biết chắc là đo (cho nó chạy thật sâu xem có tràn không) hoặc nhìn mã máy (gcc -S xem có lệnh call đệ quy hay chỉ là một jmp vòng lại). Con số mang theo: cùng một hàm đệ quy đuôi, gcc -O0 tràn ngăn xếp ở 1 triệu còn gcc -O2 chạy 100 triệu vì thành vòng lặp; GCC -O2 còn khử được cả đệ quy tích lũy không-đuôi, nhưng đệ quy không-đuôi thật thì vẫn tràn; và CPython không bao giờ TCO nên đệ quy đuôi vẫn tràn ở 1000 khung — "đệ quy đuôi an toàn" chỉ đúng khi compiler/ngôn ngữ thật sự làm TCO. Đừng tin một tối ưu bạn chưa thấy nó xảy ra.
Thử ba mươi giây
Nếu bạn có GCC hay Clang, viết một hàm đệ quy đuôi đơn giản (như tail_sum ở trên) rồi biên dịch hai lần: gcc -O0 -S và gcc -O2 -S, mở file .s ra tìm tên hàm. Ở -O0 bạn sẽ thấy một lệnh call gọi lại chính hàm — đó là đệ quy thật, sẽ chồng ngăn xếp. Ở -O2 lệnh call biến mất, thay bằng một jmp nhảy vòng về đầu — đệ quy đã thành vòng lặp. Còn nếu bạn dùng Python, chỉ cần def f(n): return f(n+1) rồi gọi f(0): nó sẽ đổ RecursionError sau đúng ~1000 lần, bất kể bạn viết ở dạng đuôi hay không — bằng chứng sống rằng TCO không phải thứ hiển nhiên mọi nơi đều có.
