tail recursion fails (possibly because of implicit cons conversion)

Question

I have what I believe to be a fairly simple tail-recursive function. However, @tailrec tells me otherwise.

  @tailrec
  def _next(continue : String, current : List[Long], first : Boolean ) : Stream[Long]  = {
    current match {
      case head :: tail => head #:: _next(continue, tail, false) //this line breaks tailrec
      case Nil if first => empty
      case _ => {
        val (nc, nl) = getIds(continue)
        _next(nc, nl, true)
      }
    }
  }

which presents me with

[error] could not optimize @tailrec annotated method _next: it contains a recursive call not in tail position
[error]  case head :: tail => head #:: _next(continue, tail, false)
[error]                                     ^

it probably has to do with the implicit notification I receive from eclipse: - Implicit conversions found: _next(continue, tail, false) => consWrapper(_next(continue, tail, false)), but unfortunately, that isn't helping me resolve the issue.

How can I fix this, and, for brownie points, where did I go wrong thinking this would tail-recurse?

you last operation is **appending**, not `_next` call -- use recursive accumulator — om-nom-nom, Apr 18 '13 at 15:14

axel22 · Accepted Answer · 2013-04-18T15:24:18.417

The problem is that the last operation in your code is not the call to _next, but the Stream cons operation #::.

One solution is to use a StreamBuilder to build your stream and keep this StreamBuilder as an accumulator variable.

  @tailrec
  def _next(continue : String, current : List[Long], first : Boolean, acc: Stream.StreamBuilder[Long]) : Stream[Long]  = {
    current match {
      case head :: tail =>
        acc += head
        _next(continue, tail, false, acc)
      case Nil if first => acc.result
      case _ => {
        val (nc, nl) = getIds(continue)
        _next(nc, nl, true, acc)
      }
    }
  }

This is not particularly efficient - the StreamBuilder is more appropriate if you add entire collections to it using the ++= instead of +=. For this reason, consider changing your code to something like this:

  @tailrec
  def _next(continue : String, current : List[Long], first : Boolean, acc: Stream.StreamBuilder[Long]) : Stream[Long]  = {
    current match {
      case Nil =>
        acc.result
      case list =>
        acc += list
        val (nc, nl) = getIds(continue)
        _next(nc, nl, true, acc)
    }
  }

finding this answer: http://stackoverflow.com/questions/10525449/tail-recursive-bounded-stream-of-pairs-of-integers-scala it seems that though it is not tail recursive, that is perfectly alright. Is it? Will this not run out of stack space for large sets? — Martijn, Apr 18 '13 at 15:29
they will be: I estimate tens of thousands of items. Could you explain what the difference between my situation and the one in the linked answer is? — Martijn, Apr 18 '13 at 15:32

tail recursion fails (possibly because of implicit cons conversion)

1 Answers1