Преобразование нормальной рекурсии в хвостовую рекурсию

Ответ 1

В случаях, когда есть простая модификация значения рекурсивного вызова, эту операцию можно перенести в начало рекурсивной функции. Классическим примером этого является рекурсия хвоста по модулю минусов, где простая рекурсивная функция в этой форме:

def recur[A](...):List[A] = {
  ...
  x :: recur(...)
}

который не является хвостовым рекурсивным, преобразуется в

def recur[A]{...): List[A] = {
   def consRecur(..., consA: A): List[A] = {
     consA :: ...
     ...
     consrecur(..., ...)
   }
   ...
   consrecur(...,...)
}

Пример Alexlv - это вариант этого.

Это такая хорошо известная ситуация, что некоторые компиляторы (я знаю примеры Prolog и Scheme, но Scalac этого не делает) могут обнаруживать простые случаи и автоматически выполнять эту оптимизацию.

Проблемы, связанные с несколькими вызовами с рекурсивными функциями, не имеют такого простого решения. Оптимизатор TMRC бесполезен, так как вы просто перемещаете первый рекурсивный вызов на другую позицию без хвоста. Единственный способ достичь рекурсивного решения - удалить все, кроме одного из рекурсивных вызовов; как это сделать полностью зависит от контекста, но требует поиска совершенно другого подхода к решению проблемы.

Как это бывает, в некотором роде ваш пример похож на классическую проблему последовательности Фибонаси; в этом случае наивное, но элегантное двухрекурсивное решение может быть заменено на одно, которое переместится вперед от 0-го числа.

def fib (n: Long): Long = n match {
  case 0 | 1 => n
  case _ => fib( n - 2) + fib( n - 1 )
}

def fib (n: Long): Long = {
  def loop(current: Long, next: => Long, iteration: Long): Long = {
    if (n == iteration) 
      current
    else
      loop(next, current + next, iteration + 1)
  }
  loop(0, 1, 0)
}

Для последовательности Fibonnaci это наиболее эффективный подход (решение на основе потоков - это просто другое выражение этого решения, которое может кэшировать результаты для последующих вызовов). Теперь, вы также можете решить свою проблему, перейдя по ссылке c0/r0 (ну, c0/r2) и вычислив каждую строку в последовательности - разница в том, что вам нужно кэшировать всю предыдущую строку. Таким образом, хотя это имеет сходство с fib, оно резко отличается по специфике и также значительно менее эффективно, чем ваше оригинальное, дважды рекурсивное решение.

Здесь приведен пример вашего примера треугольника pascal, который может эффективно вычислять pascal(30,60):

def pascal(column: Long, row: Long):Long = {
  type Point = (Long, Long)
  type Points = List[Point]
  type Triangle = Map[Point,Long]
  def above(p: Point) = (p._1, p._2 - 1)
  def aboveLeft(p: Point) = (p._1 - 1, p._2 - 1)
  def find(ps: Points, t: Triangle): Long = ps match {
    // Found the ultimate goal
    case (p :: Nil) if t contains p => t(p)
    // Found an intermediate point: pop the stack and carry on
    case (p :: rest) if t contains p => find(rest, t)
    // Hit a triangle edge, add it to the triangle
    case ((c, r) :: _) if (c == 0) || (c == r) => find(ps, t + ((c,r) -> 1))
    // Triangle contains (c - 1, r - 1)...
    case (p :: _) if t contains aboveLeft(p) => if (t contains above(p))
        // And it contains (c, r - 1)!  Add to the triangle
        find(ps, t + (p -> (t(aboveLeft(p)) + t(above(p)))))
      else
        // Does not contain(c, r -1).  So find that
        find(above(p) :: ps, t)
    // If we get here, we don't have (c - 1, r - 1).  Find that.
    case (p :: _) => find(aboveLeft(p) :: ps, t)
  }
  require(column >= 0 && row >= 0 && column <= row)
  (column, row) match {
    case (c, r) if (c == 0) || (c == r) => 1
    case p => find(List(p), Map())
  }
}

Это эффективно, но я думаю, что это показывает, насколько уродливыми сложными рекурсивными решениями могут стать, когда вы деформируете их, чтобы стать хвостом рекурсивным. На данный момент, возможно, стоит перейти к другой модели целиком. Continuations или монадическая гимнастика может быть лучше.

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

Ответ 2

Я не знаю, насколько теоретичен этот вопрос, но рекурсивная реализация не будет эффективной даже с хвостовой рекурсией. Например, попробуйте вычислить pascal(30, 60). Я не думаю, что вы получите переполнение стека, но будьте готовы сделать длинный перерыв на кофе.

Вместо этого рассмотрите возможность использования Stream или memoization:

val pascal: Stream[Stream[Long]] = 
  (Stream(1L) 
    #:: (Stream from 1 map { i => 
      // compute row i
      (1L 
        #:: (pascal(i-1) // take the previous row
               sliding 2 // and add adjacent values pairwise
               collect { case Stream(a,b) => a + b }).toStream 
        ++ Stream(1L))
    }))

Ответ 3

Да, это возможно. Обычно это делается с помощью шаблона аккумулятора через некоторую внутренне определенную функцию, которая имеет один дополнительный аргумент с так называемой логикой аккумулятора, пример с подсчетом длины списка.

Например, нормальная рекурсивная версия будет выглядеть так:

def length[A](xs: List[A]): Int = if (xs.isEmpty) 0 else 1 + length(xs.tail)

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

def length[A](xs: List[A]) = {
  def inner(ys: List[A], acc: Int): Int = {
    if (ys.isEmpty) acc else inner(ys.tail, acc + 1)
  }
  inner(xs, 0)
}

немного дольше кода, но я думаю, что идея я поняла. Из-за этого вы можете сделать это без внутренней функции, но в таком случае вы должны указать начальное значение acc вручную.

Ответ 4

Я уверен, что это возможно не, так как вы ищете общий случай, но это будет зависеть от того, насколько тщательно вы разрешаете изменения.

Рекурсивная функция хвоста должна быть перезаписана как цикл while, но попробуйте реализовать, например, фрактальное дерево, используя while-loop, Это возможно, но вам нужно использовать массив или коллекцию для хранения состояния для каждой точки, которая сулит для данных, которые иначе хранятся в стеке вызовов.

Также можно использовать trampolining.

Ответ 5

Это действительно возможно. То, как я это сделаю, - это начните с списка (1) и продолжайте рекурсию, пока не дойдете до вы хотите. Стоит заметить, что вы можете его оптимизировать: если c == 0 или c == r, это значение равно единице, и для вычисления let say столбец 3 из 100-й строки вам нужно всего лишь вычислить первые три элемента предыдущих строк. Рекурсивное решение для работы хвоста будет следующим:

def pascal(c: Int, r: Int): Int = {
  @tailrec
  def pascalAcc(c: Int, r: Int, acc: List[Int]): List[Int] = {
    if (r == 0) acc
    else pascalAcc(c, r - 1,
    // from let say 1 3 3 1 builds 0 1 3 3 1 0 , takes only the
    // subset that matters (if asking for col c, no cols after c are
    // used) and uses sliding to build (0 1) (1 3) (3 3) etc.
      (0 +: acc :+ 0).take(c + 2)
         .sliding(2, 1).map { x => x.reduce(_ + _) }.toList)
  }
  if (c == 0 || c == r) 1
  else pascalAcc(c, r, List(1))(c)
}

Аннотация @tailrec фактически позволяет компилятору проверить функцию на самом деле является хвостом рекурсивным. Вероятно, его можно было бы оптимизировать, поскольку с учетом того, что строки симметричны, если c > r/2, pascal (c, r) == pascal (r-c, r).. но оставлен читателю;)

Ответ 6

Подход аккумулятора

  def pascal(c: Int, r: Int): Int = {

    def pascalAcc(acc:Int, leftover: List[(Int, Int)]):Int = {
      if (leftover.isEmpty) acc
      else {
        val (c1, r1) = leftover.head
        // Edge.
        if (c1 == 0 || c1 == r1) pascalAcc(acc + 1, leftover.tail)
        // Safe checks.
        else if (c1 < 0 || r1 < 0 || c1 > r1) pascalAcc(acc, leftover.tail)
        // Add 2 other points to accumulator.
        else pascalAcc(acc, (c1 , r1 - 1) :: ((c1 - 1, r1 - 1) :: leftover.tail ))
      }
    }

    pascalAcc(0, List ((c,r) ))
  }

Он не переполняет стек, а как на большой строке и столбце, но Аарон упомянул об этом не быстро.