Bug in recursive implementation of Pascal's Triangle algorithm Classic List Threaded 4 messages Open this post in threaded view
|

Bug in recursive implementation of Pascal's Triangle algorithm

 I'm working through the Functional Programming in Scala track on Coursera; one of the early exercises consists of writing a recursive algorithm to calculate an element in Pascal's Triangle for a given row and column. The function should have the following signature:pascal(c: Int, r: Int): IntI should say upfront that I'm not looking for help with the exercise. It was fairly easy to solve:def pascal(c: Int, r: Int): Int = {  if (c == 0 || c == r) 1  else pascal(c - 1, r - 1) + pascal(c, r - 1)}This is simple and works, but is inefficient. I uncovered a bug while working at a (less readable) more efficient implementation, and I'm at my wit's end trying to understand it. The revised algorithm is simple enough. Here's a working version in JavaScript (written to prove that the algorithm works, and to preserve my sanity):function pascal(c, r) {    function loop(c, r) {        return (c == 0) ? 1 : (loop(c - 1, r) * ((r + 1 - c) / c))    }    return (c * 2 > r) ? loop(r - c, r) : loop(c, r)}// A few tests; All passpascal(0, 0) == 1pascal(1, 2) == 2pascal(0, 4) == 1pascal(1, 4) == 4pascal(2, 4) == 6However, an apparently identical implementation in Scala yields unexpected results, and I can't see why. I've even resulted to manual execution with pen and paper (haven't managed to get the IntelliJ debugger working yet).def pascal(c: Int, r: Int): Int = {  def loop(c: Int, r: Int): Int = {    if (c == 0) 1    else loop(c - 1, r) * ((r + 1 - c) / c)  }  if (c * 2 > r) loop(r - c, r)  else loop(c, r)}// Same tests; The last failspascal(0, 0) == 1pascal(1, 2) == 2pascal(0, 4) == 1pascal(1, 4) == 4pascal(2, 4) == 4 !!! <-- WHY NOT 6?!Any light that can be shed would be greatly appreciated. I've only just started digging into Scala, and have been quite pleasantly surprised so far. This has been the first unpleasant surprise. I feel sure it's just a gap in my early Scala knowledge and someone more experienced will spot the issue quickly. Thanks! -- You received this message because you are subscribed to the Google Groups "scala-user" group. To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email]. For more options, visit https://groups.google.com/d/optout.
Open this post in threaded view
|

Re: Bug in recursive implementation of Pascal's Triangle algorithm

 Hi WillIt boils down to this:In Scala, Int / Int = IntIn ECMAScript, the result of dividing is always a Double.Kind regardsBrianOn 12 January 2017 at 06:02, Will Clardy wrote:I'm working through the Functional Programming in Scala track on Coursera; one of the early exercises consists of writing a recursive algorithm to calculate an element in Pascal's Triangle for a given row and column. The function should have the following signature:pascal(c: Int, r: Int): IntI should say upfront that I'm not looking for help with the exercise. It was fairly easy to solve:def pascal(c: Int, r: Int): Int = {  if (c == 0 || c == r) 1  else pascal(c - 1, r - 1) + pascal(c, r - 1)}This is simple and works, but is inefficient. I uncovered a bug while working at a (less readable) more efficient implementation, and I'm at my wit's end trying to understand it. The revised algorithm is simple enough. Here's a working version in JavaScript (written to prove that the algorithm works, and to preserve my sanity):function pascal(c, r) {    function loop(c, r) {        return (c == 0) ? 1 : (loop(c - 1, r) * ((r + 1 - c) / c))    }    return (c * 2 > r) ? loop(r - c, r) : loop(c, r)}// A few tests; All passpascal(0, 0) == 1pascal(1, 2) == 2pascal(0, 4) == 1pascal(1, 4) == 4pascal(2, 4) == 6However, an apparently identical implementation in Scala yields unexpected results, and I can't see why. I've even resulted to manual execution with pen and paper (haven't managed to get the IntelliJ debugger working yet).def pascal(c: Int, r: Int): Int = {  def loop(c: Int, r: Int): Int = {    if (c == 0) 1    else loop(c - 1, r) * ((r + 1 - c) / c)  }  if (c * 2 > r) loop(r - c, r)  else loop(c, r)}// Same tests; The last failspascal(0, 0) == 1pascal(1, 2) == 2pascal(0, 4) == 1pascal(1, 4) == 4pascal(2, 4) == 4 !!! <-- WHY NOT 6?!Any light that can be shed would be greatly appreciated. I've only just started digging into Scala, and have been quite pleasantly surprised so far. This has been the first unpleasant surprise. I feel sure it's just a gap in my early Scala knowledge and someone more experienced will spot the issue quickly. Thanks! -- You received this message because you are subscribed to the Google Groups "scala-user" group. To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email]. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "scala-user" group. To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email]. For more options, visit https://groups.google.com/d/optout.