Limiting recursion depth in Scala
-
22-09-2019 - |
문제
Can you always structure a recursive function for tail-call elimination? If not, what are other strategies to limit the stack size?
For example: (inspired by 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
}
}
The goal is not to nit-pick this particular function, but to use it as a prop to learn techniques to limit stack-size.
UPDATE
My take-away from this is:
If the problem domain is such that recursion may hit limitation of stack-size:
Rewrite the code to be the scala-compiler-version-of-tailcall-optimizable. This can be aided/verified by the new (2.8) @scala.annotation.tailrec annotation.
If that is not feasible, rewrite it to use iterative looping constructs.
I'm also getting the sense that this rewriting (either case) is something that takes a certain amount of skill/talent/smarts/practice.
해결책
All recursive functions can be expressed as an iterative process, and all iterative processes can be expressed as tail-recursion, so yes, strictly speaking, you can transform any recursive algorithm into a tail-recursive one. However, don't don't assume that this will actually save you space. In many cases the record-keeping done by the stack is necessary, and you'll end up needing to essentially emulate the stack in your iterative or tail-recursive version. This can still be useful, say when you've got a small stack but a large heap.
다른 팁
You should accept Laurence Gonsalves answer, but, as for the code:
// 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
}
}
becomes
// 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)
}
All recursive functions can't expressed as a tail recursions, I think.
However you can express all recursive functions as iterative processes.
There are two cases to consider here. In the general case, are there some recursive functions that can't be expressed as tail calls? [UPDATE] As pointed out in another answer, there are not.
However, in the specific case of scala, there are some tail recursive functions that cannot be optimized to run in a tail recursive manner (meaning that they reuse stack frames.) This is mostly due to the limitations of the JVM I believe.
see previous question for more details about how this works.