Limiting recursion depth in Scala

Question

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 http://stackoverflow.com/questions/1595427/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.

Answer 1

All recursive functions can't expressed as a tail recursions, I think.

However you can express all recursive functions as iterative processes.

Answer 2

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.

Answer 3

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.

Answer 4

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)
}