CODEWITHSUNDEEP
scalarecursion
mzbaran
mzbaran

Reputation: 624

Understanding evaluation order in recursive scala countChange function

I have a function that counts the number of ways to count change given an amount of money and a list of coins. This function appears to pass basic unit tests but if I am being completely honest, I don't fully understand why it works.

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

    def countChangeRec(money: Int, coins: List[Int]): Int = {
      if (money == 0) 1
      else if(money > 0 && coins.nonEmpty) {
        countChangeRec(money - coins.head, coins) +
          countChangeRec(money, coins.tail)
      }
      else 0
    }

    if(money == 0 || coins.isEmpty) 0
    else countChangeRec(money, coins)
  }

Taking a basic example with arguments money = 4 and coins = List(1, 2)

I currently come up with the following evaluation order to return 2 (which is not correct).

  1. countChangeRec(4-1, List(1, 2)) + countChangeRec(4, List(2))
  2. countChangeRec(3-1, List(1, 2)) + countChangeRec(4-2, List(2))
  3. countChangeRec(2-1, List(1, 2)) + countChangeRec(2-2, List(2))
countChangeRec(1-1, List(1, 2)) // => 1 returns 1 since money = 0 
          + countChangeRec(0, List(2)) // => 1 since money = 0
  1. returns 2 // this is not the case since the functional actually returns 3.

Upvotes: 0

Views: 87

Answers (1)

Levi Ramsey
Levi Ramsey

Reputation: 20551

You can expand the evaluation as follows (the order doesn't actually matter, this being a pure function) using the evaluation order is to expand the left-most function application and evaluate integer additions:

  • countChangeRec(4, List(1, 2))
  • countChangeRec(3, List(1, 2)) + countChangeRec(4, List(2))
  • countChangeRec(2, List(1, 2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • countChangeRec(1, List(1, 2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • countChangeRec(0, List(1, 2)) + countChangeRec(1, List(2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 1 + countChangeRec(1, List(2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 1 + countChangeRec(-1, List(2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 1 + 0 + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 1 + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 1 + countChangeRec(0, List(2)) + countChangeRec(2, Nil) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 1 + 1 + countChangeRec(2, Nil) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 2 + countChangeRec(2, Nil) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 2 + 0 + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 2 + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
  • 2 + countChangeRec(1, List(2)) + countChangeRec(3, Nil) + countChangeRec(4, List(2))
  • 2 + countChangeRec(-1, List(2)) + countChangeRec(1, Nil) + countChangeRec(3, Nil) + countChangeRec(4, List(2))
  • 2 + 0 + countChangeRec(1, Nil) + countChangeRec(3, Nil) + countChangeRec(4, List(2))
  • 2 + countChangeRec(1, Nil) + countChangeRec(3, Nil) + countChangeRec(4, List(2))
  • 2 + 0 + countChangeRec(3, Nil) + countChangeRec(4, List(2))
  • 2 + countChangeRec(3, Nil) + countChangeRec(4, List(2))
  • 2 + 0 + countChangeRec(4, List(2))
  • 2 + countChangeRec(4, List(2))
  • 2 + countChangeRec(2, List(2)) + countChangeRec(4, Nil)
  • 2 + countChangeRec(0, List(2)) + countChangeRec(2, Nil) + countChangeRec(4, Nil)
  • 2 + 1 + countChangeRec(2, Nil) + countChangeRec(4, Nil)
  • 3 + countChangeRec(2, Nil) + countChangeRec(4, Nil)
  • 3 + 0 + countChangeRec(4, Nil)
  • 3 + countChangeRec(4, Nil)
  • 3 + 0
  • 3

each application of a function uses, effectively, its own copy of the arguments it's been passed.

This evaluation order is very similar to Scala's. The only difference is that this effectively evaluates function arguments in parallel, while in Scala it would be something like:

  • countChangeRec(4, List(1, 2))
  • countChangeRec(4-List(1, 2).head, List(1, 2)) + countChangeRec(4, List(1, 2).tail)
  • countChangeRec(4-1, List(1, 2)) + countChangeRec(4, List(1, 2).tail)
  • countChangeRec(3, List(1, 2)) + countChangeRec(4, List(1, 2).tail)

and so forth... so technically my evaluation strategy would correspond to

def countChangeRec(money: Int, coins: List[Int]): Int =
  if (money == 0) 1
  else if (money > 0 && coins.nonEmpty) {
    val minusHead = money - coins.head
    val tail = coins.tail
    countChangeRec(minusHead, coins) + countChangeRec(money, tail)
  } else 0

with the observation that since there's no dependency between minusHead and tail, we can evaluate them in parallel.

One important thing to know is that if an expression has no side effects (e.g. mutating a var or mutable structure, performing I/O, going into an infinite loop, or throwing an exception (this covers the 5 broad categories of impurity in Scala)), any strategy for evaluation which is compatible with data dependencies gives the same result. This includes parallelizing the evaluation (which includes offloading evaluation to a different computer), and caching results.

Upvotes: 1

Related Questions