在Scala中限制递归深度

Question

您是否总能构造一个用于tail-call消除的递归函数？如果不是，还有什么其他策略来限制堆栈大小？

例如： （由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可优化的。这可以通过新的（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) 
}