Предельная глубина рекурсии в Scala

Question

Можете ли вы всегда структурировать рекурсивную функцию для устранения хвостового вызова? Если нет, то каковы другие стратегии для ограничения размера стека?

Например: (вдохновленный Break or shortcircuit a fold in Scala)

// Depth-first search of labyrinth, with large depth > stacklimit 
def search (labyrinth: SearchDomain, 
      path: List[SolutionNode], 
      goal: DesiredResult) = { 

    if (path.head == goal) return path 

    candidates: List[SolutionNode] = labyrinth.childNodes(path) 

    candidates.find { c => 
    Nil != search(labyrinth, c :: path, goal) // potential boom! 
    } match { 
    case Some(c) => c :: path 
    case None => Nil 
    } 
} 

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

---

UPDATE

Мой вынос из этого:

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

Перепишите код для быть scala-компилятор-версия-tailcall-optimizable. Это может быть подтверждено/подтверждено новой аннотацией (2.8) @ scala.annotation.tailrec.

Если это невозможно, перепишите его для использования итерационных циклов.

У меня также есть смысл, что это переписывание (в любом случае) - это то, что требует определенного уровня умения/таланта/умений/практики.

Answer 1

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

Answer 2

Все рекурсивные функции не могут быть выражены как хвостовые рекурсии, я думаю.

Однако вы можете выразить все рекурсивные функции как итеративные процессы.

Answer 3

Здесь рассмотрены два случая. В общем случае существуют ли некоторые рекурсивные функции, которые не могут быть выражены в виде хвостовых вызовов? [ОБНОВЛЕНИЕ] Как указано в другом ответе, нет.

Однако в конкретном случае Скале, есть некоторые хвосты рекурсивных функции, которые не могут быть оптимизированы для работы в хвостовом рекурсивном способе (что означает, что они повторно использовать кадры стека.) Это в основном из-за ограничения, из JVM Я верю.

см. Предыдущий question для получения более подробной информации о том, как это работает.

Answer 4

Вы должны принять Laurence Gonsalves ответ, но, как по коду:

// Depth-first search of labyrinth, with large depth > stacklimit 
def search (labyrinth: SearchDomain, 
      path: List[SolutionNode], 
      goal: DesiredResult) = { 
    if (path.head == goal) return path 

    candidates: List[SolutionNode] = labyrinth.childNodes(path) 

    candidates.find { c => 
    Nil != search(labyrinth, c :: path, goal) // potential boom! 
    } match { 
    case Some(c) => c :: path 
    case None => Nil 
    } 
} 

становится

// Depth-first search of labyrinth 
def search (labyrinth: SearchDomain, 
      path: List[SolutionNode], 
      goal: DesiredResult) = { 
    def recurse(candidates: List[List[SolutionNode]], 
       path: List[SolutionNode]) = candidates match { 
    case List(Nil) => Nil 
    case Nil :: tail => recurse(tail, path.tail) 
    case (nextCandidate :: otherCandidates) :: tail => 
     if (nextCandidate == goal) 
     nextCandidate :: path 
     else 
     recurse(labyrinth.childNodes(nextCandidate :: path) :: otherCandidates, 
       nextCandidate :: path) 
    } 

    if (path.head == goal) 
    path 
    else 
    recurse(labyrinth.childNodes(path), path) 
}