Оптимизация простых функций, содержащих циклы или рекурсию

Question

Я работаю над проблемой в codewars , и мой код заработал, но время истекло. Я пробовал как рекурсию, так и циклы, но и время ожидания, и вычисление за одинаковое количество времени в простых тестах Я не знаю, как и дальше оптимизировать в пределах моей начинающей способности.

Рекурсия:

def recursive(p: Int, n: Int, l: List[Int], x: List[Int]): List[Int] = {
  if (n == p)
    x
  else
    recursive(p, n + 1, l, (l.drop(p - n - 1).sum :: x))
}

def partsSums(l: List[Int]): List[Int] = {
  val a = l.length
  recursive(a, 0, l, List(0))
}

L oop:

def partsSums(l: List[Int]): List[Int] = {
  val g = l.length
  var x = List(0)
  var n = 0
  while (n != g) {
    x = (l.drop(g - n - 1).sum) :: x
    n += 1
  }
  x
}

Answer 1

Причиной истечения времени ожидания двух функций является сложность их времени O (n ^ 2). На самом деле нужен только O (n). Вот простое решение:

l.scanRight(0)(_ + _)

Если вы предпочитаете решение с хвостовой рекурсией, оно должно работать:

def rcumsum(xs: List[Int]): List[Int] = {
   def imp(ys: List[Int], cum: List[Int], acc: Int): List[Int] = ys match {
     case Nil   => cum
     case y::rs => imp(rs, (y+acc)::cum, y+acc)
   }
   imp(xs.reverse, List(0), 0)
 }

Answer 2

Вы можете использовать аннотацию @tailrec, чтобы дать компилятору scala некоторую дополнительную информацию о рекурсивной функции. Это позволит провести дополнительную внутреннюю оптимизацию и «развернуть» стек вызовов функций:

@tailrec
def recursive(p: Int, n: Int, l: List[Int], x: List[Int]): List[Int] = {