1

Learning Scala at the moment, learning about pattern matching in particular, I wrote this simple factorial method in Scala:

 def factorial(n : Int) : Int = {
   if(n <= 1)
     1
   else
    n * factorial(n -1)
}

Then I thought to myself, I could just use pattern matching and wrote this:

def fact(n : Int) : Int = n match {
  case 0 => 1
  case n => n * fact(n -1)
}

But I thought the point of pattern matching was sorting on data, why would I ever need to use this on something like factorial?

much appreciated.

user2405469
  • 1,953
  • 2
  • 22
  • 43
  • 2
    You don't need to do this. But you can, as you just prooved. – Jens Schauder Aug 30 '15 at 10:05
  • This is cute. Fibonacci would be cuter, because you need two initial settings. But doing Fibonacci through recursion is somewhat silly as well, as it doesn't scale nicely. – Paul Aug 30 '15 at 10:06
  • @Paul: What makes you say a recursive implementation of Fibonacci wouldn't scale? A tail-recursive implementation will scale just as well as an iterative one. – Marth Aug 30 '15 at 10:13
  • @Marth I'm not an expert on its scalability, but I seem to recall that because Fibonacci is one of those functions that becomes exponentially difficult to calculate as N grows *unless* values are memoized. – Paul Aug 30 '15 at 10:30
  • [O(2^N)](http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) – Paul Aug 30 '15 at 10:34
  • @Marth When Fibonacci is done bottom-up, iteratively, and those values stored, there is a lot less duplication of effort than if it is called top-down recursively, with no memoization. – Paul Aug 30 '15 at 10:37
  • @Paul: Well yeah, using a naive recursive approach will yield horrendous performances. However you *can* use a recursive approach and still have performances similar to that of a iterative one (if your language supports tail-recursion that is). – Marth Aug 30 '15 at 10:46
  • 2
    @Marth That's good to know. I found some more [here](http://stackoverflow.com/questions/1677419/does-scala-support-tail-recursion-optimization) – Paul Aug 30 '15 at 10:53

2 Answers2

2

But I thought the point of pattern matching was sorting on data

Actually pattern matching is great for writing any type of algorithm (like the one you have in your example). In fact, most part of the Functional Programming in Scala online course by Odersky focuses a lot in writing algorithms using pattern matching.

marios
  • 8,874
  • 3
  • 38
  • 62
0

Data deconstruction and extraction, coupled with data types, are essential in pattern matching.

In the case of factorial we extract and treat values larger than one in a different way to value one, perhaps a trivial use of pattern matching which may well be replaced with and if-else expression.

elm
  • 20,117
  • 14
  • 67
  • 113