# Tail Recursion and Tail Call Optimization

## What is a tail call?

Informally, a tail call is when a function calls another function, and returns immediately. In assembly, it's when a CALL and a RET instructions are found right next to each other. For example, in the following code:

``` ```

``` myFunction: CALL foo CALL bar RET ```

`CALL bar` is a tail call, but `CALL foo` is not.

Note that, it's important that there is no operation between `CALL bar` and `RET`. Consider the following example:

``` ```

``` int foo(x){ return bar(x) * 2; } ```

Even though this looks like a tail call, the caller has to modify the return value after the `CALL` operation. As such, it's not actually a tail call. In assembly:

``` ```

``` CALL bar SHL EAX, 1 RET ```

However the following is a tail call:

``` ```

``` int foo(x){ return bar(x * 2); } ```

In assembly:

``` ```

``` SHL EAX, 1 CALL bar RET ```

As you can see, there is no operation between `CALL` and `RET` this time.

## Optimizing a tail call

A tail call can be optimized by simply replacing `CALL` with `JMP` and removing `RET`. So looking at this example, one more time:

``` ```

``` int foo(x){ return bar(x * 2); } ```

In assembly, no tail call optimization:

``` ```

``` SHL EAX, 1 CALL bar RET ```

In assembly, with tail call optimization:

``` ```

``` SHL EAX, 1 JMP bar ```

This has a minor speed up as you no longer have to save and restore the instruction pointer. The callee (in this case, `bar`) will return all the way back to the caller of this function.

It doesn't have much of an impact on a function like this, but it can have immense impact on recursive calls. A recursive call that takes 1000 recursions will have to save and restore the instruction pointer 1001 times without tail call optimization, but only once with it.

## Epilogues and Prologues

In the above examples, it is assumed that functions don't have a prologue or epilogue which is highly impractical. As such a proper implementation of tail call optimization is a lot trickier than shown here. This is only a rudimentary example.