Scala by Example Chapter 4 Solutions Exercise 4.6.1

Exercise 4.6.1 Design a tail-recursive version of factorial

A tail-recursive call is a method where the last step of the method is to call itself. The key point to remember is that the call should be a pure call and not an expression that involves a call to the method. If it is a pure call, the stack frame can be reused rather than allocating a new stack frame. The version of the factorial function seen in most places is a recursive one but its not tail-recursive since the last line of the factorial function usually calls n * factorial(n -1).

Here's the tail-recursive version of factorial. As you can see below, making a tail-recursive version involves adding an extra parameter. This parameter involves a computation that's different from just a reduction as in simple recursion.

	object TailRecursiveFactorial {
	def factorial(n: Int, product: Int): Int =
	if (n == 1) product else factorial(n - 1, n * product)
	def main(args: Array[String]) {
	println("Factorial of 8 is: " + factorial(8,1))
	}
	}

view raw tailrecursivefactorial.scala hosted with ❤ by GitHub