Tail Call Optimisation: A way to avoid Overflow of Stack

Tail Call optimisation
Tail call optimisation is compiler based optimisation ,it is used to avoid allocating new stack space in case of recursive call in function.So let’s see what happens in tail call optimisation. When a function is called, the computer must “remember” the place it was called from, the return address, but in case of tail call the new called function is not alloted with a new stack space instead it replaces the the calling function in the same stack due to which stack overflow can be avoided.Most of the funtional program support tail call optimisation.For function having tail call optimisation it should have the proper implementation. Let’s see by example how to write tail call optimisation:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

Above implementation of factorial doesn’t do tail call optimisation because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns.

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6