Tail-Recursive Function (Coursera Issues)

2
votes

I'm following a Coursera course for functional programming in Scala so that I can learn the language.

They introduced the concept of tail-recursive functions and defined them basically as a function that ends in a call to itself. But then they show this as the worked example:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  }
  loop(a, 0)
}

If I annotate sum with @tailrec, I get an error because the IDE (IntelliJ) does not consider it to be tail recursive.

Is sum called tail-recursive here, or is the inner implementation "loop" the thing that is considered to be tail recursive in this case?

2
scalasyntaxtail-recursionhigher-order-functions

2 Answers

2
votes

You're right. sum needs to call itself otherwise Scala will complain with: 

@tailrec annotated method contains no recursive calls

If you tell compiler where exactly it is, by moving the @tailrec to where the tail recursion is:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  @tailrec def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  }
  loop(a, 0)
}

Then the compiler'll be satisfied it is tail-recursion optimised.

1
votes

The inner loop method is tail-recursive, the sum method is not recursive at all. Therefore, you should annotate loop with @tailrec.

Moving loop to the outer scope may help visualize what's going on:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
    loop(a, 0)
}

def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
}

As you can see, sum is merely a public entry point for loop.

(Note that the code above won't compile because loop does not close over b or f anymore, but you get the point.)