Pascal's Triangle Scala：使用尾递归方法计算 Pascal 三角形的元素

Question

在帕斯卡三角中，三角形边上的数都是1，三角形内的每个数都是它上面两个数的和。示例 Pascal 的三角形如下所示。

我编写了一个程序，使用以下技术计算帕斯卡三角形的元素。

/**
* 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)
}

所以，例如如果

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

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

以上程序是正确的，并按预期给出了正确的输出。我的问题是，是否可以编写上述算法的尾递归版本？怎么样？

Answer 1

尝试

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))
}

或

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
}

或

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

Answer 2

对@DmytroMitin 的第一个解决方案进行了一些优化：

将if ((c == 0) && (r == 0)) 1替换为if (c == 0 || c == r) 1。
利用三角形的对称性，如果 c 大于 r 的一半，则使用 c 的反射值。

通过这些优化，调用 loop 以绘制具有 30 行的三角形的次数从 122,760 次减少到 112,375 次（#1）到 110,240 次（#1 和 #2）调用（没有记忆）。

  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))
  }

Answer 3

我正在寻找一个代码来快速理解 Pascal Triangle 的尾递归逻辑并偶然发现了这个线程。但是，想到还有一个可读的解决方案，可以清楚地说明逻辑。以下是我尝试的解决方案草案，但可以进一步改进（为了可读性）。从 optimization/performance 的角度来看，我猜这是小心的。

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))
}

Answer 4

这是一个尾递归解决方案。它是用 Scala 语言编写的。

每一个帕斯卡数(c, r), (c为列, r为行)由两个数(c-1, r-1) + (c, r-1)生成。我的解决方案是将所有帕斯卡数字保存到一个列表中，然后在一次函数调用中从列表中计算出一个数字。如果数字是边号则为1，否则将两个上面的行号推入列表。

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)))

Pascal's Triangle Scala：使用尾递归方法计算 Pascal 三角形的元素

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

algorithm

scala

recursion

tail-recursion