Tail Recursion

In recursion when return statement is just the function and no other operations, it allows compiler to return last function of the recursion, this is more efficient as compiler need have to keep variables in stack & go back in recursion loop.

e.g

Recursion example of factorial function

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

Tail recursion example of factorial function

def tailFactorial(num: Int, count: Int, product: Int):
Int = {
  if (count > num) product
  else tailFactorial(num, count+1, product * count)
}
tailFactorial(5, 1, 1)

In first case evaluation results in

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

In 2nd case, evaluation

(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120

As highlighted 1st case recursion goes back in stack trace & computes result. Whereas in 2nd case function returns from last statement & no need to go back in stack loop.