Tail Recursion/Call
Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination.
When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the call stack, a simple list of return locations in order of the times that the call locations they describe were reached. For tail calls, there is no need to remember the place we are calling from – instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables[1]), and the newly called function will return its result directly to the original caller. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call's result if any, since the calling function will never get a chance to do anything after the call if the optimization is performed.
A tail call can be located just before the syntactical end of a subroutine:
Here, both
Here, both calls to
For more details visit https://en.wikipedia.org/wiki/Functional_programming
Thanks
Gaurav
Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination.
When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the call stack, a simple list of return locations in order of the times that the call locations they describe were reached. For tail calls, there is no need to remember the place we are calling from – instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables[1]), and the newly called function will return its result directly to the original caller. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call's result if any, since the calling function will never get a chance to do anything after the call if the optimization is performed.
A tail call can be located just before the syntactical end of a subroutine:
function foo(data) {
a(data);
return b(data);
}
a(data) and b(data) are calls, but b
is the last thing the procedure executes before returning and is thus
in tail position. However, not all tail calls are necessarily located at
the syntactical end of a subroutine. Consider:function bar(data) {
if ( a(data) ) {
return b(data);
}
return c(data);
}
b and c are in tail
position. This is because each of them lies in the end of if-branch
respectively, even though the first one is not syntactically at the end
of bar's body.For more details visit https://en.wikipedia.org/wiki/Functional_programming
Thanks
Gaurav
No comments:
Post a Comment