{"slug":"toi-uu-hoa-de-quy-duoi-tail-call-optimization-la-gi","title":"Tối ưu hóa đệ quy đuôi (Tail Call Optimization) là gì?","summary":"Tối ưu hóa lời gọi đuôi (Tail Call Optimization – TCO) là kỹ thuật tối ưu trong trình biên dịch nhằm thực hiện lời gọi hàm ở vị trí đuôi mà không cần duy trì một khung ngăn xếp (Stack Frame) mới theo cơ chế gọi hàm thông thường. Khi áp dụng thành công, kỹ thuật này có thể hạn chế sự gia tăng bộ nhớ ngăn xếp, giảm chi phí gọi hàm và cho phép thực hiện những chuỗi lời gọi đuôi có độ sâu lớn.","excerpt":"Tối ưu hóa lời gọi đuôi (Tail Call Optimization – TCO) là kỹ thuật tối ưu trong trình biên dịch nhằm thực hiện lời gọi hàm ở vị trí đuôi mà không cần duy trì một khung ngăn xếp (Stack Frame) mới theo cơ chế gọi hàm thông thường. Khi áp dụng thành công, kỹ thuật này có thể hạn chế sự gia tăng bộ nhớ ngăn xếp, giảm chi phí gọi hàm và cho phép thực hiện những chuỗi lời gọi đuôi có độ sâu lớn.","markdown":"# Tối ưu hóa đệ quy đuôi (Tail Call Optimization) là gì?\n\n## Tóm tắt\n\nTối ưu hóa lời gọi đuôi (Tail Call Optimization – TCO) là kỹ thuật tối ưu trong trình biên dịch nhằm thực hiện lời gọi hàm ở vị trí đuôi mà không cần duy trì một khung ngăn xếp (Stack Frame) mới theo cơ chế gọi hàm thông thường. Khi áp dụng thành công, kỹ thuật này có thể hạn chế sự gia tăng bộ nhớ ngăn xếp, giảm chi phí gọi hàm và cho phép thực hiện những chuỗi lời gọi đuôi có độ sâu lớn.\n\nTrong trường hợp hàm tự gọi lại chính nó, kỹ thuật này thường được gọi cụ thể là tối ưu hóa đệ quy đuôi (Tail Recursion Optimization) hoặc loại bỏ lời gọi đệ quy đuôi (Tail Recursion Elimination – TRE).\n\nBài viết trình bày nguyên lý của đệ quy đuôi, cơ chế hoạt động của ngăn xếp khi gọi hàm, phương pháp chuyển đổi đệ quy thành vòng lặp, những điều kiện cần thiết để tối ưu, ảnh hưởng của quy ước gọi hàm (Calling Convention) và giao diện nhị phân ứng dụng (Application Binary Interface – ABI). Đồng thời, bài viết đối chiếu cơ chế triển khai trong GCC và LLVM, phân tích mã máy trên các kiến trúc x86-64 và ARM64, cũng như những giới hạn của kỹ thuật này trong thực tế.\n\n**Từ khóa:** tối ưu hóa lời gọi đuôi; đệ quy đuôi; trình biên dịch; khung ngăn xếp; loại bỏ đệ quy đuôi; LLVM; GCC; quy ước gọi hàm; mã máy.\n\n\n\n## 1. Đệ quy và cơ chế gọi hàm\n\n### 1.1. Đệ quy là gì?\n\nĐệ quy (Recursion) là kỹ thuật trong đó một hàm trực tiếp hoặc gián tiếp gọi lại chính nó để giải quyết một bài toán.\n\nMột thuật toán đệ quy thường có hai thành phần:\n\n**Điều kiện dừng (Base Case):** Xác định thời điểm thuật toán kết thúc việc gọi đệ quy.\n**Bước đệ quy (Recursive Case):** Tiếp tục giải quyết bài toán thông qua một lời gọi hàm mới với dữ liệu đã được biến đổi.\n\nVí dụ, giai thừa của số nguyên không âm ■ được định nghĩa:\n\n■\n\nCó thể biểu diễn bằng ngôn ngữ C:\n\nunsigned long long factorial(unsigned int n) {\nif (n == 0) {\nreturn 1;\n}\n\nreturn n * factorial(n - 1);\n}\n\n\nĐây là một hàm đệ quy trực tiếp vì `factorial` gọi lại chính `factorial`.\n\nVới `n = 4`, quá trình tính toán về mặt logic như sau:\n\nfactorial(4)\n4 * factorial(3)\n3 * factorial(2)\n2 * factorial(1)\n1 * factorial(0)\n1\n\n\nKhi đến điều kiện dừng, các lời gọi lần lượt hoàn thành theo chiều ngược lại:\n\nfactorial(0) = 1\nfactorial(1) = 1 * 1 = 1\nfactorial(2) = 2 * 1 = 2\nfactorial(3) = 3 * 2 = 6\nfactorial(4) = 4 * 6 = 24\n\n\nVí dụ này thể hiện đặc trưng của đệ quy thông thường: sau khi lời gọi đệ quy trả về, hàm gọi vẫn cần thực hiện thêm một phép toán.\n\n### 1.2. Khung ngăn xếp (Stack Frame)\n\nKhi một chương trình thực hiện lời gọi hàm, hệ thống thực thi thường cần duy trì thông tin phục vụ việc chuyển quyền điều khiển và quay trở lại hàm gọi.\n\nNhững thông tin này có thể bao gồm:\n\nĐịa chỉ trả về (Return Address).\nCác biến cục bộ cần được lưu trong bộ nhớ.\nGiá trị thanh ghi cần bảo toàn.\nTham số không được truyền hoàn toàn qua thanh ghi.\nVùng nhớ tạm phục vụ tính toán.\nDữ liệu phục vụ cơ chế gỡ lỗi hoặc xử lý ngoại lệ.\n\nTập hợp vùng nhớ và trạng thái phục vụ một lần thực thi hàm thường được gọi là khung ngăn xếp.\n\nCấu trúc cụ thể phụ thuộc vào kiến trúc CPU, quy ước gọi hàm, trình biên dịch và mức tối ưu.\n\nKhông phải mọi lời gọi hàm đều nhất thiết tạo ra một khung ngăn xếp riêng trong bộ nhớ. Tuy nhiên, nếu không được tối ưu, lời gọi đệ quy thường khiến nhiều trạng thái thực thi phải được duy trì đồng thời.\n\nVí dụ minh họa:\n\nNgăn xếp khi factorial(4) gọi xuống factorial(0)\n\n┌─────────────────────────┐\n│ factorial(0)            │\n├─────────────────────────┤\n│ factorial(1)            │\n├─────────────────────────┤\n│ factorial(2)            │\n├─────────────────────────┤\n│ factorial(3)            │\n├─────────────────────────┤\n│ factorial(4)            │\n├─────────────────────────┤\n│ Hàm gọi factorial(4)    │\n└─────────────────────────┘\n\n\nĐây là sơ đồ logic, không phải cách bố trí byte thực tế của một ABI cụ thể.\n\nKhi độ sâu đệ quy tăng, số lượng trạng thái cần duy trì cũng có thể tăng theo.\n\nNếu mỗi lần gọi cần một lượng bộ nhớ ngăn xếp nhất định, tổng mức sử dụng có thể xấp xỉ:\n\n■\n\nTrong đó:\n\n■: tổng dung lượng ngăn xếp liên quan đến chuỗi lời gọi.\n■: dung lượng ban đầu.\n■: số lần gọi đệ quy đang hoạt động.\n■: dung lượng trung bình cần duy trì cho mỗi lần gọi.\n\nĐây là mô hình đơn giản hóa, phù hợp với trường hợp các khung có kích thước gần như cố định và chưa được tối ưu.\n\n## 2. Đệ quy đuôi là gì?\n\n### 2.1. Khái niệm vị trí đuôi\n\nVị trí đuôi (Tail Position) là vị trí trong quá trình đánh giá biểu thức mà kết quả của biểu thức đó được sử dụng trực tiếp làm kết quả của hàm hiện tại, không còn phép tính tiếp theo phải thực hiện sau khi biểu thức kết thúc.\n\nMột lời gọi hàm ở vị trí đuôi được gọi là lời gọi đuôi (Tail Call).\n\nVí dụ:\n\nint f(int x) {\nreturn g(x);\n}\n\n\nỞ đây, lời gọi `g(x)` nằm tại vị trí đuôi vì kết quả của `g` được trả về trực tiếp.\n\nNgược lại:\n\nint f(int x) {\nreturn g(x) + 1;\n}\n\n\nLời gọi `g(x)` không nằm tại vị trí đuôi vì sau khi `g` trả về, hàm `f` vẫn phải thực hiện phép cộng với `1`.\n\n**Điểm quyết định không phải là lời gọi hàm có xuất hiện ở dòng cuối hay không, mà là còn công việc nào phải thực hiện sau khi lời gọi kết thúc hay không.**\n\n### 2.2. Đệ quy đuôi\n\nĐệ quy đuôi (Tail Recursion) là trường hợp một hàm tự gọi lại chính nó và lời gọi đó nằm tại vị trí đuôi.\n\nCó thể viết lại hàm tính giai thừa bằng cách sử dụng biến tích lũy (Accumulator):\n\nunsigned long long factorial_acc(\nunsigned int n,\nunsigned long long acc\n) {\nif (n == 0) {\nreturn acc;\n}\n\nreturn factorial_acc(n - 1, acc * n);\n}\n\nunsigned long long factorial(unsigned int n) {\nreturn factorial_acc(n, 1);\n}\n\n\nKhi gọi `factorial(4)`, các trạng thái logic thay đổi như sau:\n\n| Lần gọi | n | acc |\n|---|---:|---:|\n| 1 | 4 | 1 |\n| 2 | 3 | 4 |\n| 3 | 2 | 12 |\n| 4 | 1 | 24 |\n| 5 | 0 | 24 |\n\nTại mỗi bước, kết quả trung gian đã được tích lũy trong tham số `acc`.\n\nKhông cần giữ lại phép nhân để thực hiện sau khi lời gọi đệ quy trả về.\n\nLời gọi:\n\nreturn factorial_acc(n - 1, acc * n);\n\n\nnằm tại vị trí đuôi.\n\nVì vậy, hàm có cấu trúc phù hợp với tối ưu hóa đệ quy đuôi.\n\nVí dụ trên dùng số nguyên không dấu 64 bit theo cách biểu diễn thông thường của `unsigned long long`; kết quả chỉ còn chính xác trong phạm vi kiểu dữ liệu. Với hệ thống mà kiểu này có 64 bit, `20!` còn biểu diễn được, còn `21!` vượt phạm vi.\n\n### 2.3. Đệ quy đuôi và lời gọi đuôi không đồng nhất\n\nLời gọi đuôi không bắt buộc phải là lời gọi đệ quy.\n\nVí dụ:\n\nint process(int x) {\nreturn calculate(x);\n}\n\n\n`process` gọi `calculate` ở vị trí đuôi, nhưng đây không phải đệ quy.\n\nTrong khi đó:\n\nint countdown(int n) {\nif (n == 0) {\nreturn 0;\n}\n\nreturn countdown(n - 1);\n}\n\n\nlà đệ quy đuôi.\n\nDo đó, cần sử dụng thuật ngữ chính xác:\n\n| Thuật ngữ | Ý nghĩa |\n|---|---|\n| Lời gọi đuôi (Tail Call) | Lời gọi hàm ở vị trí đuôi |\n| Đệ quy đuôi (Tail Recursion) | Hàm tự gọi lại tại vị trí đuôi |\n| Tối ưu hóa lời gọi đuôi (TCO) | Tối ưu quá trình thực hiện lời gọi đuôi |\n| Loại bỏ đệ quy đuôi (TRE) | Chuyển hoặc tối ưu chuỗi tự gọi đệ quy đuôi, thường thành vòng lặp |\n\n## 3. Tối ưu hóa lời gọi đuôi là gì?\n\n### 3.1. Nguyên lý\n\nTối ưu hóa lời gọi đuôi là kỹ thuật cho phép trình biên dịch thực hiện một lời gọi hàm ở vị trí đuôi mà không cần tiếp tục giữ trạng thái của hàm gọi như trong một chuỗi lời gọi thông thường.\n\nKhi hàm gọi không còn công việc nào phải thực hiện sau lời gọi đuôi, trong những điều kiện thích hợp, trình biên dịch có thể kết thúc hoặc tái sử dụng trạng thái thực thi hiện tại trước khi chuyển quyền điều khiển sang hàm được gọi.\n\nVí dụ:\n\nint f(int x) {\nreturn g(x);\n}\n\n\nTrong cách thực hiện thông thường, có thể hình dung:\n\nf gọi g\ng thực hiện\ng trả về f\nf trả về hàm trước đó\n\n\nSau khi áp dụng tối ưu hóa lời gọi đuôi, quá trình có thể được tổ chức thành:\n\nf chuẩn bị tham số cho g\nf kết thúc hoặc giải phóng trạng thái không còn cần thiết\nchuyển trực tiếp sang g\ng trả về hàm đã gọi f\n\n\nNhư vậy, lời gọi `g` không nhất thiết cần một tầng ngăn xếp mới nằm phía trên khung thực thi còn hoạt động của `f`.\n\n### 3.2. So sánh mức sử dụng ngăn xếp\n\n**Không tối ưu:**\n\n┌───────────────────┐\n│ factorial_acc(0)  │\n├───────────────────┤\n│ factorial_acc(1)  │\n├───────────────────┤\n│ factorial_acc(2)  │\n├───────────────────┤\n│ factorial_acc(3)  │\n├───────────────────┤\n│ factorial_acc(4)  │\n└───────────────────┘\n\n\n**Sau khi loại bỏ đệ quy đuôi:**\n\n┌──────────────────────────┐\n│ Một trạng thái thực thi  │\n│ factorial_acc            │\n│                          │\n│ n và acc được cập nhật   │\n│ qua các vòng lặp         │\n└──────────────────────────┘\n\n\nĐối với kiểu tối ưu chuyển đệ quy thành vòng lặp và không sử dụng bộ nhớ phụ tăng theo độ sâu, dung lượng ngăn xếp của quá trình lặp có thể duy trì gần như không đổi.\n\nĐây là lợi ích quan trọng nhất của kỹ thuật này.\n\n### 3.3. Độ phức tạp bộ nhớ\n\nĐối với hàm đệ quy có độ sâu tỷ lệ với ■:\n\nNếu mỗi lần gọi phải duy trì một khung riêng, mức sử dụng ngăn xếp thường là ■.\nNếu đệ quy đuôi được loại bỏ thành vòng lặp với trạng thái có kích thước cố định, mức sử dụng ngăn xếp có thể là ■.\n\nTuy nhiên, ■ chỉ mô tả bộ nhớ ngăn xếp phục vụ cơ chế lặp trong những giả thiết nêu trên, không có nghĩa tổng bộ nhớ của mọi thuật toán đệ quy đuôi đều là hằng số.\n\nDữ liệu được cấp phát trên heap, cấu trúc tích lũy hoặc các đối tượng trung gian vẫn có thể sử dụng bộ nhớ tăng theo kích thước đầu vào.\n\n## 4. Cơ chế loại bỏ đệ quy đuôi\n\n### 4.1. Chuyển lời gọi đệ quy thành vòng lặp\n\nMột trong những cách triển khai phổ biến của TRE là biến lời gọi tự đệ quy thành bước nhảy trở lại đầu hàm hoặc một khối lặp tương đương.\n\nXét hàm:\n\nunsigned int sum_tail(\nunsigned int n,\nunsigned int acc\n) {\nif (n == 0) {\nreturn acc;\n}\n\nreturn sum_tail(n - 1, acc + n);\n}\n\n\nVề mặt logic, có thể chuyển đổi thành:\n\nunsigned int sum_loop(\nunsigned int n,\nunsigned int acc\n) {\nwhile (n != 0) {\nacc += n;\nn -= 1;\n}\n\nreturn acc;\n}\n\n\nTrong phiên bản thứ hai, không còn lời gọi tự đệ quy.\n\nCác giá trị trạng thái được cập nhật trực tiếp trong vòng lặp.\n\nBằng cách này, trình biên dịch không cần tạo thêm một trạng thái gọi hàm cho mỗi lần lặp.\n\n### 4.2. Quá trình biến đổi ở mức biểu diễn trung gian\n\nTrong trình biên dịch, mã nguồn thường được chuyển thành biểu diễn trung gian (Intermediate Representation – IR) trước khi sinh mã máy.\n\nHàm đệ quy đuôi có thể được biểu diễn bằng một khối chứa lời gọi tự đệ quy, sau đó là lệnh trả về.\n\nQuá trình tối ưu có thể thay lời gọi bằng việc cập nhật trạng thái và chuyển quyền điều khiển về khối đầu hàm.\n\nTài liệu LLVM mô tả phép tối ưu `tailcallelim` như sau:\n\nThis file transforms calls of the current function (self recursion) followed by a return instruction with a branch to the entry of the function, creating a loop.\n\n_(Dịch nghĩa: Phép biến đổi này thay những lời gọi tự đệ quy của hàm hiện tại, theo sau bởi lệnh trả về, bằng bước nhảy đến điểm bắt đầu của hàm, qua đó tạo thành một vòng lặp.)_\n\nNguồn: LLVM, _LLVM's Analysis and Transform Passes_, mục `tailcallelim`.[^1]\n\nNgoài trường hợp cơ bản, LLVM còn mô tả các khả năng như xử lý một số lệnh đơn giản nằm giữa lời gọi và lệnh trả về, hoặc sử dụng biến tích lũy trong những trường hợp phép toán cho phép chuyển đổi hợp lệ.\n\nĐiều đó cho thấy tối ưu hóa đệ quy đuôi không nhất thiết chỉ là việc thay trực tiếp một lệnh gọi hàm bằng một lệnh nhảy.\n\n### 4.3. Ảnh hưởng đến mã máy x86-64\n\nTrên kiến trúc x86-64, các lệnh thường gặp trong cơ chế gọi hàm bao gồm:\n\n`call`: Gọi hàm, đồng thời lưu thông tin địa chỉ trả về theo cơ chế của kiến trúc.\n`ret`: Trả quyền điều khiển về địa chỉ trả về.\n`jmp`: Chuyển quyền điều khiển trực tiếp đến một địa chỉ khác.\n\nXét đoạn mã minh họa:\n\nextern int calculate(int x);\n\nint process(int x) {\nreturn calculate(x);\n}\n\n\nTrong trường hợp phù hợp về ABI và các điều kiện tối ưu khác, trình biên dịch có thể sinh mã tương tự:\n\nprocess:\njmp calculate\n\n\nThay vì:\n\nprocess:\ncall calculate\nret\n\n\nSơ đồ này minh họa sự khác nhau về luồng điều khiển, không phải kết quả biên dịch được bảo đảm cho mọi trình biên dịch và mọi nền tảng.\n\nTrong cách thực hiện dùng `jmp`, hàm `calculate` có thể trả kết quả trực tiếp về nơi đã gọi `process`, với điều kiện trạng thái máy đã được chuẩn bị phù hợp.\n\nTrên thực tế, trình biên dịch có thể cần giải phóng vùng nhớ ngăn xếp, khôi phục thanh ghi hoặc sắp xếp lại tham số trước khi thực hiện bước nhảy.\n\n### 4.4. Ảnh hưởng đến mã máy ARM64\n\nTrên kiến trúc AArch64, những lệnh thường gặp gồm:\n\n| Lệnh | Chức năng |\n|---|---|\n| `BL` | Gọi hàm và ghi địa chỉ trả về vào thanh ghi liên kết |\n| `B` | Nhảy trực tiếp mà không cập nhật thanh ghi liên kết |\n| `RET` | Trả quyền điều khiển theo thanh ghi địa chỉ trả về |\n\nThông thường, thanh ghi `X30` được sử dụng làm thanh ghi liên kết (Link Register).\n\nVới một lời gọi đuôi hợp lệ, trình biên dịch có thể thực hiện bước nhảy thay cho cơ chế gọi hàm thông thường.\n\nVí dụ mã máy minh họa:\n\nprocess:\nb calculate\n\n\nThay cho dạng:\n\nprocess:\nbl calculate\nret\n\n\nTrong trường hợp sử dụng `B`, trình biên dịch phải bảo đảm địa chỉ trả về ban đầu vẫn còn hợp lệ, đồng thời tuân thủ quy ước gọi hàm của nền tảng.\n\nCơ chế này có thể giúp tránh phát sinh thêm một tầng gọi hàm không cần thiết.\n\n## 5. Điều kiện để áp dụng tối ưu hóa lời gọi đuôi\n\n### 5.1. Lời gọi phải thực sự ở vị trí đuôi\n\nĐiều kiện đầu tiên là hàm gọi không còn công việc phải thực hiện sau khi lời gọi kết thúc.\n\nVí dụ có thể tối ưu:\n\nint f(int x) {\nreturn g(x);\n}\n\n\nVí dụ không phải lời gọi đuôi:\n\nint f(int x) {\nreturn g(x) * 2;\n}\n\n\nTrong ví dụ thứ hai, `f` vẫn phải thực hiện phép nhân.\n\nTuy nhiên, trình biên dịch có thể thực hiện những phép biến đổi khác để loại bỏ đệ quy trong một số trường hợp. Vì vậy, việc lời gọi ban đầu không nằm tại vị trí đuôi không đồng nghĩa với việc không tồn tại bất kỳ phương án tối ưu nào.\n\n### 5.2. Phải tuân thủ quy ước gọi hàm\n\nQuy ước gọi hàm (Calling Convention) xác định cách truyền tham số, trả kết quả và bảo toàn trạng thái máy khi chuyển quyền điều khiển giữa các hàm.\n\nCác yêu cầu thường liên quan đến:\n\nThanh ghi được dùng để truyền tham số.\nThanh ghi phải được hàm gọi hoặc hàm được gọi bảo toàn.\nCách truyền giá trị trả về.\nVị trí của tham số truyền qua ngăn xếp.\nYêu cầu căn chỉnh ngăn xếp.\nCách xử lý đối số biến thiên.\nCấu trúc dữ liệu trả về có kích thước lớn.\n\nMột lời gọi có thể ở vị trí đuôi về mặt ngữ nghĩa, nhưng việc thực hiện nó dưới dạng bước nhảy trực tiếp vẫn có thể không hợp lệ nếu những yêu cầu ABI chưa được đáp ứng.\n\n### 5.3. Vòng đời của biến cục bộ\n\nTrong một số trường hợp, hàm được gọi có thể tiếp tục truy cập dữ liệu thuộc khung ngăn xếp của hàm gọi.\n\nVí dụ:\n\nextern int use_pointer(const int *p);\n\nint f(void) {\nint value = 10;\nreturn use_pointer(&value);\n}\n\n\nỞ đây, `use_pointer` nhận địa chỉ của biến cục bộ `value`.\n\nViệc giải phóng khung ngăn xếp của `f` trước khi `use_pointer` kết thúc có thể khiến con trỏ không còn trỏ đến vùng nhớ hợp lệ.\n\nDo đó, trình biên dịch không thể tùy tiện áp dụng phép biến đổi hủy khung gọi hiện tại nếu điều đó làm thay đổi vòng đời dữ liệu.\n\nĐây là một ví dụ về giới hạn an toàn của tối ưu hóa lời gọi đuôi.\n\n### 5.4. Trạng thái dọn dẹp và xử lý ngoại lệ\n\nMột số ngôn ngữ và môi trường thực thi yêu cầu thực hiện công việc bổ sung khi thoát khỏi hàm.\n\nVí dụ:\n\nChạy hàm hủy đối tượng.\nGiải phóng tài nguyên theo phạm vi.\nThực hiện khối `finally`.\nCập nhật trạng thái xử lý ngoại lệ.\nThực hiện các thao tác bảo vệ ngăn xếp.\n\nNếu những thao tác này phải xảy ra sau khi lời gọi hàm kết thúc, lời gọi có thể không còn đủ điều kiện thực hiện như một tail call trực tiếp.\n\nMột trình biên dịch có thể xử lý bằng các phép biến đổi khác khi hợp lệ, nhưng tính đúng đắn ngữ nghĩa luôn phải được duy trì.\n\n### 5.5. Giới hạn của nền tảng\n\nNgay cả khi mã nguồn có cấu trúc phù hợp, việc tối ưu vẫn có thể phụ thuộc vào:\n\nKiến trúc CPU.\nABI của hệ điều hành.\nBackend sinh mã.\nMức tối ưu.\nQuy ước gọi hàm.\nKiểu dữ liệu trả về.\nCác thuộc tính đặc biệt của hàm.\n\nVì vậy, không thể khẳng định rằng mọi hàm đệ quy đuôi đều tự động được chuyển thành vòng lặp trong mọi trình biên dịch.\n\n## 6. Tối ưu hóa đệ quy đuôi trong GCC và LLVM\n\n### 6.1. GCC\n\nGCC cung cấp tùy chọn:\n\n-foptimize-sibling-calls\n\n\nTài liệu GCC mô tả:\n\nOptimize sibling and tail recursive calls.\n\n_(Dịch nghĩa: Tối ưu hóa các lời gọi hàm ngang cấp và những lời gọi đệ quy đuôi.)_\n\nTheo tài liệu GCC 14.3, tùy chọn này được bật tại các mức tối ưu `-O2`, `-O3` và `-Os`.[^2]\n\nVí dụ:\n\ngcc -O2 -S example.c -o example.s\n\n\nLệnh trên yêu cầu GCC sinh mã hợp ngữ để có thể kiểm tra kết quả tối ưu.\n\nViệc bật tùy chọn không bảo đảm mọi lời gọi đuôi đều được tối ưu thành công. Quyết định cuối cùng còn phụ thuộc vào điều kiện hợp lệ của từng lời gọi và khả năng của backend.\n\n### 6.2. LLVM\n\nLLVM hỗ trợ nhiều cơ chế liên quan đến lời gọi đuôi.\n\nTrong LLVM IR, lời gọi có thể mang những dấu hiệu như:\n\n| Dấu hiệu | Ý nghĩa |\n|---|---|\n| `tail` | Đánh dấu một lời gọi là ứng viên cho tối ưu hóa đuôi |\n| `musttail` | Yêu cầu bảo đảm lời gọi đuôi theo các điều kiện được đặc tả |\n| `notail` | Ngăn bộ tối ưu gắn dấu hiệu tối ưu lời gọi đuôi |\n\nVí dụ minh họa LLVM IR:\n\ndefine i32 @f(i32 %x) {\nentry:\n%result = tail call i32 @g(i32 %x)\nret i32 %result\n}\n\ndeclare i32 @g(i32)\n\n\nDấu hiệu `tail` không phải sự bảo đảm tuyệt đối rằng mã máy cuối cùng sẽ thực hiện lời gọi theo dạng tối ưu.\n\nĐối với `musttail`, LLVM đặt ra những điều kiện nghiêm ngặt hơn về vị trí lời gọi, kiểu hàm, quy ước gọi hàm và các thuộc tính ảnh hưởng ABI.\n\nTài liệu ngôn ngữ LLVM quy định rằng `musttail` phải được tối ưu phù hợp để bảo đảm tính đúng đắn của chương trình; đặc biệt, chuỗi đệ quy thông qua các lời gọi `musttail` hợp lệ không được gây tăng trưởng ngăn xếp không giới hạn chỉ vì những lời gọi đó.[^3]\n\n### 6.3. Đệ quy đuôi được bảo đảm và đệ quy đuôi có thể tối ưu\n\nCần xác định sự khác nhau giữa ba trường hợp:\n\n**Trường hợp thứ nhất:** Mã nguồn có cấu trúc đệ quy đuôi, nhưng ngôn ngữ không yêu cầu trình biên dịch tối ưu.\n\n**Trường hợp thứ hai:** Trình biên dịch nhận diện lời gọi đuôi và tối ưu khi điều kiện cho phép.\n\n**Trường hợp thứ ba:** Ngôn ngữ hoặc cơ chế IR đặt ra yêu cầu bảo đảm lời gọi đuôi, trong phạm vi các điều kiện được quy định.\n\nĐiều này đặc biệt quan trọng đối với những chương trình sử dụng đệ quy sâu như một cơ chế điều khiển chính.\n\n### 6.4. Ngôn ngữ Scheme và đệ quy đuôi đúng nghĩa\n\nScheme là một ví dụ quan trọng vì đặc tả ngôn ngữ có yêu cầu rõ ràng về đệ quy đuôi đúng nghĩa (Proper Tail Recursion).\n\nBáo cáo R5RS nêu:\n\nImplementations of Scheme are required to be properly tail-recursive.\n\n_(Dịch nghĩa: Các bản triển khai của ngôn ngữ Scheme bắt buộc phải hỗ trợ đệ quy đuôi đúng nghĩa.)_\n\nNguồn: _Revised⁵ Report on the Algorithmic Language Scheme_, mục 3.5.[^4]\n\nTrong Scheme, hỗ trợ đệ quy đuôi không chỉ là một lựa chọn cải thiện hiệu năng, mà là một phần trong yêu cầu về hành vi của bản triển khai.\n\nĐặc tả yêu cầu hỗ trợ số lượng không bị giới hạn trước của các lời gọi đuôi đang hoạt động, trong ý nghĩa kỹ thuật được định nghĩa bởi ngôn ngữ.\n\nĐiều đó không có nghĩa chương trình có bộ nhớ vô hạn, mà là chuỗi lời gọi đuôi không được buộc phải tiêu thụ thêm không gian chỉ để duy trì những tầng tiếp diễn không cần thiết.\n\n## 7. Tác động đến hiệu năng và bộ nhớ\n\n### 7.1. Bộ nhớ ngăn xếp\n\nTác động nổi bật nhất của tối ưu hóa lời gọi đuôi là hạn chế sự gia tăng bộ nhớ ngăn xếp.\n\nKhi chuyển một chuỗi tự đệ quy đuôi thành vòng lặp, chương trình có thể tránh việc duy trì nhiều khung gọi hàm đồng thời.\n\nĐây là lợi ích quan trọng đối với:\n\nThuật toán xử lý chuỗi có độ dài lớn.\nBộ thông dịch và máy ảo.\nCác thuật toán duyệt cấu trúc dữ liệu.\nNhững ngôn ngữ lập trình hàm.\nCác hệ thống sử dụng hàm như đơn vị điều khiển thay cho vòng lặp.\n\n### 7.2. Chi phí gọi hàm\n\nKhi loại bỏ được lời gọi hàm thông thường, trình biên dịch có thể giảm một phần chi phí liên quan đến:\n\nLưu và khôi phục địa chỉ trả về.\nThiết lập hoặc tháo dỡ khung ngăn xếp.\nBảo toàn một số thanh ghi.\nChuyển quyền điều khiển qua nhiều tầng gọi.\n\nTuy nhiên, mức cải thiện thực tế phụ thuộc vào kiến trúc CPU, mã máy được sinh và đặc điểm chương trình.\n\nKhông phải mọi lời gọi đuôi được tối ưu đều nhanh hơn đáng kể so với lời gọi thông thường.\n\n### 7.3. Độ phức tạp thời gian\n\nĐối với ví dụ tính giai thừa, việc chuyển từ đệ quy thông thường sang đệ quy đuôi không làm thay đổi số phép nhân cần thực hiện.\n\nĐộ phức tạp thời gian vẫn là:\n\n■\n\nNếu được chuyển thành vòng lặp, độ phức tạp bộ nhớ ngăn xếp có thể giảm từ ■ xuống ■, trong điều kiện mỗi bước chỉ duy trì một lượng trạng thái cố định.\n\nNhư vậy, tối ưu hóa lời gọi đuôi chủ yếu cải thiện cơ chế thực thi và mức sử dụng tài nguyên, chứ không nhất thiết thay đổi độ phức tạp thời gian của thuật toán.\n\n## 8. Những giới hạn và vấn đề cần lưu ý\n\n### 8.1. Không phải mọi đệ quy đều là đệ quy đuôi\n\nVí dụ:\n\nunsigned long long factorial(unsigned int n) {\nif (n == 0) {\nreturn 1;\n}\n\nreturn n * factorial(n - 1);\n}\n\n\nLời gọi đệ quy không nằm tại vị trí đuôi vì vẫn còn phép nhân sau khi nhận kết quả.\n\nMột trình biên dịch có thể nhận diện và biến đổi một số dạng đệ quy như thế này, nhưng không thể xem đó là thuộc tính mặc định của mọi trình biên dịch.\n\n### 8.2. Đệ quy đuôi không đồng nghĩa với không bao giờ tràn ngăn xếp\n\nNếu một bản triển khai không thực hiện tối ưu hóa, một hàm đệ quy đuôi vẫn có thể tạo ra chuỗi lời gọi làm tăng mức sử dụng ngăn xếp.\n\nNgoài ra, chương trình còn có thể sử dụng ngăn xếp cho những hoạt động khác.\n\nVì vậy, cần xem xét cả hình thức mã nguồn lẫn bảo đảm của trình biên dịch và môi trường thực thi.\n\n### 8.3. Tối ưu hóa có thể làm thay đổi cách quan sát khi gỡ lỗi\n\nKhi lời gọi hàm được thay bằng bước nhảy hoặc vòng lặp, chuỗi lời gọi quan sát được trong trình gỡ lỗi có thể khác với cấu trúc hàm ban đầu.\n\nMột số khung gọi có thể không xuất hiện như khi biên dịch ở chế độ không tối ưu.\n\nĐiều này có thể ảnh hưởng đến:\n\nViệc quan sát ngăn xếp lời gọi (Call Stack).\nTheo dõi thứ tự thực hiện hàm.\nPhân tích thông tin khung gọi.\nĐọc kết quả lấy mẫu hiệu năng.\n\nCác trình biên dịch và công cụ gỡ lỗi có thể sử dụng thông tin bổ sung để hỗ trợ việc quan sát mã đã tối ưu, nhưng không phải lúc nào cũng tái hiện được đầy đủ chuỗi lời gọi theo mã nguồn.\n\n### 8.4. Tối ưu hóa lời gọi đuôi không thay thế mọi hình thức tối ưu khác\n\nCác kỹ thuật như nội tuyến hàm (Inlining), lan truyền hằng số (Constant Propagation), loại bỏ mã chết (Dead Code Elimination) và tối ưu vòng lặp vẫn có thể tác động đến cùng một đoạn chương trình.\n\nMột hàm đệ quy có thể được biến đổi bởi nhiều phép tối ưu kết hợp.\n\nDo đó, khi phân tích mã máy, không nên mặc nhiên gán mọi trường hợp không còn lời gọi đệ quy cho một phép tối ưu duy nhất.\n\n## 9. Kiểm chứng tối ưu hóa trong thực tế\n\n### 9.1. Chương trình thử nghiệm\n\nCó thể sử dụng đoạn mã sau:\n\n__attribute__((noinline))\nunsigned long long sum_tail(\nunsigned int n,\nunsigned long long acc\n) {\nif (n == 0) {\nreturn acc;\n}\n\nreturn sum_tail(n - 1, acc + n);\n}\n\nint main(void) {\nreturn sum_tail(10, 0) != 55;\n}\n\n\nThuộc tính `noinline` trong GCC hoặc Clang được dùng để hạn chế việc hàm bị nội tuyến, giúp quan sát riêng mã của hàm rõ hơn.\n\nTuy nhiên, thuộc tính này không cấm các tối ưu hóa khác, bao gồm việc loại bỏ đệ quy đuôi.\n\n### 9.2. Biên dịch bằng GCC\n\ngcc -O0 -S test.c -o test_O0.s\ngcc -O2 -S test.c -o test_O2.s\n\n\nSau đó, so sánh mã hợp ngữ của hàm `sum_tail`.\n\nỞ mức tối ưu thấp, mã thường giữ lại lời gọi tự đệ quy.\n\nỞ mức tối ưu cao, trình biên dịch có thể chuyển hàm thành vòng lặp và không còn lời gọi tự đệ quy.\n\nKết quả cụ thể phụ thuộc vào phiên bản GCC, kiến trúc đích và các tùy chọn biên dịch.\n\n### 9.3. Biên dịch bằng Clang\n\nclang -O0 -S test.c -o test_O0.s\nclang -O2 -S test.c -o test_O2.s\n\n\nCó thể kiểm tra biểu diễn LLVM IR:\n\nclang -O2 -S -emit-llvm test.c -o test.ll\n\n\nKhi đọc kết quả, cần tìm những dấu hiệu như:\n\nKhối lặp thay thế lời gọi đệ quy.\nLời gọi đuôi được đánh dấu trong IR.\nLệnh nhảy thay cho chuỗi gọi và trả về trong mã máy.\nSự thay đổi trong việc thiết lập khung ngăn xếp.\n\nĐây là các dấu hiệu cần phân tích cùng nhau, thay vì chỉ dựa vào sự xuất hiện của một lệnh cụ thể.\n\n## 10. Kết luận\n\nTối ưu hóa lời gọi đuôi là một kỹ thuật quan trọng trong thiết kế và triển khai trình biên dịch.\n\nKỹ thuật này khai thác đặc điểm của những lời gọi hàm không còn công việc phải thực hiện sau khi kết thúc, từ đó cho phép loại bỏ việc duy trì những trạng thái gọi hàm không cần thiết.\n\nTrong trường hợp đệ quy đuôi, trình biên dịch có thể chuyển lời gọi tự đệ quy thành vòng lặp, giúp giảm mức sử dụng bộ nhớ ngăn xếp và tránh sự gia tăng số lượng khung gọi theo độ sâu đệ quy.\n\nTuy nhiên, khả năng tối ưu phụ thuộc vào nhiều điều kiện, bao gồm cấu trúc chương trình, vòng đời dữ liệu, quy ước gọi hàm, ABI và khả năng của backend sinh mã.\n\nSự khác nhau giữa lời gọi đuôi, đệ quy đuôi, tối ưu hóa lời gọi đuôi và loại bỏ đệ quy đuôi là cơ sở cần thiết để hiểu đúng cơ chế này.\n\nĐối với nghiên cứu trình biên dịch, kỹ thuật tối ưu hóa lời gọi đuôi cũng là ví dụ tiêu biểu cho mối quan hệ giữa ngữ nghĩa ngôn ngữ lập trình, biểu diễn trung gian, phân tích luồng điều khiển và quá trình sinh mã máy.\n\n\n\n## Phụ lục A. Thuật ngữ kỹ thuật\n\n| Thuật ngữ tiếng Việt | Thuật ngữ tiếng Anh | Ý nghĩa |\n|---|---|---|\n| Đệ quy | Recursion | Hàm trực tiếp hoặc gián tiếp gọi lại chính nó |\n| Vị trí đuôi | Tail Position | Vị trí mà kết quả được dùng trực tiếp làm kết quả của hàm |\n| Lời gọi đuôi | Tail Call | Lời gọi hàm ở vị trí đuôi |\n| Đệ quy đuôi | Tail Recursion | Lời gọi tự đệ quy ở vị trí đuôi |\n| Tối ưu hóa lời gọi đuôi | Tail Call Optimization | Tối ưu lời gọi đuôi để tránh duy trì khung gọi không cần thiết |\n| Loại bỏ đệ quy đuôi | Tail Recursion Elimination | Biến đổi hoặc loại bỏ lời gọi tự đệ quy đuôi |\n| Khung ngăn xếp | Stack Frame | Trạng thái và vùng nhớ phục vụ một lần thực thi hàm |\n| Quy ước gọi hàm | Calling Convention | Quy tắc truyền tham số, trả kết quả và bảo toàn trạng thái máy |\n| Giao diện nhị phân ứng dụng | Application Binary Interface | Quy định tương tác nhị phân giữa các thành phần chương trình |\n| Biểu diễn trung gian | Intermediate Representation | Dạng biểu diễn chương trình phục vụ phân tích và tối ưu |\n| Biến tích lũy | Accumulator | Giá trị duy trì kết quả trung gian qua các bước tính toán |\n| Địa chỉ trả về | Return Address | Vị trí chương trình tiếp tục sau khi lời gọi hoàn thành |\n| Nội tuyến hàm | Inlining | Thay lời gọi hàm bằng nội dung được biến đổi từ thân hàm |\n\n## Phụ lục B. Tài liệu tham khảo và nghiên cứu mở rộng\n\n### B.1. Đặc tả và tài liệu trình biên dịch\n\n**[1] LLVM Project, *LLVM's Analysis and Transform Passes*.**\n\nMục `tailcallelim` giải thích phép biến đổi lời gọi tự đệ quy thành vòng lặp và một số mở rộng của thuật toán.\n\nhttps://llvm.org/docs/Passes.html\n\n**[2] GNU Compiler Collection, *Optimize Options*.**\n\nTài liệu về tùy chọn `-foptimize-sibling-calls`, mức tối ưu và những phép tối ưu liên quan.\n\nhttps://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html\n\n**[3] LLVM Project, *LLVM Language Reference Manual*.**\n\nĐặc tả ngôn ngữ LLVM IR, bao gồm dấu hiệu `tail`, `musttail`, `notail`, các quy ước gọi hàm và điều kiện tối ưu lời gọi đuôi.\n\nhttps://llvm.org/docs/LangRef.html\n\n**[4] Clang Project, *Attribute Reference*.**\n\nTài liệu về thuộc tính `musttail`, những điều kiện áp dụng và bảo đảm của trình biên dịch.\n\nhttps://clang.llvm.org/docs/AttributeReference.html\n\n### B.2. Ngôn ngữ lập trình và ngữ nghĩa lời gọi đuôi\n\n**[5] Richard Kelsey, William Clinger và Jonathan Rees (biên tập), *Revised⁵ Report on the Algorithmic Language Scheme*, 1998.**\n\nMục 3.5, _Proper Tail Recursion_, trình bày yêu cầu chính thức về đệ quy đuôi đúng nghĩa trong Scheme.\n\nhttps://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html\n\n**[6] Guy L. Steele Jr. và Gerald Jay Sussman, *Lambda: The Ultimate Imperative*, MIT Artificial Intelligence Laboratory, AI Memo 353, 1976.**\n\nMột công trình quan trọng trong lịch sử nghiên cứu ngôn ngữ Scheme, cơ chế tiếp diễn và các phương pháp thực thi lời gọi hàm.\n\n### B.3. Đặc tả kiến trúc và quy ước gọi hàm\n\n**[7] Arm Limited, *Procedure Call Standard for the Arm 64-bit Architecture (AAPCS64)*.**\n\nĐặc tả quy ước gọi hàm trên AArch64, bao gồm sử dụng thanh ghi, truyền tham số và tổ chức trạng thái khi gọi hàm.\n\nhttps://github.com/ARM-software/abi-aa/blob/main/aapcs64/aapcs64.rst\n\n**[8] System V Application Binary Interface, AMD64 Architecture Processor Supplement.**\n\nĐặc tả ABI dành cho x86-64 theo môi trường System V, bao gồm quy ước gọi hàm, thanh ghi và bố trí ngăn xếp.\n\nhttps://gitlab.com/x86-psABIs/x86-64-ABI\n\n**[9] Intel, *Intel 64 and IA-32 Architectures Software Developer's Manuals*.**\n\nTài liệu chính thức về tập lệnh x86, bao gồm `CALL`, `RET` và `JMP`.\n\nhttps://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html\n\n### B.4. Các chủ đề nghiên cứu tiếp theo\n\nKhung ngăn xếp (Stack Frame): Cấu trúc và vòng đời.\nTràn ngăn xếp (Stack Overflow): Nguyên nhân và cơ chế.\nGiao diện nhị phân ứng dụng (ABI): Các quy ước gọi hàm.\nBiểu diễn trung gian (IR): Phân tích và tối ưu luồng điều khiển.\nBộ liên kết (Linker): Vai trò trong quá trình biên dịch và thực thi chương trình.\n\n\n\n## Chú thích\n\n[^1]: LLVM Project, _LLVM's Analysis and Transform Passes_, mục `tailcallelim`. https://llvm.org/docs/Passes.html\n[^2]: GNU Compiler Collection, _Optimize Options_, tài liệu GCC 14.3, mục `-foptimize-sibling-calls`. https://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html\n[^3]: LLVM Project, _LLVM Language Reference Manual_, mục lệnh `call`, dấu hiệu `tail` và `musttail`. https://llvm.org/docs/LangRef.html\n[^4]: _Revised⁵ Report on the Algorithmic Language Scheme_, mục 3.5, _Proper Tail Recursion_. https://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html","html":"<h1>Tối ưu hóa đệ quy đuôi (Tail Call Optimization) là gì?</h1>\n<h2>Tóm tắt</h2>\n<p>Tối ưu hóa lời gọi đuôi (Tail Call Optimization – TCO) là kỹ thuật tối ưu trong trình biên dịch nhằm thực hiện lời gọi hàm ở vị trí đuôi mà không cần duy trì một khung ngăn xếp (Stack Frame) mới theo cơ chế gọi hàm thông thường. Khi áp dụng thành công, kỹ thuật này có thể hạn chế sự gia tăng bộ nhớ ngăn xếp, giảm chi phí gọi hàm và cho phép thực hiện những chuỗi lời gọi đuôi có độ sâu lớn.</p>\n<p>Trong trường hợp hàm tự gọi lại chính nó, kỹ thuật này thường được gọi cụ thể là tối ưu hóa đệ quy đuôi (Tail Recursion Optimization) hoặc loại bỏ lời gọi đệ quy đuôi (Tail Recursion Elimination – TRE).</p>\n<p>Bài viết trình bày nguyên lý của đệ quy đuôi, cơ chế hoạt động của ngăn xếp khi gọi hàm, phương pháp chuyển đổi đệ quy thành vòng lặp, những điều kiện cần thiết để tối ưu, ảnh hưởng của quy ước gọi hàm (Calling Convention) và giao diện nhị phân ứng dụng (Application Binary Interface – ABI). Đồng thời, bài viết đối chiếu cơ chế triển khai trong GCC và LLVM, phân tích mã máy trên các kiến trúc x86-64 và ARM64, cũng như những giới hạn của kỹ thuật này trong thực tế.</p>\n<p><strong>Từ khóa:</strong> tối ưu hóa lời gọi đuôi; đệ quy đuôi; trình biên dịch; khung ngăn xếp; loại bỏ đệ quy đuôi; LLVM; GCC; quy ước gọi hàm; mã máy.</p>\n<hr>\n<h2>1. Đệ quy và cơ chế gọi hàm</h2>\n<h3>1.1. Đệ quy là gì?</h3>\n<p>Đệ quy <span class=\"math-inline\" data-formula=\"Recursion\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.00773em;\">R</span><span class=\"mord mathnormal\">ec</span><span class=\"mord mathnormal\">u</span><span class=\"mord mathnormal\">rs</span><span class=\"mord mathnormal\">i</span><span class=\"mord mathnormal\">o</span><span class=\"mord mathnormal\">n</span></span></span></span></span> là kỹ thuật trong đó một hàm trực tiếp hoặc gián tiếp gọi lại chính nó để giải quyết một bài toán.</p>\n<p>Một thuật toán đệ quy thường có hai thành phần:</p>\n<ol>\n<li><strong>Điều kiện dừng (Base Case):</strong> Xác định thời điểm thuật toán kết thúc việc gọi đệ quy.</li>\n<li><strong>Bước đệ quy (Recursive Case):</strong> Tiếp tục giải quyết bài toán thông qua một lời gọi hàm mới với dữ liệu đã được biến đổi.</li>\n</ol>\n<p>Ví dụ, giai thừa của số nguyên không âm <span class=\"math-inline\" data-formula=\"n\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.4306em;\"></span><span class=\"mord mathnormal\">n</span></span></span></span></span> được định nghĩa:</p>\n<div class=\"math-display\" data-formula=\"n! =\n\\begin{cases}\n1 &amp; n = 0 \\\\\nn \\times (n-1)! &amp; n > 0\n\\end{cases}\"><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6944em;\"></span><span class=\"mord mathnormal\">n</span><span class=\"mclose\">!</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span><span class=\"mrel\">=</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span></span><span class=\"base\"><span class=\"strut\" style=\"height:3em;vertical-align:-1.25em;\"></span><span class=\"minner\"><span class=\"mopen delimcenter\" style=\"top:0em;\"><span class=\"delimsizing size4\">{</span></span><span class=\"mord\"><span class=\"mtable\"><span class=\"col-align-l\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:1.69em;\"><span style=\"top:-3.69em;\"><span class=\"pstrut\" style=\"height:3.008em;\"></span><span class=\"mord\"><span class=\"mord\">1</span></span></span><span style=\"top:-2.25em;\"><span class=\"pstrut\" style=\"height:3.008em;\"></span><span class=\"mord\"><span class=\"mord mathnormal\">n</span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span><span class=\"mbin\">×</span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span><span class=\"mopen\">(</span><span class=\"mord mathnormal\">n</span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span><span class=\"mbin\">−</span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span><span class=\"mord\">1</span><span class=\"mclose\">)!</span></span></span></span><span class=\"vlist-s\">​</span></span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:1.19em;\"><span></span></span></span></span></span><span class=\"arraycolsep\" style=\"width:1em;\"></span><span class=\"col-align-l\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:1.69em;\"><span style=\"top:-3.69em;\"><span class=\"pstrut\" style=\"height:3.008em;\"></span><span class=\"mord\"><span class=\"mord mathnormal\">n</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span><span class=\"mrel\">=</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span><span class=\"mord\">0</span></span></span><span style=\"top:-2.25em;\"><span class=\"pstrut\" style=\"height:3.008em;\"></span><span class=\"mord\"><span class=\"mord mathnormal\">n</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span><span class=\"mrel\">&gt;</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span><span class=\"mord\">0</span></span></span></span><span class=\"vlist-s\">​</span></span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:1.19em;\"><span></span></span></span></span></span></span></span><span class=\"mclose nulldelimiter\"></span></span></span></span></span></span></div>\n<p>Có thể biểu diễn bằng ngôn ngữ C:</p>\n<pre><code class=\"language-c\">unsigned long long factorial(unsigned int n) {\n    if n==0 {\n        return 1;\n    }\n\n    return n * factorial(n - 1);\n}</code></pre>\n<p>Đây là một hàm đệ quy trực tiếp vì <code>factorial</code> gọi lại chính <code>factorial</code>.</p>\n<p>Với <code>n = 4</code>, quá trình tính toán về mặt logic như sau:</p>\n<pre><code class=\"language-text\">factorial(4)\n  4 * factorial(3)\n        3 * factorial(2)\n              2 * factorial(1)\n                    1 * factorial(0)\n                          1</code></pre>\n<p>Khi đến điều kiện dừng, các lời gọi lần lượt hoàn thành theo chiều ngược lại:</p>\n<pre><code class=\"language-text\">factorial(0) = 1\nfactorial(1) = 1 * 1 = 1\nfactorial(2) = 2 * 1 = 2\nfactorial(3) = 3 * 2 = 6\nfactorial(4) = 4 * 6 = 24</code></pre>\n<p>Ví dụ này thể hiện đặc trưng của đệ quy thông thường: sau khi lời gọi đệ quy trả về, hàm gọi vẫn cần thực hiện thêm một phép toán.</p>\n<h3>1.2. Khung ngăn xếp (Stack Frame)</h3>\n<p>Khi một chương trình thực hiện lời gọi hàm, hệ thống thực thi thường cần duy trì thông tin phục vụ việc chuyển quyền điều khiển và quay trở lại hàm gọi.</p>\n<p>Những thông tin này có thể bao gồm:</p>\n<ul>\n<li>Địa chỉ trả về (Return Address).</li>\n<li>Các biến cục bộ cần được lưu trong bộ nhớ.</li>\n<li>Giá trị thanh ghi cần bảo toàn.</li>\n<li>Tham số không được truyền hoàn toàn qua thanh ghi.</li>\n<li>Vùng nhớ tạm phục vụ tính toán.</li>\n<li>Dữ liệu phục vụ cơ chế gỡ lỗi hoặc xử lý ngoại lệ.</li>\n</ul>\n<p>Tập hợp vùng nhớ và trạng thái phục vụ một lần thực thi hàm thường được gọi là khung ngăn xếp.</p>\n<p>Cấu trúc cụ thể phụ thuộc vào kiến trúc CPU, quy ước gọi hàm, trình biên dịch và mức tối ưu.</p>\n<p>Không phải mọi lời gọi hàm đều nhất thiết tạo ra một khung ngăn xếp riêng trong bộ nhớ. Tuy nhiên, nếu không được tối ưu, lời gọi đệ quy thường khiến nhiều trạng thái thực thi phải được duy trì đồng thời.</p>\n<p>Ví dụ minh họa:</p>\n<pre><code class=\"language-text\">Ngăn xếp khi factorial(4) gọi xuống factorial(0)\n\n┌─────────────────────────┐\n│ factorial(0)            │\n├─────────────────────────┤\n│ factorial(1)            │\n├─────────────────────────┤\n│ factorial(2)            │\n├─────────────────────────┤\n│ factorial(3)            │\n├─────────────────────────┤\n│ factorial(4)            │\n├─────────────────────────┤\n│ Hàm gọi factorial(4)    │\n└─────────────────────────┘</code></pre>\n<p>Đây là sơ đồ logic, không phải cách bố trí byte thực tế của một ABI cụ thể.</p>\n<p>Khi độ sâu đệ quy tăng, số lượng trạng thái cần duy trì cũng có thể tăng theo.</p>\n<p>Nếu mỗi lần gọi cần một lượng bộ nhớ ngăn xếp nhất định, tổng mức sử dụng có thể xấp xỉ:</p>\n<div class=\"math-display\" data-formula=\"S(n) = S_0 + n \\times F\"><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.05764em;\">S</span><span class=\"mopen\">(</span><span class=\"mord mathnormal\">n</span><span class=\"mclose\">)</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span><span class=\"mrel\">=</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span></span><span class=\"base\"><span class=\"strut\" style=\"height:0.8333em;vertical-align:-0.15em;\"></span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right:0.05764em;\">S</span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:0.3011em;\"><span style=\"top:-2.55em;margin-left:-0.0576em;margin-right:0.05em;\"><span class=\"pstrut\" style=\"height:2.7em;\"></span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">0</span></span></span></span><span class=\"vlist-s\">​</span></span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:0.15em;\"><span></span></span></span></span></span></span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span><span class=\"mbin\">+</span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span></span><span class=\"base\"><span class=\"strut\" style=\"height:0.6667em;vertical-align:-0.0833em;\"></span><span class=\"mord mathnormal\">n</span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span><span class=\"mbin\">×</span><span class=\"mspace\" style=\"margin-right:0.2222em;\"></span></span><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.13889em;\">F</span></span></span></span></span></div>\n<p>Trong đó:</p>\n<ul>\n<li><span class=\"math-inline\" data-formula=\"S(n)\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.05764em;\">S</span><span class=\"mopen\">(</span><span class=\"mord mathnormal\">n</span><span class=\"mclose\">)</span></span></span></span></span>: tổng dung lượng ngăn xếp liên quan đến chuỗi lời gọi.</li>\n<li><span class=\"math-inline\" data-formula=\"S_0\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.8333em;vertical-align:-0.15em;\"></span><span class=\"mord\"><span class=\"mord mathnormal\" style=\"margin-right:0.05764em;\">S</span><span class=\"msupsub\"><span class=\"vlist-t vlist-t2\"><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:0.3011em;\"><span style=\"top:-2.55em;margin-left:-0.0576em;margin-right:0.05em;\"><span class=\"pstrut\" style=\"height:2.7em;\"></span><span class=\"sizing reset-size6 size3 mtight\"><span class=\"mord mtight\">0</span></span></span></span><span class=\"vlist-s\">​</span></span><span class=\"vlist-r\"><span class=\"vlist\" style=\"height:0.15em;\"><span></span></span></span></span></span></span></span></span></span></span>: dung lượng ban đầu.</li>\n<li><span class=\"math-inline\" data-formula=\"n\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.4306em;\"></span><span class=\"mord mathnormal\">n</span></span></span></span></span>: số lần gọi đệ quy đang hoạt động.</li>\n<li><span class=\"math-inline\" data-formula=\"F\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.13889em;\">F</span></span></span></span></span>: dung lượng trung bình cần duy trì cho mỗi lần gọi.</li>\n</ul>\n<p>Đây là mô hình đơn giản hóa, phù hợp với trường hợp các khung có kích thước gần như cố định và chưa được tối ưu.</p>\n<h2>2. Đệ quy đuôi là gì?</h2>\n<h3>2.1. Khái niệm vị trí đuôi</h3>\n<p>Vị trí đuôi (Tail Position) là vị trí trong quá trình đánh giá biểu thức mà kết quả của biểu thức đó được sử dụng trực tiếp làm kết quả của hàm hiện tại, không còn phép tính tiếp theo phải thực hiện sau khi biểu thức kết thúc.</p>\n<p>Một lời gọi hàm ở vị trí đuôi được gọi là lời gọi đuôi (Tail Call).</p>\n<p>Ví dụ:</p>\n<pre><code class=\"language-c\">int f(int x) {\n    return gx;\n}</code></pre>\n<p>Ở đây, lời gọi <code>g<span class=\"math-inline\" data-formula=\"x\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.4306em;\"></span><span class=\"mord mathnormal\">x</span></span></span></span></span></code> nằm tại vị trí đuôi vì kết quả của <code>g</code> được trả về trực tiếp.</p>\n<p>Ngược lại:</p>\n<pre><code class=\"language-c\">int f(int x) {\n    return gx + 1;\n}</code></pre>\n<p>Lời gọi <code>g<span class=\"math-inline\" data-formula=\"x\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.4306em;\"></span><span class=\"mord mathnormal\">x</span></span></span></span></span></code> không nằm tại vị trí đuôi vì sau khi <code>g</code> trả về, hàm <code>f</code> vẫn phải thực hiện phép cộng với <code>1</code>.</p>\n<p><strong>Điểm quyết định không phải là lời gọi hàm có xuất hiện ở dòng cuối hay không, mà là còn công việc nào phải thực hiện sau khi lời gọi kết thúc hay không.</strong></p>\n<h3>2.2. Đệ quy đuôi</h3>\n<p>Đệ quy đuôi (Tail Recursion) là trường hợp một hàm tự gọi lại chính nó và lời gọi đó nằm tại vị trí đuôi.</p>\n<p>Có thể viết lại hàm tính giai thừa bằng cách sử dụng biến tích lũy <span class=\"math-inline\" data-formula=\"Accumulator\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6944em;\"></span><span class=\"mord mathnormal\">A</span><span class=\"mord mathnormal\">cc</span><span class=\"mord mathnormal\">u</span><span class=\"mord mathnormal\">m</span><span class=\"mord mathnormal\">u</span><span class=\"mord mathnormal\" style=\"margin-right:0.01968em;\">l</span><span class=\"mord mathnormal\">a</span><span class=\"mord mathnormal\">t</span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">or</span></span></span></span></span>:</p>\n<pre><code class=\"language-c\">unsigned long long factorial_acc(\n    unsigned int n,\n    unsigned long long acc\n) {\n    if n==0 {\n        return acc;\n    }\n\n    return factorial_acc(n - 1, acc * n);\n}\n\nunsigned long long factorial(unsigned int n) {\n    return factorial_acc(n, 1);\n}</code></pre>\n<p>Khi gọi <code>factorial(4)</code>, các trạng thái logic thay đổi như sau:</p>\n<p>| Lần gọi | n | acc | |---|---:|---:| | 1 | 4 | 1 | | 2 | 3 | 4 | | 3 | 2 | 12 | | 4 | 1 | 24 | | 5 | 0 | 24 |</p>\n<p>Tại mỗi bước, kết quả trung gian đã được tích lũy trong tham số <code>acc</code>.</p>\n<p>Không cần giữ lại phép nhân để thực hiện sau khi lời gọi đệ quy trả về.</p>\n<p>Lời gọi:</p>\n<pre><code class=\"language-c\">return factorial_acc(n - 1, acc * n);</code></pre>\n<p>nằm tại vị trí đuôi.</p>\n<p>Vì vậy, hàm có cấu trúc phù hợp với tối ưu hóa đệ quy đuôi.</p>\n<p>Ví dụ trên dùng số nguyên không dấu 64 bit theo cách biểu diễn thông thường của <code>unsigned long long</code>; kết quả chỉ còn chính xác trong phạm vi kiểu dữ liệu. Với hệ thống mà kiểu này có 64 bit, <code>20!</code> còn biểu diễn được, còn <code>21!</code> vượt phạm vi.</p>\n<h3>2.3. Đệ quy đuôi và lời gọi đuôi không đồng nhất</h3>\n<p>Lời gọi đuôi không bắt buộc phải là lời gọi đệ quy.</p>\n<p>Ví dụ:</p>\n<pre><code class=\"language-c\">int process(int x) {\n    return calculatex;\n}</code></pre>\n<p><code>process</code> gọi <code>calculate</code> ở vị trí đuôi, nhưng đây không phải đệ quy.</p>\n<p>Trong khi đó:</p>\n<pre><code class=\"language-c\">int countdown(int n) {\n    if n==0 {\n        return 0;\n    }\n\n    return countdown(n - 1);\n}</code></pre>\n<p>là đệ quy đuôi.</p>\n<p>Do đó, cần sử dụng thuật ngữ chính xác:</p>\n<p>| Thuật ngữ | Ý nghĩa | |---|---| | Lời gọi đuôi (Tail Call) | Lời gọi hàm ở vị trí đuôi | | Đệ quy đuôi (Tail Recursion) | Hàm tự gọi lại tại vị trí đuôi | | Tối ưu hóa lời gọi đuôi <span class=\"math-inline\" data-formula=\"TCO\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">TCO</span></span></span></span></span> | Tối ưu quá trình thực hiện lời gọi đuôi | | Loại bỏ đệ quy đuôi <span class=\"math-inline\" data-formula=\"TRE\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.05764em;\">TRE</span></span></span></span></span> | Chuyển hoặc tối ưu chuỗi tự gọi đệ quy đuôi, thường thành vòng lặp |</p>\n<h2>3. Tối ưu hóa lời gọi đuôi là gì?</h2>\n<h3>3.1. Nguyên lý</h3>\n<p>Tối ưu hóa lời gọi đuôi là kỹ thuật cho phép trình biên dịch thực hiện một lời gọi hàm ở vị trí đuôi mà không cần tiếp tục giữ trạng thái của hàm gọi như trong một chuỗi lời gọi thông thường.</p>\n<p>Khi hàm gọi không còn công việc nào phải thực hiện sau lời gọi đuôi, trong những điều kiện thích hợp, trình biên dịch có thể kết thúc hoặc tái sử dụng trạng thái thực thi hiện tại trước khi chuyển quyền điều khiển sang hàm được gọi.</p>\n<p>Ví dụ:</p>\n<pre><code class=\"language-c\">int f(int x) {\n    return gx;\n}</code></pre>\n<p>Trong cách thực hiện thông thường, có thể hình dung:</p>\n<pre><code class=\"language-text\">f gọi g\ng thực hiện\ng trả về f\nf trả về hàm trước đó</code></pre>\n<p>Sau khi áp dụng tối ưu hóa lời gọi đuôi, quá trình có thể được tổ chức thành:</p>\n<pre><code class=\"language-text\">f chuẩn bị tham số cho g\nf kết thúc hoặc giải phóng trạng thái không còn cần thiết\nchuyển trực tiếp sang g\ng trả về hàm đã gọi f</code></pre>\n<p>Như vậy, lời gọi <code>g</code> không nhất thiết cần một tầng ngăn xếp mới nằm phía trên khung thực thi còn hoạt động của <code>f</code>.</p>\n<h3>3.2. So sánh mức sử dụng ngăn xếp</h3>\n<p><strong>Không tối ưu:</strong></p>\n<pre><code class=\"language-text\">┌───────────────────┐\n│ factorial_acc(0)  │\n├───────────────────┤\n│ factorial_acc(1)  │\n├───────────────────┤\n│ factorial_acc(2)  │\n├───────────────────┤\n│ factorial_acc(3)  │\n├───────────────────┤\n│ factorial_acc(4)  │\n└───────────────────┘</code></pre>\n<p><strong>Sau khi loại bỏ đệ quy đuôi:</strong></p>\n<pre><code class=\"language-text\">┌──────────────────────────┐\n│ Một trạng thái thực thi  │\n│ factorial_acc            │\n│                          │\n│ n và acc được cập nhật   │\n│ qua các vòng lặp         │\n└──────────────────────────┘</code></pre>\n<p>Đối với kiểu tối ưu chuyển đệ quy thành vòng lặp và không sử dụng bộ nhớ phụ tăng theo độ sâu, dung lượng ngăn xếp của quá trình lặp có thể duy trì gần như không đổi.</p>\n<p>Đây là lợi ích quan trọng nhất của kỹ thuật này.</p>\n<h3>3.3. Độ phức tạp bộ nhớ</h3>\n<p>Đối với hàm đệ quy có độ sâu tỷ lệ với <span class=\"math-inline\" data-formula=\"n\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.4306em;\"></span><span class=\"mord mathnormal\">n</span></span></span></span></span>:</p>\n<ul>\n<li>Nếu mỗi lần gọi phải duy trì một khung riêng, mức sử dụng ngăn xếp thường là <span class=\"math-inline\" data-formula=\"O(n)\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">O</span><span class=\"mopen\">(</span><span class=\"mord mathnormal\">n</span><span class=\"mclose\">)</span></span></span></span></span>.</li>\n<li>Nếu đệ quy đuôi được loại bỏ thành vòng lặp với trạng thái có kích thước cố định, mức sử dụng ngăn xếp có thể là <span class=\"math-inline\" data-formula=\"O(1)\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">O</span><span class=\"mopen\">(</span><span class=\"mord\">1</span><span class=\"mclose\">)</span></span></span></span></span>.</li>\n</ul>\n<p>Tuy nhiên, <span class=\"math-inline\" data-formula=\"O(1)\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">O</span><span class=\"mopen\">(</span><span class=\"mord\">1</span><span class=\"mclose\">)</span></span></span></span></span> chỉ mô tả bộ nhớ ngăn xếp phục vụ cơ chế lặp trong những giả thiết nêu trên, không có nghĩa tổng bộ nhớ của mọi thuật toán đệ quy đuôi đều là hằng số.</p>\n<p>Dữ liệu được cấp phát trên heap, cấu trúc tích lũy hoặc các đối tượng trung gian vẫn có thể sử dụng bộ nhớ tăng theo kích thước đầu vào.</p>\n<h2>4. Cơ chế loại bỏ đệ quy đuôi</h2>\n<h3>4.1. Chuyển lời gọi đệ quy thành vòng lặp</h3>\n<p>Một trong những cách triển khai phổ biến của TRE là biến lời gọi tự đệ quy thành bước nhảy trở lại đầu hàm hoặc một khối lặp tương đương.</p>\n<p>Xét hàm:</p>\n<pre><code class=\"language-c\">unsigned int sum_tail(\n    unsigned int n,\n    unsigned int acc\n) {\n    if n==0 {\n        return acc;\n    }\n\n    return sum_tail(n - 1, acc + n);\n}</code></pre>\n<p>Về mặt logic, có thể chuyển đổi thành:</p>\n<pre><code class=\"language-c\">unsigned int sum_loop(\n    unsigned int n,\n    unsigned int acc\n) {\n    while n!=0 {\n        acc += n;\n        n -= 1;\n    }\n\n    return acc;\n}</code></pre>\n<p>Trong phiên bản thứ hai, không còn lời gọi tự đệ quy.</p>\n<p>Các giá trị trạng thái được cập nhật trực tiếp trong vòng lặp.</p>\n<p>Bằng cách này, trình biên dịch không cần tạo thêm một trạng thái gọi hàm cho mỗi lần lặp.</p>\n<h3>4.2. Quá trình biến đổi ở mức biểu diễn trung gian</h3>\n<p>Trong trình biên dịch, mã nguồn thường được chuyển thành biểu diễn trung gian (Intermediate Representation – IR) trước khi sinh mã máy.</p>\n<p>Hàm đệ quy đuôi có thể được biểu diễn bằng một khối chứa lời gọi tự đệ quy, sau đó là lệnh trả về.</p>\n<p>Quá trình tối ưu có thể thay lời gọi bằng việc cập nhật trạng thái và chuyển quyền điều khiển về khối đầu hàm.</p>\n<p>Tài liệu LLVM mô tả phép tối ưu <code>tailcallelim</code> như sau:</p>\n<blockquote><p>This file transforms calls of the current function (self recursion) followed by a return instruction with a branch to the entry of the function, creating a loop.</p></blockquote>\n<p><em>(Dịch nghĩa: Phép biến đổi này thay những lời gọi tự đệ quy của hàm hiện tại, theo sau bởi lệnh trả về, bằng bước nhảy đến điểm bắt đầu của hàm, qua đó tạo thành một vòng lặp.)</em></p>\n<p>Nguồn: LLVM, <em>LLVM's Analysis and Transform Passes</em>, mục <code>tailcallelim</code>.<sup class=\"footnote-ref\" id=\"fnref-1\"><a href=\"#fn-1\" role=\"doc-noteref\" data-footnote-ref=\"\">[1]</a></sup></p>\n<p>Ngoài trường hợp cơ bản, LLVM còn mô tả các khả năng như xử lý một số lệnh đơn giản nằm giữa lời gọi và lệnh trả về, hoặc sử dụng biến tích lũy trong những trường hợp phép toán cho phép chuyển đổi hợp lệ.</p>\n<p>Điều đó cho thấy tối ưu hóa đệ quy đuôi không nhất thiết chỉ là việc thay trực tiếp một lệnh gọi hàm bằng một lệnh nhảy.</p>\n<h3>4.3. Ảnh hưởng đến mã máy x86-64</h3>\n<p>Trên kiến trúc x86-64, các lệnh thường gặp trong cơ chế gọi hàm bao gồm:</p>\n<ul>\n<li><code>call</code>: Gọi hàm, đồng thời lưu thông tin địa chỉ trả về theo cơ chế của kiến trúc.</li>\n<li><code>ret</code>: Trả quyền điều khiển về địa chỉ trả về.</li>\n<li><code>jmp</code>: Chuyển quyền điều khiển trực tiếp đến một địa chỉ khác.</li>\n</ul>\n<p>Xét đoạn mã minh họa:</p>\n<pre><code class=\"language-c\">extern int calculate(int x);\n\nint process(int x) {\n    return calculatex;\n}</code></pre>\n<p>Trong trường hợp phù hợp về ABI và các điều kiện tối ưu khác, trình biên dịch có thể sinh mã tương tự:</p>\n<pre><code class=\"language-asm\">process:\n    jmp calculate</code></pre>\n<p>Thay vì:</p>\n<pre><code class=\"language-asm\">process:\n    call calculate\n    ret</code></pre>\n<p>Sơ đồ này minh họa sự khác nhau về luồng điều khiển, không phải kết quả biên dịch được bảo đảm cho mọi trình biên dịch và mọi nền tảng.</p>\n<p>Trong cách thực hiện dùng <code>jmp</code>, hàm <code>calculate</code> có thể trả kết quả trực tiếp về nơi đã gọi <code>process</code>, với điều kiện trạng thái máy đã được chuẩn bị phù hợp.</p>\n<p>Trên thực tế, trình biên dịch có thể cần giải phóng vùng nhớ ngăn xếp, khôi phục thanh ghi hoặc sắp xếp lại tham số trước khi thực hiện bước nhảy.</p>\n<h3>4.4. Ảnh hưởng đến mã máy ARM64</h3>\n<p>Trên kiến trúc AArch64, những lệnh thường gặp gồm:</p>\n<p>| Lệnh | Chức năng | |---|---| | <code>BL</code> | Gọi hàm và ghi địa chỉ trả về vào thanh ghi liên kết | | <code>B</code> | Nhảy trực tiếp mà không cập nhật thanh ghi liên kết | | <code>RET</code> | Trả quyền điều khiển theo thanh ghi địa chỉ trả về |</p>\n<p>Thông thường, thanh ghi <code>X30</code> được sử dụng làm thanh ghi liên kết (Link Register).</p>\n<p>Với một lời gọi đuôi hợp lệ, trình biên dịch có thể thực hiện bước nhảy thay cho cơ chế gọi hàm thông thường.</p>\n<p>Ví dụ mã máy minh họa:</p>\n<pre><code class=\"language-asm\">process:\n    b calculate</code></pre>\n<p>Thay cho dạng:</p>\n<pre><code class=\"language-asm\">process:\n    bl calculate\n    ret</code></pre>\n<p>Trong trường hợp sử dụng <code>B</code>, trình biên dịch phải bảo đảm địa chỉ trả về ban đầu vẫn còn hợp lệ, đồng thời tuân thủ quy ước gọi hàm của nền tảng.</p>\n<p>Cơ chế này có thể giúp tránh phát sinh thêm một tầng gọi hàm không cần thiết.</p>\n<h2>5. Điều kiện để áp dụng tối ưu hóa lời gọi đuôi</h2>\n<h3>5.1. Lời gọi phải thực sự ở vị trí đuôi</h3>\n<p>Điều kiện đầu tiên là hàm gọi không còn công việc phải thực hiện sau khi lời gọi kết thúc.</p>\n<p>Ví dụ có thể tối ưu:</p>\n<pre><code class=\"language-c\">int f(int x) {\n    return gx;\n}</code></pre>\n<p>Ví dụ không phải lời gọi đuôi:</p>\n<pre><code class=\"language-c\">int f(int x) {\n    return gx * 2;\n}</code></pre>\n<p>Trong ví dụ thứ hai, <code>f</code> vẫn phải thực hiện phép nhân.</p>\n<p>Tuy nhiên, trình biên dịch có thể thực hiện những phép biến đổi khác để loại bỏ đệ quy trong một số trường hợp. Vì vậy, việc lời gọi ban đầu không nằm tại vị trí đuôi không đồng nghĩa với việc không tồn tại bất kỳ phương án tối ưu nào.</p>\n<h3>5.2. Phải tuân thủ quy ước gọi hàm</h3>\n<p>Quy ước gọi hàm (Calling Convention) xác định cách truyền tham số, trả kết quả và bảo toàn trạng thái máy khi chuyển quyền điều khiển giữa các hàm.</p>\n<p>Các yêu cầu thường liên quan đến:</p>\n<ul>\n<li>Thanh ghi được dùng để truyền tham số.</li>\n<li>Thanh ghi phải được hàm gọi hoặc hàm được gọi bảo toàn.</li>\n<li>Cách truyền giá trị trả về.</li>\n<li>Vị trí của tham số truyền qua ngăn xếp.</li>\n<li>Yêu cầu căn chỉnh ngăn xếp.</li>\n<li>Cách xử lý đối số biến thiên.</li>\n<li>Cấu trúc dữ liệu trả về có kích thước lớn.</li>\n</ul>\n<p>Một lời gọi có thể ở vị trí đuôi về mặt ngữ nghĩa, nhưng việc thực hiện nó dưới dạng bước nhảy trực tiếp vẫn có thể không hợp lệ nếu những yêu cầu ABI chưa được đáp ứng.</p>\n<h3>5.3. Vòng đời của biến cục bộ</h3>\n<p>Trong một số trường hợp, hàm được gọi có thể tiếp tục truy cập dữ liệu thuộc khung ngăn xếp của hàm gọi.</p>\n<p>Ví dụ:</p>\n<pre><code class=\"language-c\">extern int use_pointer(const int *p);\n\nint fvoid {\n    int value = 10;\n    return use_pointer(&amp;value);\n}</code></pre>\n<p>Ở đây, <code>use_pointer</code> nhận địa chỉ của biến cục bộ <code>value</code>.</p>\n<p>Việc giải phóng khung ngăn xếp của <code>f</code> trước khi <code>use_pointer</code> kết thúc có thể khiến con trỏ không còn trỏ đến vùng nhớ hợp lệ.</p>\n<p>Do đó, trình biên dịch không thể tùy tiện áp dụng phép biến đổi hủy khung gọi hiện tại nếu điều đó làm thay đổi vòng đời dữ liệu.</p>\n<p>Đây là một ví dụ về giới hạn an toàn của tối ưu hóa lời gọi đuôi.</p>\n<h3>5.4. Trạng thái dọn dẹp và xử lý ngoại lệ</h3>\n<p>Một số ngôn ngữ và môi trường thực thi yêu cầu thực hiện công việc bổ sung khi thoát khỏi hàm.</p>\n<p>Ví dụ:</p>\n<ul>\n<li>Chạy hàm hủy đối tượng.</li>\n<li>Giải phóng tài nguyên theo phạm vi.</li>\n<li>Thực hiện khối <code>finally</code>.</li>\n<li>Cập nhật trạng thái xử lý ngoại lệ.</li>\n<li>Thực hiện các thao tác bảo vệ ngăn xếp.</li>\n</ul>\n<p>Nếu những thao tác này phải xảy ra sau khi lời gọi hàm kết thúc, lời gọi có thể không còn đủ điều kiện thực hiện như một tail call trực tiếp.</p>\n<p>Một trình biên dịch có thể xử lý bằng các phép biến đổi khác khi hợp lệ, nhưng tính đúng đắn ngữ nghĩa luôn phải được duy trì.</p>\n<h3>5.5. Giới hạn của nền tảng</h3>\n<p>Ngay cả khi mã nguồn có cấu trúc phù hợp, việc tối ưu vẫn có thể phụ thuộc vào:</p>\n<ul>\n<li>Kiến trúc CPU.</li>\n<li>ABI của hệ điều hành.</li>\n<li>Backend sinh mã.</li>\n<li>Mức tối ưu.</li>\n<li>Quy ước gọi hàm.</li>\n<li>Kiểu dữ liệu trả về.</li>\n<li>Các thuộc tính đặc biệt của hàm.</li>\n</ul>\n<p>Vì vậy, không thể khẳng định rằng mọi hàm đệ quy đuôi đều tự động được chuyển thành vòng lặp trong mọi trình biên dịch.</p>\n<h2>6. Tối ưu hóa đệ quy đuôi trong GCC và LLVM</h2>\n<h3>6.1. GCC</h3>\n<p>GCC cung cấp tùy chọn:</p>\n<pre><code class=\"language-bash\">-foptimize-sibling-calls</code></pre>\n<p>Tài liệu GCC mô tả:</p>\n<blockquote><p>Optimize sibling and tail recursive calls.</p></blockquote>\n<p><em>(Dịch nghĩa: Tối ưu hóa các lời gọi hàm ngang cấp và những lời gọi đệ quy đuôi.)</em></p>\n<p>Theo tài liệu GCC 14.3, tùy chọn này được bật tại các mức tối ưu <code>-O2</code>, <code>-O3</code> và <code>-Os</code>.<sup class=\"footnote-ref\" id=\"fnref-2\"><a href=\"#fn-2\" role=\"doc-noteref\" data-footnote-ref=\"\">[2]</a></sup></p>\n<p>Ví dụ:</p>\n<pre><code class=\"language-bash\">gcc -O2 -S example.c -o example.s</code></pre>\n<p>Lệnh trên yêu cầu GCC sinh mã hợp ngữ để có thể kiểm tra kết quả tối ưu.</p>\n<p>Việc bật tùy chọn không bảo đảm mọi lời gọi đuôi đều được tối ưu thành công. Quyết định cuối cùng còn phụ thuộc vào điều kiện hợp lệ của từng lời gọi và khả năng của backend.</p>\n<h3>6.2. LLVM</h3>\n<p>LLVM hỗ trợ nhiều cơ chế liên quan đến lời gọi đuôi.</p>\n<p>Trong LLVM IR, lời gọi có thể mang những dấu hiệu như:</p>\n<p>| Dấu hiệu | Ý nghĩa | |---|---| | <code>tail</code> | Đánh dấu một lời gọi là ứng viên cho tối ưu hóa đuôi | | <code>musttail</code> | Yêu cầu bảo đảm lời gọi đuôi theo các điều kiện được đặc tả | | <code>notail</code> | Ngăn bộ tối ưu gắn dấu hiệu tối ưu lời gọi đuôi |</p>\n<p>Ví dụ minh họa LLVM IR:</p>\n<pre><code class=\"language-llvm\">define i32 @f(i32 %x) {\nentry:\n  %result = tail call i32 @g(i32 %x)\n  ret i32 %result\n}\n\ndeclare i32 @gi32</code></pre>\n<p>Dấu hiệu <code>tail</code> không phải sự bảo đảm tuyệt đối rằng mã máy cuối cùng sẽ thực hiện lời gọi theo dạng tối ưu.</p>\n<p>Đối với <code>musttail</code>, LLVM đặt ra những điều kiện nghiêm ngặt hơn về vị trí lời gọi, kiểu hàm, quy ước gọi hàm và các thuộc tính ảnh hưởng ABI.</p>\n<p>Tài liệu ngôn ngữ LLVM quy định rằng <code>musttail</code> phải được tối ưu phù hợp để bảo đảm tính đúng đắn của chương trình; đặc biệt, chuỗi đệ quy thông qua các lời gọi <code>musttail</code> hợp lệ không được gây tăng trưởng ngăn xếp không giới hạn chỉ vì những lời gọi đó.<sup class=\"footnote-ref\" id=\"fnref-3\"><a href=\"#fn-3\" role=\"doc-noteref\" data-footnote-ref=\"\">[3]</a></sup></p>\n<h3>6.3. Đệ quy đuôi được bảo đảm và đệ quy đuôi có thể tối ưu</h3>\n<p>Cần xác định sự khác nhau giữa ba trường hợp:</p>\n<p><strong>Trường hợp thứ nhất:</strong> Mã nguồn có cấu trúc đệ quy đuôi, nhưng ngôn ngữ không yêu cầu trình biên dịch tối ưu.</p>\n<p><strong>Trường hợp thứ hai:</strong> Trình biên dịch nhận diện lời gọi đuôi và tối ưu khi điều kiện cho phép.</p>\n<p><strong>Trường hợp thứ ba:</strong> Ngôn ngữ hoặc cơ chế IR đặt ra yêu cầu bảo đảm lời gọi đuôi, trong phạm vi các điều kiện được quy định.</p>\n<p>Điều này đặc biệt quan trọng đối với những chương trình sử dụng đệ quy sâu như một cơ chế điều khiển chính.</p>\n<h3>6.4. Ngôn ngữ Scheme và đệ quy đuôi đúng nghĩa</h3>\n<p>Scheme là một ví dụ quan trọng vì đặc tả ngôn ngữ có yêu cầu rõ ràng về đệ quy đuôi đúng nghĩa (Proper Tail Recursion).</p>\n<p>Báo cáo R5RS nêu:</p>\n<blockquote><p>Implementations of Scheme are required to be properly tail-recursive.</p></blockquote>\n<p><em>(Dịch nghĩa: Các bản triển khai của ngôn ngữ Scheme bắt buộc phải hỗ trợ đệ quy đuôi đúng nghĩa.)</em></p>\n<p>Nguồn: <em>Revised⁵ Report on the Algorithmic Language Scheme</em>, mục 3.5.<sup class=\"footnote-ref\" id=\"fnref-4\"><a href=\"#fn-4\" role=\"doc-noteref\" data-footnote-ref=\"\">[4]</a></sup></p>\n<p>Trong Scheme, hỗ trợ đệ quy đuôi không chỉ là một lựa chọn cải thiện hiệu năng, mà là một phần trong yêu cầu về hành vi của bản triển khai.</p>\n<p>Đặc tả yêu cầu hỗ trợ số lượng không bị giới hạn trước của các lời gọi đuôi đang hoạt động, trong ý nghĩa kỹ thuật được định nghĩa bởi ngôn ngữ.</p>\n<p>Điều đó không có nghĩa chương trình có bộ nhớ vô hạn, mà là chuỗi lời gọi đuôi không được buộc phải tiêu thụ thêm không gian chỉ để duy trì những tầng tiếp diễn không cần thiết.</p>\n<h2>7. Tác động đến hiệu năng và bộ nhớ</h2>\n<h3>7.1. Bộ nhớ ngăn xếp</h3>\n<p>Tác động nổi bật nhất của tối ưu hóa lời gọi đuôi là hạn chế sự gia tăng bộ nhớ ngăn xếp.</p>\n<p>Khi chuyển một chuỗi tự đệ quy đuôi thành vòng lặp, chương trình có thể tránh việc duy trì nhiều khung gọi hàm đồng thời.</p>\n<p>Đây là lợi ích quan trọng đối với:</p>\n<ul>\n<li>Thuật toán xử lý chuỗi có độ dài lớn.</li>\n<li>Bộ thông dịch và máy ảo.</li>\n<li>Các thuật toán duyệt cấu trúc dữ liệu.</li>\n<li>Những ngôn ngữ lập trình hàm.</li>\n<li>Các hệ thống sử dụng hàm như đơn vị điều khiển thay cho vòng lặp.</li>\n</ul>\n<h3>7.2. Chi phí gọi hàm</h3>\n<p>Khi loại bỏ được lời gọi hàm thông thường, trình biên dịch có thể giảm một phần chi phí liên quan đến:</p>\n<ul>\n<li>Lưu và khôi phục địa chỉ trả về.</li>\n<li>Thiết lập hoặc tháo dỡ khung ngăn xếp.</li>\n<li>Bảo toàn một số thanh ghi.</li>\n<li>Chuyển quyền điều khiển qua nhiều tầng gọi.</li>\n</ul>\n<p>Tuy nhiên, mức cải thiện thực tế phụ thuộc vào kiến trúc CPU, mã máy được sinh và đặc điểm chương trình.</p>\n<p>Không phải mọi lời gọi đuôi được tối ưu đều nhanh hơn đáng kể so với lời gọi thông thường.</p>\n<h3>7.3. Độ phức tạp thời gian</h3>\n<p>Đối với ví dụ tính giai thừa, việc chuyển từ đệ quy thông thường sang đệ quy đuôi không làm thay đổi số phép nhân cần thực hiện.</p>\n<p>Độ phức tạp thời gian vẫn là:</p>\n<div class=\"math-display\" data-formula=\"T(n) = O(n)\"><span class=\"katex-display\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.13889em;\">T</span><span class=\"mopen\">(</span><span class=\"mord mathnormal\">n</span><span class=\"mclose\">)</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span><span class=\"mrel\">=</span><span class=\"mspace\" style=\"margin-right:0.2778em;\"></span></span><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">O</span><span class=\"mopen\">(</span><span class=\"mord mathnormal\">n</span><span class=\"mclose\">)</span></span></span></span></span></div>\n<p>Nếu được chuyển thành vòng lặp, độ phức tạp bộ nhớ ngăn xếp có thể giảm từ <span class=\"math-inline\" data-formula=\"O(n)\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">O</span><span class=\"mopen\">(</span><span class=\"mord mathnormal\">n</span><span class=\"mclose\">)</span></span></span></span></span> xuống <span class=\"math-inline\" data-formula=\"O(1)\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:1em;vertical-align:-0.25em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">O</span><span class=\"mopen\">(</span><span class=\"mord\">1</span><span class=\"mclose\">)</span></span></span></span></span>, trong điều kiện mỗi bước chỉ duy trì một lượng trạng thái cố định.</p>\n<p>Như vậy, tối ưu hóa lời gọi đuôi chủ yếu cải thiện cơ chế thực thi và mức sử dụng tài nguyên, chứ không nhất thiết thay đổi độ phức tạp thời gian của thuật toán.</p>\n<h2>8. Những giới hạn và vấn đề cần lưu ý</h2>\n<h3>8.1. Không phải mọi đệ quy đều là đệ quy đuôi</h3>\n<p>Ví dụ:</p>\n<pre><code class=\"language-c\">unsigned long long factorial(unsigned int n) {\n    if n==0 {\n        return 1;\n    }\n\n    return n * factorial(n - 1);\n}</code></pre>\n<p>Lời gọi đệ quy không nằm tại vị trí đuôi vì vẫn còn phép nhân sau khi nhận kết quả.</p>\n<p>Một trình biên dịch có thể nhận diện và biến đổi một số dạng đệ quy như thế này, nhưng không thể xem đó là thuộc tính mặc định của mọi trình biên dịch.</p>\n<h3>8.2. Đệ quy đuôi không đồng nghĩa với không bao giờ tràn ngăn xếp</h3>\n<p>Nếu một bản triển khai không thực hiện tối ưu hóa, một hàm đệ quy đuôi vẫn có thể tạo ra chuỗi lời gọi làm tăng mức sử dụng ngăn xếp.</p>\n<p>Ngoài ra, chương trình còn có thể sử dụng ngăn xếp cho những hoạt động khác.</p>\n<p>Vì vậy, cần xem xét cả hình thức mã nguồn lẫn bảo đảm của trình biên dịch và môi trường thực thi.</p>\n<h3>8.3. Tối ưu hóa có thể làm thay đổi cách quan sát khi gỡ lỗi</h3>\n<p>Khi lời gọi hàm được thay bằng bước nhảy hoặc vòng lặp, chuỗi lời gọi quan sát được trong trình gỡ lỗi có thể khác với cấu trúc hàm ban đầu.</p>\n<p>Một số khung gọi có thể không xuất hiện như khi biên dịch ở chế độ không tối ưu.</p>\n<p>Điều này có thể ảnh hưởng đến:</p>\n<ul>\n<li>Việc quan sát ngăn xếp lời gọi (Call Stack).</li>\n<li>Theo dõi thứ tự thực hiện hàm.</li>\n<li>Phân tích thông tin khung gọi.</li>\n<li>Đọc kết quả lấy mẫu hiệu năng.</li>\n</ul>\n<p>Các trình biên dịch và công cụ gỡ lỗi có thể sử dụng thông tin bổ sung để hỗ trợ việc quan sát mã đã tối ưu, nhưng không phải lúc nào cũng tái hiện được đầy đủ chuỗi lời gọi theo mã nguồn.</p>\n<h3>8.4. Tối ưu hóa lời gọi đuôi không thay thế mọi hình thức tối ưu khác</h3>\n<p>Các kỹ thuật như nội tuyến hàm <span class=\"math-inline\" data-formula=\"Inlining\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.8889em;vertical-align:-0.1944em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.07847em;\">I</span><span class=\"mord mathnormal\">n</span><span class=\"mord mathnormal\" style=\"margin-right:0.01968em;\">l</span><span class=\"mord mathnormal\">inin</span><span class=\"mord mathnormal\" style=\"margin-right:0.03588em;\">g</span></span></span></span></span>, lan truyền hằng số (Constant Propagation), loại bỏ mã chết (Dead Code Elimination) và tối ưu vòng lặp vẫn có thể tác động đến cùng một đoạn chương trình.</p>\n<p>Một hàm đệ quy có thể được biến đổi bởi nhiều phép tối ưu kết hợp.</p>\n<p>Do đó, khi phân tích mã máy, không nên mặc nhiên gán mọi trường hợp không còn lời gọi đệ quy cho một phép tối ưu duy nhất.</p>\n<h2>9. Kiểm chứng tối ưu hóa trong thực tế</h2>\n<h3>9.1. Chương trình thử nghiệm</h3>\n<p>Có thể sử dụng đoạn mã sau:</p>\n<pre><code class=\"language-c\">__attribute__((noinline))\nunsigned long long sum_tail(\n    unsigned int n,\n    unsigned long long acc\n) {\n    if n==0 {\n        return acc;\n    }\n\n    return sum_tail(n - 1, acc + n);\n}\n\nint mainvoid {\n    return sum_tail(10, 0) != 55;\n}</code></pre>\n<p>Thuộc tính <code>noinline</code> trong GCC hoặc Clang được dùng để hạn chế việc hàm bị nội tuyến, giúp quan sát riêng mã của hàm rõ hơn.</p>\n<p>Tuy nhiên, thuộc tính này không cấm các tối ưu hóa khác, bao gồm việc loại bỏ đệ quy đuôi.</p>\n<h3>9.2. Biên dịch bằng GCC</h3>\n<pre><code class=\"language-bash\">gcc -O0 -S test.c -o test_O0.s\ngcc -O2 -S test.c -o test_O2.s</code></pre>\n<p>Sau đó, so sánh mã hợp ngữ của hàm <code>sum_tail</code>.</p>\n<p>Ở mức tối ưu thấp, mã thường giữ lại lời gọi tự đệ quy.</p>\n<p>Ở mức tối ưu cao, trình biên dịch có thể chuyển hàm thành vòng lặp và không còn lời gọi tự đệ quy.</p>\n<p>Kết quả cụ thể phụ thuộc vào phiên bản GCC, kiến trúc đích và các tùy chọn biên dịch.</p>\n<h3>9.3. Biên dịch bằng Clang</h3>\n<pre><code class=\"language-bash\">clang -O0 -S test.c -o test_O0.s\nclang -O2 -S test.c -o test_O2.s</code></pre>\n<p>Có thể kiểm tra biểu diễn LLVM IR:</p>\n<pre><code class=\"language-bash\">clang -O2 -S -emit-llvm test.c -o test.ll</code></pre>\n<p>Khi đọc kết quả, cần tìm những dấu hiệu như:</p>\n<ul>\n<li>Khối lặp thay thế lời gọi đệ quy.</li>\n<li>Lời gọi đuôi được đánh dấu trong IR.</li>\n<li>Lệnh nhảy thay cho chuỗi gọi và trả về trong mã máy.</li>\n<li>Sự thay đổi trong việc thiết lập khung ngăn xếp.</li>\n</ul>\n<p>Đây là các dấu hiệu cần phân tích cùng nhau, thay vì chỉ dựa vào sự xuất hiện của một lệnh cụ thể.</p>\n<h2>10. Kết luận</h2>\n<p>Tối ưu hóa lời gọi đuôi là một kỹ thuật quan trọng trong thiết kế và triển khai trình biên dịch.</p>\n<p>Kỹ thuật này khai thác đặc điểm của những lời gọi hàm không còn công việc phải thực hiện sau khi kết thúc, từ đó cho phép loại bỏ việc duy trì những trạng thái gọi hàm không cần thiết.</p>\n<p>Trong trường hợp đệ quy đuôi, trình biên dịch có thể chuyển lời gọi tự đệ quy thành vòng lặp, giúp giảm mức sử dụng bộ nhớ ngăn xếp và tránh sự gia tăng số lượng khung gọi theo độ sâu đệ quy.</p>\n<p>Tuy nhiên, khả năng tối ưu phụ thuộc vào nhiều điều kiện, bao gồm cấu trúc chương trình, vòng đời dữ liệu, quy ước gọi hàm, ABI và khả năng của backend sinh mã.</p>\n<p>Sự khác nhau giữa lời gọi đuôi, đệ quy đuôi, tối ưu hóa lời gọi đuôi và loại bỏ đệ quy đuôi là cơ sở cần thiết để hiểu đúng cơ chế này.</p>\n<p>Đối với nghiên cứu trình biên dịch, kỹ thuật tối ưu hóa lời gọi đuôi cũng là ví dụ tiêu biểu cho mối quan hệ giữa ngữ nghĩa ngôn ngữ lập trình, biểu diễn trung gian, phân tích luồng điều khiển và quá trình sinh mã máy.</p>\n<hr>\n<h2>Phụ lục A. Thuật ngữ kỹ thuật</h2>\n<p>| Thuật ngữ tiếng Việt | Thuật ngữ tiếng Anh | Ý nghĩa | |---|---|---| | Đệ quy | Recursion | Hàm trực tiếp hoặc gián tiếp gọi lại chính nó | | Vị trí đuôi | Tail Position | Vị trí mà kết quả được dùng trực tiếp làm kết quả của hàm | | Lời gọi đuôi | Tail Call | Lời gọi hàm ở vị trí đuôi | | Đệ quy đuôi | Tail Recursion | Lời gọi tự đệ quy ở vị trí đuôi | | Tối ưu hóa lời gọi đuôi | Tail Call Optimization | Tối ưu lời gọi đuôi để tránh duy trì khung gọi không cần thiết | | Loại bỏ đệ quy đuôi | Tail Recursion Elimination | Biến đổi hoặc loại bỏ lời gọi tự đệ quy đuôi | | Khung ngăn xếp | Stack Frame | Trạng thái và vùng nhớ phục vụ một lần thực thi hàm | | Quy ước gọi hàm | Calling Convention | Quy tắc truyền tham số, trả kết quả và bảo toàn trạng thái máy | | Giao diện nhị phân ứng dụng | Application Binary Interface | Quy định tương tác nhị phân giữa các thành phần chương trình | | Biểu diễn trung gian | Intermediate Representation | Dạng biểu diễn chương trình phục vụ phân tích và tối ưu | | Biến tích lũy | Accumulator | Giá trị duy trì kết quả trung gian qua các bước tính toán | | Địa chỉ trả về | Return Address | Vị trí chương trình tiếp tục sau khi lời gọi hoàn thành | | Nội tuyến hàm | Inlining | Thay lời gọi hàm bằng nội dung được biến đổi từ thân hàm |</p>\n<h2>Phụ lục B. Tài liệu tham khảo và nghiên cứu mở rộng</h2>\n<h3>B.1. Đặc tả và tài liệu trình biên dịch</h3>\n<p><strong>[1] LLVM Project, <em>LLVM's Analysis and Transform Passes</em>.</strong></p>\n<p>Mục <code>tailcallelim</code> giải thích phép biến đổi lời gọi tự đệ quy thành vòng lặp và một số mở rộng của thuật toán.</p>\n<p>https://llvm.org/docs/Passes.html</p>\n<p><strong>[2] GNU Compiler Collection, <em>Optimize Options</em>.</strong></p>\n<p>Tài liệu về tùy chọn <code>-foptimize-sibling-calls</code>, mức tối ưu và những phép tối ưu liên quan.</p>\n<p>https://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html</p>\n<p><strong>[3] LLVM Project, <em>LLVM Language Reference Manual</em>.</strong></p>\n<p>Đặc tả ngôn ngữ LLVM IR, bao gồm dấu hiệu <code>tail</code>, <code>musttail</code>, <code>notail</code>, các quy ước gọi hàm và điều kiện tối ưu lời gọi đuôi.</p>\n<p>https://llvm.org/docs/LangRef.html</p>\n<p><strong>[4] Clang Project, <em>Attribute Reference</em>.</strong></p>\n<p>Tài liệu về thuộc tính <code>musttail</code>, những điều kiện áp dụng và bảo đảm của trình biên dịch.</p>\n<p>https://clang.llvm.org/docs/AttributeReference.html</p>\n<h3>B.2. Ngôn ngữ lập trình và ngữ nghĩa lời gọi đuôi</h3>\n<p><strong>[5] Richard Kelsey, William Clinger và Jonathan Rees (biên tập), <em>Revised⁵ Report on the Algorithmic Language Scheme</em>, 1998.</strong></p>\n<p>Mục 3.5, <em>Proper Tail Recursion</em>, trình bày yêu cầu chính thức về đệ quy đuôi đúng nghĩa trong Scheme.</p>\n<p>https://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html</p>\n<p><strong>[6] Guy L. Steele Jr. và Gerald Jay Sussman, <em>Lambda: The Ultimate Imperative</em>, MIT Artificial Intelligence Laboratory, AI Memo 353, 1976.</strong></p>\n<p>Một công trình quan trọng trong lịch sử nghiên cứu ngôn ngữ Scheme, cơ chế tiếp diễn và các phương pháp thực thi lời gọi hàm.</p>\n<h3>B.3. Đặc tả kiến trúc và quy ước gọi hàm</h3>\n<p><strong>[7] Arm Limited, <em>Procedure Call Standard for the Arm 64-bit Architecture <span class=\"math-inline\" data-formula=\"AAPCS64\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\">AA</span><span class=\"mord mathnormal\" style=\"margin-right:0.05764em;\">PCS</span><span class=\"mord\">64</span></span></span></span></span></em>.</strong></p>\n<p>Đặc tả quy ước gọi hàm trên AArch64, bao gồm sử dụng thanh ghi, truyền tham số và tổ chức trạng thái khi gọi hàm.</p>\n<p>https://github.com/ARM-software/abi-aa/blob/main/aapcs64/aapcs64.rst</p>\n<p><strong>[8] System V Application Binary Interface, AMD64 Architecture Processor Supplement.</strong></p>\n<p>Đặc tả ABI dành cho x86-64 theo môi trường System V, bao gồm quy ước gọi hàm, thanh ghi và bố trí ngăn xếp.</p>\n<p>https://gitlab.com/x86-psABIs/x86-64-ABI</p>\n<p><strong>[9] Intel, <em>Intel 64 and IA-32 Architectures Software Developer's Manuals</em>.</strong></p>\n<p>Tài liệu chính thức về tập lệnh x86, bao gồm <code>CALL</code>, <code>RET</code> và <code>JMP</code>.</p>\n<p>https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html</p>\n<h3>B.4. Các chủ đề nghiên cứu tiếp theo</h3>\n<ul>\n<li>Khung ngăn xếp (Stack Frame): Cấu trúc và vòng đời.</li>\n<li>Tràn ngăn xếp (Stack Overflow): Nguyên nhân và cơ chế.</li>\n<li>Giao diện nhị phân ứng dụng <span class=\"math-inline\" data-formula=\"ABI\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\">A</span><span class=\"mord mathnormal\" style=\"margin-right:0.05017em;\">B</span><span class=\"mord mathnormal\" style=\"margin-right:0.07847em;\">I</span></span></span></span></span>: Các quy ước gọi hàm.</li>\n<li>Biểu diễn trung gian <span class=\"math-inline\" data-formula=\"IR\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6833em;\"></span><span class=\"mord mathnormal\" style=\"margin-right:0.07847em;\">I</span><span class=\"mord mathnormal\" style=\"margin-right:0.00773em;\">R</span></span></span></span></span>: Phân tích và tối ưu luồng điều khiển.</li>\n<li>Bộ liên kết <span class=\"math-inline\" data-formula=\"Linker\"><span class=\"katex\"><span class=\"katex-html\" aria-hidden=\"true\"><span class=\"base\"><span class=\"strut\" style=\"height:0.6944em;\"></span><span class=\"mord mathnormal\">L</span><span class=\"mord mathnormal\" style=\"margin-right:0.03148em;\">ink</span><span class=\"mord mathnormal\" style=\"margin-right:0.02778em;\">er</span></span></span></span></span>: Vai trò trong quá trình biên dịch và thực thi chương trình.</li>\n</ul>\n<hr>\n<h2>Chú thích</h2>\n<div class=\"footnotes\" role=\"doc-endnotes\">\n<ol class=\"footnotes-list\">\n<li id=\"fn-1\" class=\"footnote-item\" role=\"doc-endnote\"><span class=\"footnote-text\">LLVM Project, <em>LLVM's Analysis and Transform Passes</em>, mục <code>tailcallelim</code>. https://llvm.org/docs/Passes.html</span> <span class=\"footnote-backrefs\"><a href=\"#fnref-1\" class=\"footnote-backref\" role=\"doc-backlink\" title=\"Quay lại nội dung\" aria-label=\"Quay lại nội dung\">↩</a></span></li>\n<li id=\"fn-2\" class=\"footnote-item\" role=\"doc-endnote\"><span class=\"footnote-text\">GNU Compiler Collection, <em>Optimize Options</em>, tài liệu GCC 14.3, mục <code>-foptimize-sibling-calls</code>. https://gcc.gnu.org/onlinedocs/gcc-14.3.0/gcc/Optimize-Options.html</span> <span class=\"footnote-backrefs\"><a href=\"#fnref-2\" class=\"footnote-backref\" role=\"doc-backlink\" title=\"Quay lại nội dung\" aria-label=\"Quay lại nội dung\">↩</a></span></li>\n<li id=\"fn-3\" class=\"footnote-item\" role=\"doc-endnote\"><span class=\"footnote-text\">LLVM Project, <em>LLVM Language Reference Manual</em>, mục lệnh <code>call</code>, dấu hiệu <code>tail</code> và <code>musttail</code>. https://llvm.org/docs/LangRef.html</span> <span class=\"footnote-backrefs\"><a href=\"#fnref-3\" class=\"footnote-backref\" role=\"doc-backlink\" title=\"Quay lại nội dung\" aria-label=\"Quay lại nội dung\">↩</a></span></li>\n<li id=\"fn-4\" class=\"footnote-item\" role=\"doc-endnote\"><span class=\"footnote-text\"><em>Revised⁵ Report on the Algorithmic Language Scheme</em>, mục 3.5, <em>Proper Tail Recursion</em>. https://www.gnu.org/software/guile/manual/r5rs/Proper-tail-recursion.html</span> <span class=\"footnote-backrefs\"><a href=\"#fnref-4\" class=\"footnote-backref\" role=\"doc-backlink\" title=\"Quay lại nội dung\" aria-label=\"Quay lại nội dung\">↩</a></span></li>\n</ol>\n</div>","tags":[],"author":"virgorilabs_112522","publishedAt":"2026-10-16T12:34:05.563Z","updatedAt":"2026-10-16T14:36:36.241Z","published_at":"2026-10-16T12:34:05.563Z","updated_at":"2026-10-16T14:36:36.241Z","view_count":1,"canonical":"https://wiki.quizzman.com/wiki/toi-uu-hoa-de-quy-duoi-tail-call-optimization-la-gi","url":"https://wiki.quizzman.com/wiki/toi-uu-hoa-de-quy-duoi-tail-call-optimization-la-gi","markdownUrl":"https://wiki.quizzman.com/api/articles/toi-uu-hoa-de-quy-duoi-tail-call-optimization-la-gi.md","apiUrl":"https://wiki.quizzman.com/api/articles/toi-uu-hoa-de-quy-duoi-tail-call-optimization-la-gi"}