Anonymous user
Tail Recursion and Tail Call Optimization: Difference between revisions
Jump to navigation
Jump to search
Tail Recursion and Tail Call Optimization (view source)
Revision as of 06:04, 28 March 2023
, 1 year agoOkay, I delayed this way more than I thought I would...
| [unchecked revision] | [unchecked revision] |
(Okay, I delayed this way more than I thought I would...) |
|||
Line 1:
==
Formally, a call within a function is a tail call if the caller does not modify the state after the call and before returning.
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:
<code>
myFunction:
CALL foo
CALL bar
RET
</code>
<code>CALL bar</code> is a tail call, but <code>CALL foo</code> is not.
Note that, it's important that there is no operation between <code>CALL bar</code> and <code>RET</code>. Consider the following example:
<code>
int foo(x){
return bar(x) * 2;
}
</code>
Even though this looks like a tail call, the caller has to modify the return value after the <code>CALL</code> operation. As such, it's not actually a tail call. In assembly:
<code>
CALL bar
SHL EAX, 1
RET
</code>
However the following is a tail call:
<code>
int foo(x){
return bar(x * 2);
}
</code>
In assembly:
<code>
SHL EAX, 1
CALL bar
RET
</code>
As you can see, there is no operation between <code>CALL</code> and <code>RET</code> this time.
== Optimizing a tail call ==
A tail call can be optimized by simply replacing <code>CALL</code> with <code>JMP</code> and removing <code>RET</code>. So looking at this example, one more time:
<code>
int foo(x){
return bar(x * 2);
}
</code>
In assembly, no tail call optimization:
<code>
SHL EAX, 1
CALL bar
RET
</code>
In assembly, with tail call optimization:
<code>
SHL EAX, 1
JMP bar
</code>
This has a minor speed up as you no longer have to save and restore the instruction pointer. The callee (in this case, <code>bar</code>) 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.
| |||