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 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.

Rewritting recursion just takes practice. At first it is very hard, but as you get used to the technique, it becomes progressively more straight-forward, if not necessarily easy. Sometimes, it just isn't worth the effort -- another thing that you'll get an eye for with practice. — Daniel C. Sobral, Oct 21 '09 at 13:12

score 9 · Accepted Answer · answered Oct 20 '09 at 17:38

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.

score 4 · Answer 2 · edited May 23 '17 at 12:01

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

To be clear *Daniel* - are you pointing out how the OP should re-write his method for it to be tail-recursive, or you are suggesting that the `scalac` compiler will perform this optimization for him? — oxbow_lakes, Oct 20 '09 at 18:48
The Scala compiler can't do this sort of optimization, because the result may not always have the same semantics as the original (due to side-effects). It works fine in this case, but not necessarily in general. — Daniel Spiewak, Oct 20 '09 at 22:42
To be clear, it is an example of how to rewrite it to be tail-recursive. Note that the recursion stack became explicit in the candidates variable, as passed through each recurse invokation. On the other hand, since the function is local (in fact, a closure), I treat labyrinth and goal as "globals", and avoid repeating them on the stack. — Daniel C. Sobral, Oct 21 '09 at 13:09

score 1 · Answer 3 · answered Oct 20 '09 at 17:21

1

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

However you can express all recursive functions as iterative processes.

answered Oct 20 '09 at 17:21

Juha Syrjälä

33,425
31
131
183

score 1 · Answer 4 · edited May 23 '17 at 12:19

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.

Limiting recursion depth in Scala

4 Answers4