java.lang.StackOverflowError /// Pascal's triangle

Question

I'm trying to define a procedure which takes a column c and a row r, counting from 0 and returns the number at that spot in the triangle:

def pascal(c: Int, r: Int): Int = {
    if (c <= 0) 1
    else
        println(pascal(r, c-1) * (r-c)/c)
        pascal(r, c-1) * (r-c)/c
}

When I run my code:

>>>pascal(1,3) 

I have the following error:

pascal: (c: Int, r: Int)Int
java.lang.StackOverflowError

How can I fix that?

Thanks.

Answer 1

To get an element of the pascal triangle, you simply need to add the prev row's 2 elements.

The following code will do that correctly.

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

Answer 2

I don't think you should be calling pascal function again in your println, you should also use curly braces. I've rewritten it a little bit:

def pascal(c: Int, r: Int): Int = {
  var p = 1
  if (c > 0) {
    p = pascal(r, c-1) * (r-c)/c 
    println(p)
  }
  p
}

This prints for pascal(1,3):

-1
-2

---

UPDATE: I was curious to write a correct solution and this is what I ended up with:

  def fact(n: Int, r: Int=1): Int = if (n==0) r else fact(n-1, n*r)

  def pascal(c: Int, r: Int): Int = {
    fact(c) / (fact(r) * fact(c-r))
  }

  def main(a: Array[String]) { 
    println(pascal(3, 2))
  }

The only problem (that I know of) is the coordinates must be correct, with indices starting from 0. Anything out of bounds of the Pascal's triangle will cause a division by zero, this includes the OP's given example of pascal(1,3) - there's only two numbers on the row #1.

Answer 3

You could try this version that calculates binomial coefficients that are the same as entries of Pascal's triangle:

  def pascal(col: Int, row: Int): Int = {

    val l = if (col > row / 2) col else row - col
    @tailrec
    def go(i: Int, acc: Int): Int = {
      if (i == l + 1) acc
      else go(i + 1, acc * (row - l + i) / i)
    }
    return go(1, 1);
  }

This solution uses tail recursion, so StackOverflowError is not a threat here.

Answer 4

Your Pascal's triangle algorithm is incorrect, but maybe you haven't finished it yet, so I'm not going to tell you how to write a correct algorithm, just how to stop the stack overflow.

EDIT: maksimov is right that by forgetting to wrap your else sequence in braces, you are only making the first expression conditional, which means that the second expression is always evaluated and loops infinitely into stack overflow. Adding the braces, however, will only change a 100% probability of stack overflow into a possibility of a stack overflow, because the calls to your pascal function are not in tail position. To remove the risk of stack overflow, you have to make further modifications, explained below...

Recursive functions can avoid stack overflows by using tail recursion. However, for that to work, the recursive call has to be in tail position. That is, the recursive call must be the final expression to be executed before the function returns and its value must be returned without modification, all the way back up the stack to the first invocation. Since your calculation uses pascal(r, c-1) * (r-c)/c, you are always modifying the returned value before returning that modified result, so the call is not in tail position. You need to modify your function so that when it finally returns it gives the correct result with no need for modification. The end result should have this basic shape...

def pascal(c: Int, r: Int): Int = {
  ...
  if (c <= 0) 1 else pascal(..., ...)
}

You will find that the only way to do this is to define a local function inside your pascal function and have that do the recursion....

def pascal(c: Int, r: Int): Int = {
  def loop(...): Int = ... match {
    case ... => 1
    case ... => x + y
    case ... => loop(...)
    case _ => loop(...)
  }
  ...
  if (c <= 0) 1 else loop(...)
}

This is because the recursive function will have to check state to find out whether it has solved the final problem or a sub-task within the problem. The state can be extra parameters passed to loop or local vars defined at the top level of pascal

Only once you have safely moved the recursion into the local function can you safely do what maksimov suggested

var p = if (c <= 0) 1 loop(...)
println(p)
p

You can do this safely because the recursive calls all happen inside loop and are all (if you use my template) in tail position.

To be clear: having two successive calls to your pascal function is not the cause of the overflow. The two top-level calls in your code are sequential and do not interfere with each other; if one completes, so will the other. If the first fails, the second one would also have failed (and removing the first one will not stop the second one from failing).

Answer 5

Here an example of the whole code:

object Main {

  def main(args: Array[String]) {
  println("Pascal's Triangle")

 for (row <- 0 to 10) {
  for (col <- 0 to row)
    print(pascal(col, row) + " ")

    println()
  }
 }


def pascal(c: Int, r: Int): Int = {
 if ( c <= 0 || c == r ){
    return 1
  }

  return pascal(c, r - 1) + pascal(c - 1, r -1)
}

}

Answer 6

Pure Functional Programming

def printPascalsTriangle(n: Int): Unit ={

    // n=1 print 1
    // n=2 print 1 1
    // n=3 print 1 2 1   List(prev(0),prev(0+1),prev(1))
    // n=4 print 1 3 3 1 List(prev.head,prev(0+1),prev(1+2),prev.reverse.head)

    def combine(oldList: List[Int], newList: List[Int]) = List(oldList.head) ::: newList ::: List(oldList.reverse.head)

    def g(prevList:List[Int],v:Int) = List(prevList(v-1), prevList(v))

    def pascalLine(prevList: List[Int], n: Int): List[Int] =
    {
      if(n>0)
      prevList match {
        case Nil => {println(List(1));pascalLine(List(1),n-1)}
        case List(1) => {println(List(1,1));pascalLine(List(1,1),n-1)}
        case _ => {
          val newList=combine(prevList,(1 to prevList.length-1).map(x => g(prevList,x)).map(y=>y.sum).toList)
          println(newList)
          pascalLine(newList,n-1)
        }

      }
      else
        Nil
    }
    pascalLine(Nil,n)
}