Tail recursion - Scala (any language else)

Question

i have a question about Tail recursion. As i know Tail recursion is when the last recursive call from function will deliver the result of the function. But when i have a function like this

def func1(n: Int): Int = {
   if (n > 100) {
      n - 10
   }
   else {
      func1(func1(n + 11))
   }
}

would it be tail recursion ? For example

func1(100) = func1(func1(111)) = func1(101) = 91

so the last recursive call would be func1(101) and it should deliver the results so that would be tail recursion right? I'm a little confused. Thank you!

Answer 1

It's not tail-recursive. You could rewrite the code to look like this:

def func1(n: Int): Int = {
   if (n > 100) {
      n - 10
   }
   else {
      val f = func1(n + 11)
      func1(f)
   }
}

You can see that there is a call to func1 on line 6 that is not in the tail position.

Answer 2

Any easy way to check would be to just try it. the @tailrec annotation (import scala.annotation.tailrec) will give you a compile-time error if your method is not tail recursive.

This is not tail recursive though because you have a recursive call in a non-tail position.

You have two recursive calls in your function, one is in a tail position, it's the last call in the method, but the other is the input to that call, which isn't tail recursive because something comes after it, the next call. It's not enough to have one recursive call in the tail position, every recursive call must be a tail call

Answer 3

No, your example is not a case of tail recursion.

func1(func1(n + 11)) is a case of non-linear recursion (particularly, nested recursion).

Tail recursion is a particular case of linear recursion that can be immediately converted into iteration (loop), which is why it is interesting, as it allows easy optimization.

In your case, the call to the inner function is not the last operation in the function (there is still pending the call to the outer function), thus, it is not tail recursion.

Answer 4

Actually tail recursive method is a method which 'returns' a result itself or next invocation. If you can rewrite your algorithm the following way - it can be tail recursive.

trait Recursive[R] {
  def oneIteration: Either[R, Recursive[R]]
}

object Recursive {
  def interpret[R](fn: Recursive[R]): R = {
    var res: Either[R, Recursive[R]] = Right(fn)
    while(res.isRight) {
      res = res.right.get.oneIteration
    }
    res.left.get
  }
}

object Factorial extends App {
  def factorial(acc: BigDecimal, n: Int): Recursive[BigDecimal] = new Recursive[BigDecimal] {
    override def oneIteration(): Either[BigDecimal, Recursive[BigDecimal]] = {
      if(n == 1 ){
        Left(acc)
      }
      else {
        Right(factorial(acc * n, n - 1))
      }
    }
  }

  val res = Recursive.interpret(factorial(1 , 5))
  println(res)
}