Implementing a recursive function using pattern matching

Question

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()
}

score 3 · Accepted Answer · answered May 01 '14 at 13:41

3

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.

answered May 01 '14 at 13:41

wheaties

35,646
15
94
131

Ok, got it. Another question: Is it good practice to have two case statements with `_`? Would it be more idiomatic to write this function using `if-else` statements as I have in the first function, `pascal`? – May 01 '14 at 14:28
Screw idiomatic. Do whatever you and your group have agreed is most readable. – wheaties May 01 '14 at 14:34
Also possible: `case \`r\` => 1` (literal), `case \`r\` | 0 => 1` (combination). See http://stackoverflow.com/a/7078077/2963903 – leewz Jul 02 '14 at 07:12

bluenote10 · Answer 2 · 2014-05-02T11:14:43.667

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.

Implementing a recursive function using pattern matching

2 Answers2

Alternative 1

Alternative 2