Limiting recursion depth in Scala
recursion, scala, tail-recursion
Solution
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.
Problem
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.