Stack-overflow in scala recursive change coin function

Question

Looking at the resources that the scala course from coursera offers I found an algorithm which should work ( the logic should work ) however when implemented in scala it returns a stack-overflow. I think I know what a stack is as I have played in C for a bit but I don't understand how the following function can use up so much memory:

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


    def cc(amount: Int, list: List[Int]): Int = {
      if (amount == 0) 1
      if (amount < 0 || list.isEmpty) 0

      return cc(amount - list.head, list) + cc(amount, list.tail)

    }

    cc(money, coins)






  }

Here is the error:

Exception in thread "main" java.lang.StackOverflowError
at java.lang.Integer.valueOf(Unknown Source)
at scala.runtime.BoxesRunTime.boxToInteger(BoxesRunTime.java:70)
at recfun.Main$.cc$1(Main.scala:78)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)
at recfun.Main$.cc$1(Main.scala:80)

Here is the call to the function:

 println ("" + countChange(10,List(2,3,5)))

Two comments: You're supposed to solve this yourself (you did read the honor code you agreed to, right?) and what have you tried to debug it? At the least, I'd expect you to have added a println in each branch to track what was happening, and that would have shown the problem pretty quickly — The Archetypal Paul
– The Archetypal Paul, Commented May 8, 2014 at 9:20
@Paul I am doing this myself. This is not a question regarding in any way how to create this. This is a question regarding why I'm having a stack-overflow error since I don't expect that a function which recurs itself 5 times will use up all the allocated memory given by the stack. I have read the honour code and it states that no code should be copied and pasted and should be created by yourself. As I have said 2 lines above I'm not asking you for the code nor even how to create this. I'm asking you to kindly help me debug why I'm using up all memory allocated by the stack — Bula
– Bula, Commented May 8, 2014 at 14:22
No, the honor code does not state that. It actually says "My answers to homework, quizzes and exams will be my own work (except for assignments that explicitly permit collaboration)." That's rather more than the actual code. And independent of that, a few printlns would have quuikly shown you it doesn't "recur itself 5 times", of course. Anyway, I see you've posted another version of the same question. Hopefully you have something working now. — The Archetypal Paul
– The Archetypal Paul, Commented May 8, 2014 at 15:52

Yuriy · Accepted Answer · 2014-05-08 07:39:45Z

3

Wrong return behavior (mix expressions and statements)

Without return keyword:

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

Or with return keyword:

def countChange1(money: Int, coins: List[Int]): Int = {
  def cc(amount: Int, list: List[Int]): Int = {
    if (amount == 0) return 1
    if (amount < 0 || list.isEmpty) return 0
    return cc(amount - list.head, list) + cc(amount, list.tail)
  }
  cc(money, coins)
}

edited May 8, 2014 at 7:39

answered May 8, 2014 at 7:32

Yuriy

2,77915 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Stack-overflow in scala recursive change coin function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related