Scala người mới: đệ quy và stackoverflow lỗi

Question

Là một newbie Scala, tôi đang đọc sách, tài liệu và cố gắng giải quyết vấn đề được tìm thấy trên http://aperiodic.net/phil/scala/s-99/. Có vẻ như mã Scala chính xác được dựa trên các giá trị bất biến (val) và trên đệ quy hơn là trên các vòng lặp và các biến để làm cho tính song song an toàn hơn và tránh sử dụng khóa.

Ví dụ, một giải pháp khả thi cho P22 tập thể dục (http://aperiodic.net/phil/scala/s-99/p22.scala) là:

// Recursive. 
def rangeRecursive(start: Int, end: Int): List[Int] = 
if (end < start) Nil 
else start :: rangeRecursive(start + 1, end) 

Tất nhiên mã này là nhỏ gọn và trông thông minh nhưng, dĩ nhiên, nếu số lượng đệ quy là cao, bạn sẽ đối mặt với lỗi StackOverflow (rangeRecusrsive (1.10000) chẳng hạn như không có điều chỉnh JVM). Nếu bạn nhìn vào nguồn của xây dựng trong List.range (https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1), bạn sẽ thấy rằng các vòng lặp và vars được sử dụng.

Câu hỏi của tôi là làm thế nào để quản lý các ảnh hưởng của các công cụ học tập Scala mà đang xúc tiến Vals và đệ quy khi biết rằng mã như vậy có thể phá vỡ do số lượng của đệ quy?

Answer 1

Điều tốt đẹp về Scala là bạn có thể dễ dàng theo cách của bạn. Bắt đầu, bạn có thể viết các vòng lặp và làm nhiều hơn với đệ quy khi bạn phát triển thoải mái hơn với ngôn ngữ. Bạn không thể làm điều này với các ngôn ngữ chức năng 'thuần khiết' hơn như Clojure hoặc Haskell. Nói cách khác, bạn có thể cảm thấy thoải mái với bất biến và val và chuyển sang đệ quy sau.

Khi bạn bắt đầu với đệ quy, bạn nên tra cứu cuộc gọi đuôi. Nếu cuộc gọi đệ quy là cuộc gọi cuối cùng trong hàm, trình biên dịch Scala sẽ tối ưu hóa điều này thành một vòng lặp trong bytecode. Bằng cách đó, bạn sẽ không nhận được StackOverflowError giây. Ngoài ra, nếu bạn thêm chú thích @tailrec vào hàm đệ quy của mình, trình biên dịch sẽ cảnh báo bạn nếu hàm của bạn không phải là đuôi gọi đệ quy.

Ví dụ: hàm trong câu hỏi của bạn không phải là đệ quy cuộc gọi đuôi. Có vẻ như cuộc gọi tới số rangeRecursive là cuộc gọi cuối cùng trong hàm, nhưng khi cuộc gọi này trả về, nó vẫn phải thêm start vào kết quả của cuộc gọi. Vì vậy, nó không thể được gọi là đệ quy đuôi: nó vẫn phải làm việc khi cuộc gọi trả về.

Answer 2

Nếu bạn viết lại phần trên để đuôi đệ quy, trình biên dịch sẽ tối ưu hóa mã thành vòng lặp while. Ngoài ra, bạn có thể sử dụng chú thích @tailrec để nhận lỗi khi phương thức chú thích không phải là đệ quy đuôi. Vì vậy, cho phép bạn biết "khi bạn đã nhận nó đúng".

Answer 3

Dưới đây là ví dụ về cách làm cho phương thức đó đệ quy đuôi. Chú thích @tailrec là không cần thiết, trình biên dịch sẽ tối ưu hóa mà không cần nó. Nhưng có nó làm cho trình biên dịch cờ một lỗi khi nó không thể làm tối ưu hóa.

scala> def rangeRecursive(start: Int, end: Int): List[Int] = { 
    | @scala.annotation.tailrec 
    | def inner(accum : List[Int], start : Int) : List[Int] = { 
    |  if (end < start) accum.reverse 
    |  else inner(start :: accum, start + 1) 
    | } 
    | 
    | inner(Nil, start) 
    | } 
rangeRecursive: (start: Int,end: Int)List[Int] 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

Nó sử dụng kỹ thuật chung được gọi là "kiểu chuyển tiếp tích lũy" trong đó kết quả trung gian được tích lũy và chuyển sang bước tiếp theo trong đệ quy. Bước dưới cùng nhất là trách nhiệm trả lại kết quả tích lũy. Trong trường hợp này, bộ tích lũy sẽ xảy ra để xây dựng kết quả ngược của nó sao cho vỏ cơ sở phải đảo ngược nó.

Answer 4

Đây là một thay thế cho câu trả lời James Iry, với hành vi tương tự:

def rangeRecursive(start: Int, end: Int): List[Int] = { 
    def inner(start : Int) : Stream[Int] = { 
     if (end < start) Stream.empty 
     else start #:: inner(start + 1) 
    } 

    inner(start).toList 
} 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

này không ném một StackOverflowError vì Stream.cons -operator (#::) lưu trữ các đuôi bằng cách tham khảo.Nói cách khác, các phần tử Luồng không được tính cho đến khi stream.toList được gọi.

Theo tôi, đây là dễ đọc hơn so với mô hình ắc vì nó gần giống với hầu hết các thuật toán ban đầu ngây thơ (chỉ cần thay thế :: bởi #:: và Nil bởi Stream.empty). Ngoài ra, không cần thiết cho accum.reverse, có thể dễ dàng bị lãng quên.