StackOverflowError cho thay đổi đồng xu trong Scala?

Question

Tôi đang viết chức năng đệ quy cho số Coin (change) problem trong Scala.

Thời gian thực hiện của tôi với StackOverflowError và tôi không thể hiểu tại sao nó xảy ra.

Exception in thread "main" java.lang.StackOverflowError 
    at scala.collection.immutable.$colon$colon.tail(List.scala:358) 
    at scala.collection.immutable.$colon$colon.tail(List.scala:356) 
    at recfun.Main$.recurs$1(Main.scala:58) // repeat this line over and over 

đây là cuộc gọi của tôi:

println(countChange(20, List(1,5,10))) 

đây là định nghĩa của tôi:

def countChange(money: Int, coins: List[Int]): Int = { 

    def recurs(money: Int, coins: List[Int], combos: Int): Int = 
    {  
     if (coins.isEmpty) 
      combos 
     else if (money==0) 
      combos + 1 
     else 
      recurs(money,coins.tail,combos+1) + recurs(money-coins.head,coins,combos+1) 

    } 
    recurs(money, coins, 0) 
} 

Chỉnh sửa: Tôi chỉ cần thêm sự khác câu lệnh if trong hỗn hợp:

else if(money<0) 
    combos 

nó đã thoát khỏi lỗi nhưng đầu ra của tôi là 1500 cái gì đó: (w mũ là sai với logic của tôi?

Answer 1

Dưới đây là giải pháp đúng đắn dựa trên mã của bạn:

def countChange(money: Int, coins: List[Int]): Int = { 
    def recurs(m: Int, cs: List[Int], cnt: Int): Int = 
     if(m < 0) cnt //Not a change, keep cnt 
     else if(cs.isEmpty) { 
     if(m == 0) cnt + 1 else cnt // plus cnt if find a change 
     } 
     else recurs(m, cs.tail, cnt) + recurs(m-cs.head, cs, cnt) 
    recurs(money, coins, 0) 
} 

Dù sao, có một giải pháp ngắn (Nhưng không hiệu quả, bạn có thể cache kết quả trung để làm cho nó có hiệu quả.)

def countChange(m: Int, cs: List[Int]): Int = cs match { 
    case Nil => if(m == 0) 1 else 0 
    case c::rs => (0 to m/c) map (k => countChange(m-k*c,rs)) sum 
} 

Answer 2

giải pháp các @Eastsun là tốt nhưng nó không thành công khi tiền = 0 do nó trả về 1 thay vì 0, nhưng bạn có thể sửa chữa nó một cách dễ dàng:

def countChange(money: Int, coins: List[Int]): Int = { 
    def recurs(m: Int, cs: List[Int], cnt: Int): Int = 
     if(m < 0) cnt //Not a change, keep cnt 
     else if(cs.isEmpty) { 
     if(m == 0) cnt + 1 else cnt // plus cnt if find a change 
     } 
     else recurs(m, cs.tail, cnt) + recurs(m-cs.head, cs, cnt) 
    if(money>0) recurs(money, coins, 0) else 0 
} 

Answer 3

Ta có thể bỏ qua tham số cnt, trên thực tế, không bao giờ được tích lũy. Chức năng tái phát luôn trả về 0 hoặc 1, vì vậy các thuật toán tối ưu sẽ là:

def countChange(money: Int, coins: List[Int]): Int = { 
    def recurs(m: Int, cs: List[Int]): Int = 
     if(m < 0) 0 //Not a change, return 0 
     else if(cs.isEmpty) { 
     if(m == 0) 1 else 0 // 1 if change found, otherwise 0 
     } 
     else recurs(m, cs.tail) + recurs(m-cs.head, cs) 
    if(money>0) recurs(money, coins) else 0 
} 

Answer 4

Các giải pháp đầu tiên trong the accepted answer có một tham số cuối cùng thừa as noted by Paaro vì vậy tôi muốn thoát khỏi nó. Giải pháp thứ hai sử dụng map mà tôi muốn tránh vì nó chưa được đề cập trong Tuần 1 hoặc khóa học Scala mà tôi cho là bạn đang dùng. Ngoài ra, giải pháp thứ hai, như được ghi chú đúng bởi tác giả, sẽ chậm hơn, trừ khi nó sử dụng một số ghi nhớ. Cuối cùng, Paaro's solution dường như có chức năng lồng nhau không cần thiết.

Vì vậy, đây là những gì tôi đã kết thúc với:

def countChange(money: Int, coins: List[Int]): Int = 
    if (money < 0) 
    0 
    else if (coins.isEmpty) 
    if (money == 0) 1 else 0 
    else 
    countChange(money, coins.tail) + countChange(money - coins.head, coins) 

Không cần cho niềng răng ở đây, như bạn có thể nhìn thấy.

Tôi tự hỏi nếu nó có thể đơn giản hơn nữa.

Answer 5

đây là một cách tiếp cận DP để giảm rất nhiều tính lại trong cách tiếp cận đệ quy

object DP { 
    implicit val possibleCoins = List(1, 5, 10, 25, 100) 
    import collection.mutable.Map 

    def countChange(amount: Int)(implicit possibleCoins: List[Int]) = { 
    val min = Map((1 to amount).map (_->Int.MaxValue): _*) 
    min(0) = 0 
    for { 
     i <- 1 to amount 
     coin <- possibleCoins 
     if coin <= i && min(i - coin) + 1 < min(i) 
    } min(i) = min(i-coin) + 1 
    min(amount) 
    } 

    def main(args: Array[String]) = println(countChange(97)) 
} 

thấy DP from novice to advanced cho thuật toán