Chức năng đệ quy, Ngăn xếp ngăn xếp và Bộ kết hợp Y

Question

Tôi có chức năng đệ quy (trong C#) mà tôi cần gọi khoảng 800 triệu lần; điều này rõ ràng thường sẽ dẫn đến tràn ngăn xếp sau khoảng cuộc gọi thứ 900. Tôi đã thực hiện điều này với nhiều vòng lặp, nhưng mô hình đệ quy thì dễ dàng hơn nhiều và dễ bảo trì hơn.

Tôi đang xem xét triển khai hàm đệ quy sử dụng bộ kết hợp y, như từ những gì tôi đọc và thấy, sẽ giải quyết vấn đề tràn ngăn xếp và sửa nhiều vòng lồng nhau.

Có ai có kinh nghiệm sử dụng bộ kết hợp y không? Tôi vẫn sẽ bị kẹt trong một ngăn xếp tràn?

Lấy ví dụ đơn giản về giai thừa. Giai thừa trên hầu hết các số lớn hơn 5.000 sẽ gây ra tràn ngăn xếp. Nếu tôi sử dụng một bộ phối hợp y đúng cách trong kịch bản đó, nó sẽ sửa chữa tràn ngăn xếp?

Nó không có vẻ tầm thường để thực hiện, vì vậy tôi muốn xác nhận nó trước khi tôi dành nỗ lực phát triển/tài nguyên triển khai và học y combinator.

Answer 1

Không, việc sử dụng bộ kết hợp Y sẽ không giúp được tình huống của bạn. Nếu bạn cần làm điều gì đó 800 triệu lần, bạn có thể (a) recurse, hoặc (b) loop (hoặc tôi giả sử (c) viết 800 triệu cuộc gọi đến chức năng của bạn). Vì bộ kết hợp Y không lặp lại, do đó nó phải tái chế.

Vòng lặp là thứ bạn đang tìm kiếm, trừ khi bạn đang sử dụng môi trường thời gian chạy cung cấp đệ quy đuôi thích hợp (chẳng hạn như Sơ đồ).

Có nói rằng, việc thực hiện bộ kết hợp Y từ đầu bằng ngôn ngữ bạn chọn là một bài tập tuyệt vời.

Answer 2

Bộ kết hợp Y rất hữu ích nhưng tôi nghĩ rằng bạn thực sự muốn tối ưu hóa đệ quy đuôi giúp loại bỏ việc sử dụng ngăn xếp cho các hàm đệ quy đuôi. Đợt đệ quy chỉ có thể xảy ra khi kết quả của mọi cuộc gọi đệ quy ngay lập tức được trả về bởi người gọi và không bao giờ tính thêm bất kỳ sau cuộc gọi. Thật không may, C# không hỗ trợ tối ưu hóa đệ quy đuôi, tuy nhiên bạn có thể mô phỏng nó bằng một tấm bạt lò xo cho phép chuyển đổi đơn giản từ phương pháp đệ quy đuôi sang phương pháp quấn tấm bạt lò xo.

// Tail 
int factorial(int n) { return factorialTail(n, 1, 1); } 
int factorialTail(int n, int i, int acc) { 
    if (n < i) return acc; 
    else return factorialTail(n, i + 1, acc * i); 
} 

// Trampoline 
int factorialTramp(int n) { 
    var bounce = new Tuple<bool,int,int>(true,1,1); 
    while(bounce.Item1) bounce = factorialOline(n, bounce.Item2, bounce.Item3); 
    return bounce.Item3; 
} 
Tuple<bool,int,int> factorialOline(int n, int i, int acc) { 
    if (n < i) return new Tuple<bool,int,int>(false,i,acc); 
    else return new Tuple<bool,int,int>(true,i + 1,acc * i); 
} 

Answer 3

Bạn có thể sử dụng tấm bạt lò xo như được sử dụng trong phản ứng mở rộng, tôi đã cố gắng giải thích nó trên blog của tôi http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Một giải pháp là để chuyển đổi chức năng của bạn (s) để sử dụng một vòng lặp và một rõ ràng bối cảnh cấu trúc dữ liệu. Bối cảnh đại diện cho những gì mọi người thường nghĩ đến như là ngăn xếp cuộc gọi. Bạn có thể tìm thấy my answer to another question about converting to tail recursion hữu ích. Các bước liên quan là từ 1 đến 5; 6 và 7 là đặc trưng cho chức năng cụ thể đó, trong khi âm thanh của bạn phức tạp hơn.

Cách thay thế "dễ dàng" là thêm bộ đếm chiều sâu vào từng chức năng của bạn; khi nó chạm một số giới hạn (được xác định bằng thử nghiệm), sinh ra một luồng mới để tiếp tục đệ quy với một chồng mới. Các khối chuỗi cũ đang chờ chuỗi mới gửi kết quả (hoặc nếu bạn muốn được ưa thích, kết quả hoặc ngoại lệ để tăng lại). Bộ đếm chiều sâu quay trở lại 0 cho chuỗi mới; khi nó đạt đến giới hạn, hãy tạo một chuỗi thứ ba, v.v. Nếu bạn lưu trữ các chuỗi để tránh phải trả chi phí tạo chuỗi thường xuyên hơn mức cần thiết, hy vọng bạn sẽ nhận được hiệu suất chấp nhận được mà không cần phải tái cơ cấu mạnh mẽ chương trình của mình.