MATLAB có thực hiện tối ưu hóa cuộc gọi đuôi không?

Question

Gần đây tôi đã học được Haskell và đang cố gắng mang phong cách chức năng thuần túy đến mã khác của tôi khi có thể. Một khía cạnh quan trọng của việc này là xử lý tất cả các biến là không thay đổi, tức là hằng số. Để làm như vậy, nhiều tính toán sẽ được thực hiện bằng cách sử dụng vòng trong một phong cách bắt buộc phải được thực hiện bằng cách sử dụng đệ quy, thường phát sinh một hình phạt bộ nhớ do việc phân bổ một khung stack mới cho mỗi cuộc gọi chức năng. Trong trường hợp đặc biệt của một cuộc gọi đuôi (nơi mà giá trị trả về của một hàm được gọi ngay lập tức được trả về cho người gọi của callee), tuy nhiên, hình phạt này có thể bị bỏ qua bởi một quá trình gọi là tối ưu hóa cuộc gọi đuôi (trong một phương pháp, điều này có thể được thực hiện) về cơ bản thay thế cuộc gọi bằng jmp sau khi thiết lập ngăn xếp đúng). MATLAB có thực hiện TCO theo mặc định hay không hoặc có cách nào để nói cho nó biết không?

Answer 1

Nếu tôi xác định một đơn giản đuôi-đệ quy chức năng:

function tailtest(n) 
    if n==0; feature memstats; return; end 
    tailtest(n-1); 
end 

và gọi nó để nó sẽ recurse khá sâu sắc:

set(0,'RecursionLimit',10000); 
tailtest(1000); 

sau đó nó không giống như các khung stack là ăn nhiều bộ nhớ. Tuy nhiên, nếu tôi làm cho điều đó trở nên sâu sắc hơn nhiều:

set(0,'RecursionLimit',10000); 
tailtest(5000); 

sau đó (trên máy của tôi, hôm nay) MATLAB chỉ gặp sự cố: quá trình này không được thực hiện.

Tôi không nghĩ điều này phù hợp với MATLAB thực hiện bất kỳ TCO nào; trường hợp mà một hàm gọi chính nó, chỉ ở một nơi, không có biến cục bộ nào ngoài một đối số đơn lẻ, chỉ đơn giản là như mọi người có thể hy vọng.

Vì vậy: Không, có vẻ như MATLAB hoàn toàn không làm TCO, ít nhất theo mặc định. Tôi đã không (cho đến nay) tìm kiếm các tùy chọn có thể kích hoạt nó. Tôi sẽ ngạc nhiên nếu có.

Trong trường hợp chúng tôi không thổi ra ngăn xếp, chi phí đệ quy là bao nhiêu? Xem nhận xét của tôi về câu trả lời của Bill Cheatham: có vẻ như thời gian trên không vô nghĩa nhưng không điên.

... Ngoại trừ việc Bill Cheatham đã xóa câu trả lời của mình sau khi tôi để lại nhận xét đó. ĐƯỢC. Vì vậy, tôi đã thực hiện lặp đi lặp lại đơn giản của hàm Fibonacci và một hàm đệ quy đuôi đơn giản, thực hiện cùng một tính toán trong cả hai và định thời gian cho cả hai trên fib(60). Việc triển khai đệ quy mất khoảng 2,5 lần để chạy hơn so với lặp lại. Tất nhiên, chi phí tương đối sẽ nhỏ hơn đối với các hàm hoạt động nhiều hơn một phép cộng và một phép trừ cho mỗi lần lặp.

(Tôi cũng đồng ý với tình cảm delnan của:. Đang được đánh giá cao đệ quy của các loại mà cảm thấy tự nhiên trong Haskell là thường có khả năng là unidiomatic trong MATLAB)