# Pascal triangle algorithm is good but fails

I have created a function which returns the number that corresponds to the given row and column from the pascal triangle. I have used the formula for this:

n! / r! * (r-n)!

The code:

def pascal(c: Int, r: Int): Int = {

def factorial(number: Int): Int = {

def loop(adder: Int, num: Int): Int = {
else loop(adder * num, num - 1)

}

loop(1,number)
}

factorial(r) / (factorial(c) * factorial(r-c));
}


I received 180 points out of 190 for this function because it returns an arithmetic exception for a given case (they don't give me the case). How could I improve this code and how can I make it better? Most importantly, how can I spot the bug?

-
I'm voting against closure cause his code is working(one small case not), and asking for improvement. (also how to spot the bug but not asking to fix the bug). –  chillworld May 9 at 5:12

The code appears to be correct, though the explanatory formula you posted is wrong.

Your factorial function is more complex than it needs to be. Furthermore, adder is a poor variable name, since the result is multiplicative rather than additive. The traditional recursive definition is:

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


The main problem with your approach is that you work with large numbers in both the numerator and the denominator. If your program is generally working, then your problem is probably arithmetic overflow. An Int would only handle values up to 231 - 1 correctly.

Therefore, your best bet is to use an entirely different way to construct Pascal's Triangle, as suggested by @janos.

-
you are right. If I insert large numbers division by 0 occurs. Now implementing a whole new algorithm I guess would do the trick. However couldn't I just work with long? and then return an int? –  Bula May 9 at 15:08
OP's factorial version has an advantage of being a little bit faster (it's tail-recursive ) –  sasha.sochka May 29 at 14:49

There is a simpler solution. Consider this logic:

• if it's the first column, the value is always 1
• if it's the last column, the value is always 1. (You can check this based on the row!)
• otherwise, it's the sum of the value in the previous row previous column + previous row same column

def pascal(c: Int, r: Int): Int = { require(!(c < 0 || r < 0 || c > r), "c, r must be both positive and c <= r") if (c == 0) 1 else if (c == r) 1 else pascal(c - 1, r - 1) + pascal(c, r - 1) }
Idiomatically instead of if (c < 0 || r < 0 || c > r) throw new IllegalArgumentException("invalid args: " + c + " " + r) you should write require(c >= 0 && r>= 7 && c <= r) –  sasha.sochka May 29 at 14:50