CODEWITHSUNDEEP
scalarecursion
Tinku
Tinku

Reputation: 1608

Why this function is not tail recursive?

I have wrtten the following function for pascal triangle. Why the call 

pascal_cont(a-1, b-1, (x:Int) => pascal_cont(a, b-1, (y:Int) => cont(x + y)))

is not tail recursive ? 

def pascal(c: Int, r: Int): Int = {
  def pascal_cont(a:Int, b:Int, cont: (Int) => Int): Int = {
    if (a==0 || a==b) cont(1)
    else pascal_cont(a-1, b-1, (x:Int) => pascal_cont(a, b-1, (y:Int) => cont(x + y)))        
  }

  pascal_cont(c,r,n => n)  
}

Upvotes: 1

Views: 206

Answers (2)

gzm0
gzm0

Reputation: 14842

The Scala compiler cannot optimize any (theoretically) tail-recursive function, as it translates them to a while-loop. It for example also is unable to optimize mutually tail-recursive functions. You can use the trampoline pattern to mitigate this.

In Scala, scala.util.control.TailCalls contains the necessary utilities. This will turn into:

def pascal(c: Int, r: Int): Int = {
  import scala.util.control.TailCalls._

  def pascal_cont(a:Int, b:Int, cont: (Int) => TailRec[Int]): TailRec[Int] = {
    if (a==0 || a==b) cont(1)
    else tailcall {
      pascal_cont(a-1, b-1, (x:Int) =>
        pascal_cont(a, b-1, (y:Int) => cont(x + y)))
    }
  }

  pascal_cont(c,r,n => done(n)).result
}

Upvotes: 4

Marius Danila
Marius Danila

Reputation: 10411

If you add the @tailrec annotation on the pascal_cont function you'll get the following error:

[error] ....scala:18: could not optimize @tailrec annotated method pascal_cont: it contains a recursive call not in tail position
[error]         pascal_cont(a-1, b-1, (x:Int) => pascal_cont(a, b-1, (y:Int)=> cont (x + y)))
[error]                                                     ^
[error] one error found

So the call inside the lambda expression is not in tail position, and that's why it's not tail recursive

Upvotes: 4

Related Questions