Tail-Call optimization

Recursive Functions can cause some trouble because of the ***“call stack”. ***The issue is that the “call stack” has a limited size, and when the evaluation of one function body calls another function, a new element is pushed on the call stack, and it is popped off when the called function completes.

There is a solution to this issue that was described in a 1977 paper about LISP by Guy Steele, **Tail Recursion. **

The programmer could rewrite the count function so that it does *not *need to do any additional computation after the recursive call. The trick is to create a helper function with an extra parameter, as the second approach (OCaml example):

 
(* WITHOUT TAIL RECURSION *)
let rec count n =
  if n = 0 then 0 else 1 + count (n - 1)
 
(* WITH TAIL RECURSION *)
let rec count_aux n acc =
  if n = 0 then acc else count_aux (n - 1) (acc + 1)

Here’s why tail position matters: **A recursive call in tail position does not need a new stack frame. It can just reuse the existing stack frame. **That’s because there’s nothing left of use in the existing stack frame! There’s no computation left to be done, so none of the local variables, or next instruction to execute, etc. matter any more. None of that memory ever needs to be read again, because that call is effectively already finished. So instead of wasting space by allocating another stack frame, the compiler “recycles” the space used by the previous frame.

This is the tail-call optimization.

It is important that the compiler support the optimization. Otherwise, the transformation you do to the code as a programmer makes no difference. Indeed, most compilers do support it, at least as an option. Java is a notable exception.

https://stackoverflow.com/questions/310974/what-is-tail-call-optimization

The Recipe for Tail Recursion. In a nutshell, here’s how we made a function be tail recursive:

1. Change the function into a helper function. Add an extra argument: the accumulator, often named acc.
2. Write a new “main” version of the function that calls the helper. It passes the original base case’s return value as the initial value of the accumulator.
3. Change the helper function to return the accumulator in the base case.
4. Change the helper function’s recursive case. It now needs to do the extra work on the accumulator argument, before the recursive call. This is the only step that requires much ingenuity.

An Example: Factorial. Let’s transform this factorial function to be tail recursive:

(* [fact n] is [n] factorial *)let rec fact n =
  if n = 0 then 1 else n * fact (n - 1)

val fact : int -> int = <fun>

First, we change its name and add an accumulator argument:

let rec fact_aux n acc = ...

Second, we write a new “main” function that calls the helper with the original base case as the accumulator:

let rec fact_tr n = fact_aux n 1

Third, we change the helper function to return the accumulator in the base case:

if n = 0 then acc ...

Finally, we change the recursive case:

else fact (n - 1) (n * acc)

Putting it all together, we have:

let rec fact_aux n acc =
  if n = 0 then acc else fact_aux (n - 1) (n * acc)
 
let fact_tr n = fact_aux n 1

val fact_aux : int -> int -> int = <fun>

val fact_tr : int -> int = <fun>

---

🌱 Back to Garden