Скала треугольника Паскаля: Вычислить элементы треугольника Паскаля, используя хвостовой рекурсивный подход - PullRequest
Новая
       5

Скала треугольника Паскаля: Вычислить элементы треугольника Паскаля, используя хвостовой рекурсивный подход

0 голосов
/ 16 октября 2019

В Треугольнике Паскаля все числа на краю треугольника равны 1, и каждое число внутри треугольника является суммой двух чисел над ним. Пример треугольника Паскаля будет выглядеть следующим образом. 

    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.

Вышеуказанная программа верна и дает правильный результат, как и ожидалось. У меня вопрос, можно ли написать хвостовую рекурсивную версию вышеупомянутого алгоритма? Как?

1 Ответ

1 голос
/ 16 октября 2019

Попробуйте 

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

...