Muavia Muavia - 1 month ago 24
Scala Question

coin change algorithm in scala using recursion

I am trying to program the coin change problem in Scala using recursion. The code that i have written is as follows.

def countChange(money: Int, coins: List[Int]): Int = {
def ways(change: List[Int], size: Int, capacity: Int): Int = {
if(capacity == 0) 1
if((capacity < 0) || (size <= 0)) 0

//println and readLine to check and control each recursive call.

println("calling ways(",change, change.length-1, capacity,") + ways(",change, change.length, capacity - change(change.length - 1),")")
readLine()
//

ways(change, change.length-1, capacity) + ways(change, change.length, capacity - change(change.length - 1))
}
ways(coins, coins.length, money)
}


On running the code, it does not terminate and keeps on calling the first recursive call. Where am I going wrong?

Answer

Simply stating a value does not make Scala return it; you either need an explicit return, or it has to be the last item stated. Thus:

if (capacity == 0) return 1

or

if (capacity == 0) 1
else if (...)
else { ... }