Pascal's Triangle Scala: Compute elements of Pascal's triangle using tail recursive approach

Question

In Pascal's Triangle the number at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. A sample Pascal's triangle would look like below.

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

I wrote a program that computes the elements of Pascal's triangle using below technique.

/**
* Can I make it tail recursive???
*
* @param c column
* @param r row
* @return 
*/
def pascalTriangle(c: Int, r: Int): Int = {
  if (c == 0 || (c == r)) 1
  else
    pascalTriangle(c-1, r-1) + pascalTriangle(c, r - 1)
}

So, for example if

i/p: pascalTriangle(0,2)  
o/p: 1.

i/p: pascalTriangle(1,3)  
o/p: 3.

Above program is correct and giving the correct output as expected. My question is, is it possible to write tail recursive version of above algorithm? How?

Emmerich

Yes, the same way you would write any tail-recursive function. You need your own in-heap stack of remaining operations, an an inner accumulator for keeping track of the result. – Ghee

Answer 1

Try

def pascalTriangle(c: Int, r: Int): Int = {
  @tailrec
  def loop(c0: Int, r0: Int, pred: Array[Int], cur: Array[Int]): Int = {
    cur(c0) = (if (c0 > 0) pred(c0 - 1) else 0) + (if (c0 < r0) pred(c0) else 0)

    if ((c0 == c) && (r0 == r)) cur(c0)
    else if (c0 < r0) loop(c0 + 1, r0, pred, cur)
    else loop(0, r0 + 1, cur, new Array(_length = r0 + 2))
  }

  if ((c == 0) && (r == 0)) 1
  else loop(0, 1, Array(1), Array(0, 0))
}

or

import scala.util.control.TailCalls._

def pascalTriangle(c: Int, r: Int): Int = {
  def hlp(c: Int, r: Int): TailRec[Int] =
    if (c == 0 || (c == r)) done(1)
    else for {
      x <- tailcall(hlp(c - 1, r - 1))
      y <- tailcall(hlp(c, r - 1))
    } yield (x + y)

  hlp(c, r).result
}

or

import cats.free.Trampoline
import cats.free.Trampoline.{defer, done}
import cats.instances.function._

def pascalTriangle(c: Int, r: Int): Int = {
  def hlp(c: Int, r: Int): Trampoline[Int] =
    if (c == 0 || (c == r)) done(1)
    else for {
      x <- defer(hlp(c - 1, r - 1))
      y <- defer(hlp(c, r - 1))
    } yield (x + y)

  hlp(c, r).run
}

http://eed3si9n.com/herding-cats/stackless-scala-with-free-monads.html

Despairing

any thoughts on the benefits of this seemingly complex recursive approach vs. iterative? – Subsidiary

@GeoffLangenderfer Which recursive approach are you talking about and which iterative one are you talking about? – Despairing

this example generates a whole row instead of one cell: leetcode.com/problems/pascals-triangle/discuss/38141/… – Subsidiary

@GeoffLangenderfer This is Java, not Scala. – Despairing

Answer 2

A couple optimizations to @DmytroMitin 's 1st solution:

1. Replace if ((c == 0) && (r == 0)) 1 with if (c == 0 || c == r) 1.
2. Take advantage of the symmetry in the triangle and use c's reflected value if it is greater than half of r.

With these optimizations, the number of calls to loop to draw a triangle with 30 rows is reduced from 122,760 to 112,375 (with #1) to 110,240 (with both #1 and #2) calls (without memoization).

  def pascalTail(c: Int, r: Int): Int = {
    val cOpt = if (c > r/2) r - c else c
    def loop(col: Int, row: Int, previous: Array[Int], current: Array[Int]): Int = {
      current(col) = (if (col > 0) previous(col - 1) else 0) + (if (col < row) previous(col) else 0)

      if ((col == cOpt) && (row == r)) current(col)
      else if (col < row) loop(col + 1, row, previous, current)
      else loop(0, row + 1, current, new Array(_length = row + 2))
    }

    if (c == 0 || c == r) 1
    else loop(0, 1, Array(1), new Array(_length = 2))
  }

Ellita

Answer 3

I was searching for a code to quickly comprehend the tail recursion logic for Pascal Triangle and stumbled upon this thread. However, thought of also having a readable solution which can shout out the logic clearly. Below is my draft attempted solution but can further be improved (for readability). From an optimization/performance standpoint it is taken care I guess.

def pascal(c: Int, r: Int): Int = {
  if(c > r) throw new RuntimeException

  def symmetricalGet(row: Array[Int]) = {
    val lastIndex = row.size - 1
    lastIndex match {
      case l if l >= c => row(c)
      case l => {
        val diffFromCenter = c - l
        val mirrorIdx = l - diffFromCenter
        row(mirrorIdx)
      }
    }
  }

  def computeRow(acc: Array[Int], isRowIdxOdd: Boolean): Array[Int] = {
    val cArray = 1 +: acc
      .sliding(2)
      .map(_.sum)
      .toArray

    isRowIdxOdd match {
      case true => cArray :+ cArray.last
      case _ => cArray
    }
  }

  @tailrec
  def goNextRow(row: Int, acc: Array[Int] = Array(1, 1)): Array[Int] = {
    val isOdd = row % 2 != 0
    if(row == r) computeRow(acc, isOdd)
    else goNextRow(row + 1, computeRow(acc, isOdd))
  }

  if(c == 0 || r <= 1 || c == r) 1
  else symmetricalGet(goNextRow(2))
}

Bathilda

Answer 4

This is a tail recursion solution. It is written in Scala Language.

Each pascal number(c, r), (c is column, r is row) is generated by two number (c-1, r-1) + (c, r-1). My solution is to save all the pascal numbers into a List, then calculate one number from the List in one function call. If the number is edge number then it is 1, otherwise push two upper row numbers into the list.

def pascal(c: Int, r: Int): Int =
  @tailrec
  def pascal_tail(sum: Int, numbers: List[(Int, Int)]): Int =
    numbers match
      // Every pascal number's final value is the sum of many 1
      case Nil => sum
      case head :: tail =>
        val (c, r) = head
        // If the number is edge number, its value is 1
        if c == 0 || c == r then pascal_tail(sum + 1, tail)
        // If it is not edge number, add two upper numbers into the list
        else pascal_tail(sum, (c-1, r-1)::(c, r-1)::tail)
  pascal_tail(0, List((c, r)))

Jagged