Tail recursion and call by name / value

Question

Learning Scala and functional programming in general. In the following tail-recursive factorial implementation:

def factorialTailRec(n: Int) : Int = {

    @tailrec
    def factorialRec(n: Int, f: => Int): Int = {
      if (n == 0) f else factorialRec(n - 1, n * f)
    }

    factorialRec(n, 1)
}

I wonder whether there is any benefit to having the second parameter called by value vs called by name (as I have done). In the first case, every stack frame is burdened with a product. In the second case, if my understanding is correct, the entire chain of products will be carried over to the case if ( n== 0) at the nth stack frame, so we will still have to perform the same number of multiplications. Unfortunately, this is not a product of form a^n, which can be calculated in log_2n steps through repeated squaring, but a product of terms that differ by 1 every time. So I can't see any possible way of optimizing the final product: it will still require the multiplication of O(n) terms.

Is this correct? Is call by value equivalent to call by name here, in terms of complexity?

Answer 1

Through experimentation I found out that with the call by name formalism, the method becomes... non-tail recursive! I made this example code to compare factorial tail-recursively, and factorial non-tail-recursively:

 package example

 import scala.annotation.tailrec

 object Factorial extends App {

  val ITERS = 100000

  def factorialTailRec(n: Int) : Int = {
    @tailrec
    def factorialTailRec(n: Int, f: => Int): Int = {
      if (n == 0) f else factorialTailRec(n - 1, n * f)
    }
    factorialTailRec(n, 1)
  }

  for(i <-1 to ITERS) println("factorialTailRec(" + i + ") = " + factorialTailRec(i))


  def factorial(n:Int) : Int = {
    if(n == 0) 1 else n * factorial(n-1)
  }

  for(i <-1 to ITERS) println("factorial(" + i + ") = " + factorial(i))

}

Observe that the inner tailRec function calls the second argument by name. for which the @tailRec annotation still does NOT throw a compile-time error!

I've been playing around with different values for the ITERS variable, and for a value of 100,000, I receive a... StackOverflowError!

(The result of zero is there because of overflow of Int.)

So I went ahead and changed the signature of factorialTailRec/2, to:

def factorialTailRec(n: Int, f: Int): Int 

i.e call by value for the argument f. This time, the portion of main that runs factorialTailRec finishes absolutely fine, whereas, of course, factorial/1 crashes at the exact same integer.

Very, very interesting. It seems as if call by name in this situation maintains the stack frames because of the need of computation of the products themselves all the way back to the call chain.

Answer 2

Let me just expand a little bit what you've already been told in comments. That's how by-name parameters are desugared by the compiler:

@tailrec
def factorialTailRec(n: Int, f: => Int): Int = {
  if (n == 0) {
    val fEvaluated = f
    fEvaluated
  } else {
    val fEvaluated = f // <-- here we are going deeper into stack. 
    factorialTailRec(n - 1, n * fEvaluated)
  }
}