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

Question

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

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

/**
* 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.

上述程序是正确的，并按预期给出了正确的输出。我的问题是，是否有可能编写上述算法的尾递归版本？如何实现？

- Madstuffs

---

是的，你可以像编写任何尾递归函数一样编写它。你需要自己在堆中创建一个剩余操作的栈，并使用内部累加器来跟踪结果。 - Luis Miguel Mejía Suárez

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

- Dmytro Mitin

---

这种看似复杂的递归方法相较于迭代方法有哪些好处？ - Geoff Langenderfer

@GeoffLangenderfer，您在谈论哪种递归方法和哪种迭代方法？ - Dmytro Mitin

这个例子生成了整行而不是一个单元格：https://leetcode.com/problems/pascals-triangle/discuss/38141/My-concise-solution-in-Java - Geoff Langenderfer

@GeoffLangenderfer 这是Java，不是Scala。 - Dmytro Mitin

Answer 2

我正在寻找一段代码，以便快速理解帕斯卡三角形的尾递归逻辑，并偶然发现了这个线程。然而，我想要一个易于阅读的解决方案，可以清晰地展示逻辑。以下是我尝试的草稿解决方案，但可以进一步改进（以提高可读性）。从优化/性能的角度来看，我想已经处理好了。

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

- Sundar Rajan Muthuraj

Answer 3

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

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

通过这些优化，绘制30行三角形时调用loop的次数从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))
  }

- davejlin

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

- PokerFace