Tối ưu hóa cuộc gọi đuôi bên cạnh đệ quy đuôi?

Question

Có bất kỳ sự tối ưu hóa cuộc gọi đuôi nào ngoài việc đệ quy đuôi không? Tôi đã cố gắng để tìm hoặc nghĩ về một trong đó không liên quan đến đệ quy, nhưng không thành công. Có thể không? Bất kỳ ví dụ nào?

Answer 1

int bar(int x); 
int foo(int x) { return bar(x); } 

foo chỉ có thể nhảy đến bar ai trả cho người gọi trực tiếp; không có đệ quy nào là cần thiết ở bất cứ đâu.

Answer 2

Chắc chắn, "tối ưu hóa cuộc gọi đuôi" thực tế là thuật ngữ cho loại tối ưu hóa này ở dạng tổng quát nhất, đệ quy-bất khả tri. Tối ưu hóa này không thay thế đệ quy bằng một vòng lặp while hoặc một thứ gì đó tương tự. Thay vào đó, các cuộc gọi đuôi được chuyển đổi sao cho khung ngăn xếp của người gọi được sử dụng lại. Mọi mã của biểu mẫu return f(...) hoặc f(...); return đều có thể sửa đổi được. Nó hoạt động cho bất kỳf, ngay cả đối với hàm con trỏ/đóng/phương pháp ảo nơi trình biên dịch không thể biết được những gì đang được gọi. Do đó, nó cũng hoạt động tốt hơn với các trình biên dịch riêng biệt, các hàm bậc cao hơn, kết thúc trễ, v.v.

Nếu bạn xem mã đủ, có chức năng hoặc bắt buộc, bạn sẽ tìm thấy các cuộc gọi không theo sau. Một trường hợp phổ biến là khi người gọi đại biểu đến callee cho nhiệm vụ chính và chỉ thực hiện một số chuẩn bị bổ sung. Trong mã chức năng, bạn thường sẽ tìm thấy nhiều chức năng nhỏ chỉ thực hiện một điều và được thực hiện theo các chức năng nhỏ khác, vì vậy bạn sẽ có một vài lớp áp dụng một phép biến đổi đơn giản cho các đối số, sau đó thực hiện cuộc gọi đuôi đến lớp tiếp theo (với dữ liệu được chuyển đổi làm đối số). TCO tối ưu hóa bước thứ hai, nó (lý tưởng) làm cho các cuộc gọi giá rẻ như một đơn giản jump và làm cho các mã mô-đun đẹp, mất ít không gian ngăn xếp hơn là một thực hiện nguyên khối hơn. Trong một thiết kế hướng đối tượng có thể bạn muốn soạn một đối tượng của các đối tượng khác và tiếp xúc với các phương pháp tiện lợi mà đại biểu:

SomeClass doSomething(Argument a) { 
    log.debug("Doing something"); 
    return this.somethingDoer.doIt(a, this.someExtraData); 
} 

Một ví dụ khác đó là về mặt kỹ thuật đệ quy lẫn nhau, nhưng thường chỉ có rất ít kích hoạt của bất kỳ chức năng nhất định (với hàng chục hoặc hàng trăm hoạt động khác ở giữa), là các máy trạng thái được triển khai bằng cách có một chức năng cho mỗi tiểu bang và gọi nó là nhập trạng thái đó:

void stateA() { 
    // do actual work 
    // determine which transition applies 
    stateB(); 
} 

void stateB() { 
    // do actual work 
    // determine which transition applies 
    state...(); 
} 

// dozens, possibly hundreds of other states