Scala có hỗ trợ tối ưu đệ quy đuôi không?

Question

Scala có hỗ trợ tối ưu đệ quy đuôi không?

Answer 1

Scala tối ưu hóa đệ quy đuôi lúc biên dịch, như các áp phích khác đã nói. Đó là, một hàm đệ quy đuôi được chuyển thành một vòng lặp bởi trình biên dịch (một phương thức gọi được chuyển thành một bước nhảy), như có thể thấy từ dấu vết ngăn xếp khi chạy một hàm đệ quy đuôi.

Hãy thử đoạn mã sau:

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1) 
boom(10) 

và kiểm tra vết đống. Nó sẽ chỉ hiển thị một cuộc gọi đến chức năng bùng nổ - do đó bytecode được biên dịch không đệ quy.

Có một đề xuất nổi xung quanh implement tail calls at the JVM level - theo ý kiến ​​của tôi sẽ là điều tuyệt vời để làm, khi đó JVM có thể thực hiện tối ưu hóa thời gian chạy, thay vì chỉ biên dịch tối ưu hóa mã - và có thể có nghĩa là đuôi linh hoạt hơn đệ quy. Về cơ bản, tailcall invoke sẽ hoạt động chính xác như một phương thức bình thường invoke nhưng sẽ thả ngăn xếp của người gọi khi an toàn để làm như vậy - đặc tả của JVM nói rằng các khung ngăn xếp phải được bảo toàn, vì vậy JIT phải thực hiện một số phân tích mã tĩnh tìm hiểu xem các khung ngăn xếp sẽ không bao giờ được sử dụng hay không.

Trạng thái hiện tại của nó là proto 80%. Tôi không nghĩ rằng nó sẽ được thực hiện trong thời gian cho Java 7 (invokedynamic có một ưu tiên lớn hơn, và việc thực hiện gần như được thực hiện) nhưng Java 8 có thể thấy nó được thực hiện.

Answer 2

Chỉ trong các trường hợp rất đơn giản, trong đó chức năng là tự đệ quy.

Proof of tail recursion ability.

Dường như Scala 2.8 có thể cải thiện đuôi-đệ quy công nhận, mặc dù.

Answer 3

Scala 2.7.x hỗ trợ tối ưu hóa cuộc gọi đuôi để tự đệ quy (một hàm gọi chính nó) của các phương thức cuối cùng và các hàm cục bộ.

Scala 2.8 có thể đi kèm với thư viện hỗ trợ cho tấm bạt lò xo quá, đó là một kỹ thuật để tối ưu hóa các chức năng đệ quy lẫn nhau.

Rất nhiều thông tin về trạng thái đệ quy Scala có thể được tìm thấy trong Rich Dougherty's blog.

Answer 4

Trong Scala 2.8 bạn có thể sử dụng để đánh dấu @tailrec phương pháp cụ thể mà bạn hy vọng các trình biên dịch sẽ tối ưu hóa:

import scala.annotation.tailrec 

@tailrec def factorialAcc(acc: Int, n: Int): Int = { 
    if (n <= 1) acc 
    else factorialAcc(n * acc, n - 1) 
} 

Nếu một phương pháp không thể được tối ưu hóa bạn nhận được một cảnh báo.