Sau đây sẽ gây ra tràn ngăn xếp cho lớn 'n', và tôi có thể hiểu tại sao.Tại sao mã này gây ra tình trạng tràn ngăn xếp?
def factorial(n)
(n > 1) ? (return (n * factorial(n - 1))) : (return 1)
end
Tại sao nguyên nhân sau cũng bị tràn?
def factorial(n, k)
(n > 1) ? (return factorial(n - 1, lambda {|v| return k.call(v * n)})) : (return k.call(1))
end
Thuật toán thứ hai của bạn tạo ra một chuỗi các quy trình lambda n dài, mỗi quy trình chứa tham chiếu đến quy trình trước đó. Tôi không biết chính xác những gì Ruby làm, nhưng trong một ngôn ngữ đuôi đệ quy đúng, ngăn xếp sẽ không tràn trong thuật toán thứ hai của bạn, bởi vì k.call trong lambda cũng ở vị trí đuôi. Nếu, như thử nghiệm của Brian cho thấy, Ruby không có các cuộc gọi đuôi thích hợp, chuỗi các cuộc gọi lồng nhau tới chuỗi lambda n sẽ tràn ngăn xếp khi người đứng đầu chuỗi được gọi, mặc dù Ruby đủ thông minh để chuyển đổi đuôi -recursive factorial gọi vào vòng lặp (= tối ưu hóa cuộc gọi đuôi).
Phiên bản thứ hai vẫn còn đệ quy về giai thừa. Tôi nghĩ Ruby không làm TCO. Nhưng nó không thổi cho đến khi nó đạt đến lambdas. Tôi bối rối. (Mọi người khác thậm chí còn bối rối hơn, hoặc không đọc được câu hỏi. Tôi đang downvoting những người khác một cách thích hợp.) –
"Nhưng nó không thổi cho đến khi nó đạt đến lambdas." - er? Tôi không hiểu. –
Cho rằng ví dụ thứ hai vẫn đang đệ quy trên 'factorial', tôi đã dự kiến nó sẽ tràn ngăn xếp trước khi nó đạt đến trường hợp cơ sở' k.call (1) '. Nhưng trong đoạn mã ví dụ thứ hai ở trên, các lời gọi đến 'giai thừa' không tràn ngăn xếp (ngay cả đối với n rất lớn), đó là hành vi khác với ví dụ đầu tiên. Ví dụ thứ hai đạt được trường hợp cơ sở đó và không tràn cho đến khi nhiều 'k.call' đã diễn ra. Nếu không có TCO, tôi không thấy nó làm cho nó xa như thế nào. –
Như trong hàm đầu tiên, các cuộc gọi đệ quy có thể kết thúc quá nhiều để hệ thống xử lý.
Trong hầu hết các ngôn ngữ, các cuộc gọi chức năng đi vào ngăn xếp cuộc gọi ngăn xếp, thực sự chỉ là ngăn xếp. Gọi một hàm đệ quy sẽ tiếp tục thêm vào ngăn xếp cuộc gọi. Cuối cùng bạn điền vào ngăn xếp, và bạn nhận được một tràn ngăn xếp. Đó luôn luôn là một nguy hiểm khi chạy một hàm đệ quy nơi mức đệ quy của bạn sẽ trở nên sâu sắc.
-1: cf. "Sau đây sẽ tràn cho lớn 'n', và tôi có thể hiểu tại sao" –
Vì lý do tương tự, thiết bị đầu tiên có tràn ngăn xếp ... Chuỗi cuộc gọi quá lớn.
Tràn? hoặc StackOverflow ?! –
-1, Thuộc về dịch vụ sử dụng. –