CODEWITHSUNDEEP
scala
user3248346
user3248346

Reputation:

Implementing a recursive function using pattern matching

I want to rewrite a recursive function using pattern matching instead of if-else statements, but I am getting (correct) warning messages that some parts of the code are unreachable. In fact, I am getting wrong logic evaluation.

The function I am trying to re-write is:

def pascal(c: Int, r: Int): Int =
  if (c == 0)
    1
  else if (c == r)
    1
  else
    pascal(c - 1, r - 1) + pascal(c, r - 1)

This function works as expected. I re-wrote it as follows using pattern matching but now the function is not working as expected:

def pascal2 (c : Int, r : Int) : Int = c match {
  case 0 => 1
  case r => 1
  case _ => pascal2(c - 1, r - 1) + pascal2(c, r - 1)
}

Where am I going wrong?

Main:

println("Pascal's Triangle")
for (row <- 0 to 10) {
  for (col <- 0 to row)
    print(pascal(col, row) + " ")
  println()
}

Upvotes: 2

Views: 706

Answers (2)

bluenote10
bluenote10

Reputation: 26560

I fully agree with @wheaties and advice you to follow his directions. For sake of completeness I want to point out a few alternatives.

Alternative 1

You could write your own unapply:

def pascal(c: Int, r: Int): Int = { 
  object MatchesBoundary {
    def unapply(i: Int) = if (i==0 || i==r) Some(i) else None
  }
  c match {
    case MatchesBoundary(_) => 1
    case _ => pascal(c-1, r-1) + pascal(c, r-1)
  }
}

I would not claim that it improves readability in this case a lot. Just want to show the possibility to combine semantically similar cases (with identical/similar case bodies), which may be useful in more complex examples.

Alternative 2

There is also a possible solution, which exploits the fact that Scala's syntax for pattern matching only treats lower case variables as variables for a match. The following example shows what I mean by that:

def pascal(c: Int, r: Int): Int = { 
  val BoundaryL = 0
  val BoundaryR = r
  c match {
    case BoundaryL => 1
    case BoundaryR => 1
    case _ => pascal(c-1, r-1) + pascal(c, r-1)
  }
}

Since BoundaryL and BoundaryR start with upper case letters they are not treated as variables, but are used directly as matching object. Therefore the above works (while changing them to boundaryL and boundaryR would not, which btw also gives compiler warnings). This means that you could get your example to work simply by replacing r by R. Since this is a rather ugly solution I mention it only for educational purposes.

Upvotes: 1

wheaties
wheaties

Reputation: 35980

The following statement "shadows" the variable r:

case r =>

That is to say, the "r" in that case statement is not, in fact, the "r" that you have defined above. It is it's own "r" which is equivalently equal to "c" because you are telling Scala to assign any value to some variable named "r."

Hence, what you really want is:

def pascal2(c: Int, r: Int): Int = c match{
  case 0 => 1
  case _ if c == r => 1
  case _ => pascal2(c-1, r-1) + pascal2(c, r-1)
}

This is not, however tail recursive.

Upvotes: 3

Related Questions