Tail Call Optimization is the process by which a smart compiler can make a call to a function and take no additional stack space.
The only situation in which this happens is if the last instruction executed in a function is a call to another function or the function itself.
The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.
Normally during a recursion, the runtime needs to keep track of all the recursive calls, so that when one returns it can resume at the previous call and so on.
Keeping track of all the calls takes up space, which gets significant when the function calls itself a lot. But with tail call optimization, it can just say "go back to the beginning, only this time change the parameter values to these new ones." It can do that because nothing after the recursive call refers to those values.
Note first of all that not all languages support it.
In plain terms, TCO applies to a special case of recursion. If the last thing you do in a function is call itself (e.g. it is calling itself from the "tail" position), this can be optimized by the compiler to act like iteration instead of standard recursion.
The following example of calculating Factorial in elixir explain how Tail Call Optimization can be done.
defmodule Factorial do def of(0), do: 1 def of(n) when n > 0 do # Not tail call optimized # because recursion needs to # occur before multiplication n * of(n - 1) end end
defmodule Factorial do def of(0), do: 1 def of(n), do: of(n, 1) def of(1, acc), do: acc def of(n, acc) when n > 1 do # Tail call optimized # because recursion is the # last calculation of(n - 1, acc * n) end end
Subscribe to Today I learned
Get the latest posts delivered right to your inbox