What is tail recursion in data structure?

Answer 1

If there is n consecutive execution in a recursive function, then the function will return the value to itself either 1 or n-1 times.

but in normal recursion it returns n times the value to that function.

Answer 2

Tail recursion is a term used in computer programming, whereby the final statement in a function is a recursive call to the same function. Function calls are expensive in terms of performance as well as memory consumption, but when the final statement is a recursive call there is an opportunity for optimisation.

Program execution normally flows from one statement to the next, but all non-trivial programs will inevitably break the flow of execution with conditional statements (if), jumps (goto), loops (for and while) and procedure calls (function calls). In order to achieve these "branches", the CPU's next instruction pointer is simply replaced with the address of the appropriate instruction and execution continues from that point on. However, function calls need to be treated differently because there has to be a clear return path back to the point of the call.

When a function call is encountered, the CPU's current state must be saved so that it can be restored when the function returns. There also has to be some means of telling the called function where to resume execution of the current function when it returns. Also, the caller needs some means of passing arguments to the called function. All of this is achieved through a special area of memory known as the procedure call stack (often shortened to the call stack, or simply the stack). Being a stack, values can be popped off in the reverse order they were pushed on, thus providing a simple means of restoring the current function's state as well as a means of passing information to and from functions (arguments and return values).

However, this functionality comes at a cost in terms of performance. Functions are a programming aid, making it easier to read and maintain source code. But in order to achieve the highest performance, the compiler uses complex algorithms to determine if a function call is actually needed or not. If the function is fairly simple (one that performs a very simple operation and returns a value), it will often inject the code directly in place of the function call, thus eliminating the function call entirely. This technique is known as inline expansion and allows programmers to make use of functions without worrying too much about the performance impact. While inline expansion helps performance by eliminating unnecessary function calls, it can also have a negative impact because it also increases code size (large code tends to run slower than short code).

Recursive functions are often difficult if not impossible to expand inline. If the function is fairly trivial, a good compiler may be able to expand a few of the recursions, but ultimately it must draw the line somewhere otherwise code growth begins to impact the performance. However, when the final statement of a function is a call to the same function (a tail recursion), there is an obvious opportunity for optimisation.

Tail recursion does not need to maintain state because as soon as the called instance of the function returns, the current instance also returns. A good compiler will optimise away the function call simply by modifying the current instance's arguments and jumping back to the beginning -- re-invoking the same instance without making an unnecessary function call.

Although many algorithms are naturally recursive (sorting algorithms in particular), those that use tail recursion can be manually modified to become iterative algorithms (loops). However, this can often result in code that is more complex to both read and maintain. But since a good compiler can do this for us, we can take advantage of the simplicity of a recursive call and let the compiler do the hard work for us by injecting the necessary code to render the algorithm iterative.

Answer 3

Tail recursion is a term used in computer programming, whereby the final statement in a function is a recursive call to the same function. Function calls are expensive in terms of performance as well as memory consumption, but when the final statement is a recursive call there is an opportunity for optimisation.

Program execution normally flows from one statement to the next, but all non-trivial programs will inevitably break the flow of execution with conditional statements (if), jumps (goto), loops (for and while) and procedure calls (function calls). In order to achieve these "branches", the CPU's next instruction pointer is simply replaced with the address of the appropriate instruction and execution continues from that point on. However, function calls need to be treated differently because there has to be a clear return path back to the point of the call.

When a function call is encountered, the CPU's current state must be saved so that it can be restored when the function returns. There also has to be some means of telling the called function where to resume execution of the current function when it returns. Also, the caller needs some means of passing arguments to the called function. All of this is achieved through a special area of memory known as the procedure call stack (often shortened to the call stack, or simply the stack). Being a stack, values can be popped off in the reverse order they were pushed on, thus providing a simple means of restoring the current function's state as well as a means of passing information to and from functions (arguments and return values).

However, this functionality comes at a cost in terms of performance. Functions are a programming aid, making it easier to read and maintain source code. But in order to achieve the highest performance, the compiler uses complex algorithms to determine if a function call is actually needed or not. If the function is fairly simple (one that performs a very simple operation and returns a value), it will often inject the code directly in place of the function call, thus eliminating the function call entirely. This technique is known as inline expansion and allows programmers to make use of functions without worrying too much about the performance impact. While inline expansion helps performance by eliminating unnecessary function calls, it can also have a negative impact because it also increases code size (large code tends to run slower than short code).

Recursive functions are often difficult if not impossible to expand inline. If the function is fairly trivial, a good compiler may be able to expand a few of the recursions, but ultimately it must draw the line somewhere otherwise code growth begins to impact the performance. However, when the final statement of a function is a call to the same function (a tail recursion), there is an obvious opportunity for optimisation.

Tail recursion does not need to maintain state because as soon as the called instance of the function returns, the current instance also returns. A good compiler will optimise away the function call simply by modifying the current instance's arguments and jumping back to the beginning -- re-invoking the same instance without making an unnecessary function call.

Although many algorithms are naturally recursive (sorting algorithms in particular), those that use tail recursion can be manually modified to become iterative algorithms (loops). However, this can often result in code that is more complex to both read and maintain. But since a good compiler can do this for us, we can take advantage of the simplicity of a recursive call and let the compiler do the hard work for us by injecting the necessary code to render the algorithm iterative.