Является ли эта реализация глубины поиска в первую очередь рекурсивной сейчас? - PullRequest
Новая
       65

Является ли эта реализация глубины поиска в первую очередь рекурсивной сейчас?

0 голосов
/ 26 марта 2019

У меня была эта функция для функционального обхода графа: 

private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
    current.edges.foldLeft(acc) {
      (results, next) =>
        if (results.contains(rCellsMovedWithEdges(next))) results
        else dfs(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
    } :+ current
  }

Реализация взята из Мануэля Кисслинга здесь

Это довольно мило, но я волнуюсь, что ": current" в конце делает его не хвостовым рекурсивом.

Я изменил это на: 

private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell]): Vector[RCell] = {

    @annotation.tailrec
    def go(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
      current.edges.foldLeft(acc) {
        (results, next) =>
          if (results.contains(rCellsMovedWithEdges(next))) results
          else go(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
      }
    }
    go(current, rCellsMovedWithEdges) :+ current
  }

но компилятор говорит, что рекурсивный вызов не находится в хвостовой позиции.

Есть ли у левого хвоста рекурсивный хвост за шанс?

Если нет, есть ли другой способ сделать то, что я хочу?

Ответы [ 2 ]

4 голосов
/ 26 марта 2019

Это не хвостовая рекурсия, потому что последний вызов не go, а foldLeft. Нет никакого способа, которым он может быть даже взаимно рекурсивным, так как foldLeft вызывает go несколько раз. Трудно сделать хвостовую часть DFS рекурсивной, поскольку рекурсивный алгоритм в значительной степени опирается на стек вызовов для отслеживания вашей позиции в дереве. Я бы посоветовал не беспокоить, если вы можете гарантировать, что ваше дерево мелкое. В противном случае вам нужно будет обойтись без явного стека (List - хороший выбор здесь) и полностью переписать ваш код.

2 голосов
/ 26 марта 2019

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

def dfs(start: RCell, rCellsMovedWithEdges: Vector[RCell]): Vector[RCell] = {
  @annotation.tailrec
  def go(stack: List[RCell], visited: Set[RCell], acc: Vector[RCell]): Vector[RCell] = stack match {
    case Nil => acc
    case head :: rest => {
      if (visited.contains(head)) {
        go(rest, visited, acc)
      } else {
        val expanded = head.edges.map(rCellsMovedWithEdges)
        val unvisited = expanded.filterNot(visited.contains)
        go(unvisited ++ rest, visited + head, acc :+ head)
      }
    }
  }
  go(List(start), Set.empty, Vector.empty)
}

Бонус: измените unvisited ++ rest на rest ++ unvisited и вы получите BFS.

...