Tail recursion and return statement in Scala

Question

I was thinking about one of the questions asked here (Why does Scala require a return type for recursive functions?) and how to improve the code.

Anyway, I was thinking something like this:

def simpledb_update(name: String, metadata: Map[String, String]) = {

  def inner_update(attempt: int): Unit = {
    try {
      db(config("simpledb_db")) += (name, metadata)
      return
    } catch {
      case e =>
        if (attempt >= 6) {
          AUlog(name + ": SimpleDB Failed")
          return
        }
    }
    inner_update(attempt+1)
  }

    inner_update(0)
}

Or

def simpledb_update(name: String, metadata: Map[String, String]) {

  def inner_update(attempt: int): Unit = {
    try {
      db(config("simpledb_db")) += (name, metadata)
    } catch {
      //Do I need the pattern match, since I don't
      // care what exception is thrown???
      if (attempt >= 6) {
        AUlog(name + ": SimpleDB Failed")
      } else {
        inner_update(attempt+1)
      }
    }
  }

  inner_update(0)
}

Is the second implementation still tail recursive (is the first???). I'm still a bit hazy on when a function is tail recursive, and when it's not.

score 3 · Accepted Answer · answered Mar 15 '11 at 14:24

3

Yes, both examples are still tail-recursive, you're doing the checking/processing first, with the recursive call last.

The Jargon File put it succinctly: Tail Recursion (n): If you aren't sick of it already, see tail recursion.

answered Mar 15 '11 at 14:24

PaulRein

148
1
6

1

I just read an answer to another SO question (http://stackoverflow.com/questions/3678569/how-to-recognize-what-is-and-what-is-not-tail-recursion) which said pretty much the same thing. Thanks – GKelly Mar 15 '11 at 14:27

score 2 · Answer 2 · answered Mar 16 '11 at 05:16

2

In Scala, you can add tailrecursive annotation to the function, and then the compiler will check whether or not it can do tail call optimisation on the function.

answered Mar 16 '11 at 05:16

Timo Rantalaiho

21
1

1

`@tailrec` is the annotation. – Nicolas Payette Mar 16 '11 at 21:37

score 0 · Answer 3 · answered Apr 25 '13 at 00:44

0

Tail recursion is simple to understand - if the last expression, from all code paths of a function F, is simply a function call then it is tail recursive. But is it tail-recursive for Scala compiler to optimize - depends. The fact that JVM doesn't do TCO means scala compiler does the magic.

And the reason scalac might fail to optimize has to do with polymorphism. If the Function can be overridden in a subclass, scalac cannot optimize it out.

@Timo Rantalaiho, using the tailrec annotation is the safest way to verify if TCO can be done.

answered Apr 25 '13 at 00:44

Ustaman Sangat

1,505
1
14
26

Also while I think functional programming is great, it does seem that while the code looks nice and declarative (in Scala, a novice developer sadly has all the liberty to do imperative stuff), one has to actually know a lot more and maybe worry about performance, case in point stackoverflow. See my rant at http://tshrestha.blogspot.com/2013/04/scala-and-price-of-not-being-purely.html – Ustaman Sangat Apr 25 '13 at 00:46

Tail recursion and return statement in Scala

3 Answers3