title: StackOverflowError for coin change in Scala?
body: <p>I'm writing a recursive function for the <a href="http://en.wikipedia.org/wiki/Coin_problem" rel="nofollow">Coin (change) problem</a> in Scala.</p>
  
  <p>My implementation breaks with StackOverflowError and I can't figure out why it happens.</p>
  
  <pre><code>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
  </code></pre>
  
  <p>this is my call:</p>
  
  <pre><code>  println(countChange(20, List(1,5,10)))
  </code></pre>
  
  <p>this is my definition:</p>
  
  <pre><code>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)
  } 
  </code></pre>
  
  <p>Edit: I just added the else if statement in the mix:</p>
  
  <pre><code>else if(money&lt;0)
      combos
  </code></pre>
  
  <p>it got rid of the error but my output is 1500 something :( what is wrong with my logic?</p>