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

Question

在Pascal三角形中，三角形边缘的数字均为1，三角形内部的每个数字均为其上方两个数字的和。 Pascal的三角形示例如下所示。

    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.

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

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