What is tail recursion? What is tail recursion?

An algorithm used in computer programming techniques.

Tail recursion is aimed at traditional recursive algorithms.

In other words, traditional recursive algorithms are often seen as a flood beast. It's notorious, and it seems to be forever associated with inefficiency.

Tail recursion is to start from the end, and the corresponding result is calculated every time the recursion is made, that is, the function call appears at the tail of the caller's function, because it is the tail, so there is no need to save any local variables. Directly let the called function return past the caller and back to the caller.

It's easy to see that ordinary linear recursion is more resource-intensive than tail recursion, and in terms of implementation, it's a process that is repeated every time.

The invocation chain is constantly lengthening. The system had to use the stack for data saving and recovery. And tail recursion.

There is no such problem, because his state is completely saved by n and a. <>

C allows a function to call itself, which is called recursion.

In its simplest form, recursive calls are placed at the end of the function, just before the return statement. This form is called tail recursion or end recursion because the recursive call appears at the end of the function. Since it acts as a recursive statement, it is the simplest form of recursion.

The recursion must contain a statement that can terminate the recursive call!

The point of recursion is that it provides the easiest way to solve certain programming problems, while the disadvantage is that some recursive algorithms can quickly exhaust the memory resources of the computer. At the same time, programs that use recursion are difficult to read and maintain. <>

A program that invokes its own programming technique is called recursion. Recursion as an algorithm is inProgramming languagesIt is widely used.

A procedure or function has a method that directly or indirectly invokes itself in its definition or description, and it usually transforms a large and complex problem into a smaller problem similar to the original problem to solve, and the recursive strategy can describe the solution process with only a small number of programs.

The number of repeated calculations required greatly reduces the amount of the program.

The power of recursion lies in defining an infinite set of objects in finite statements.

In general, recursion needs to have boundary conditions.

Recursive forward segments and recursive return segments. When the boundary conditions are not satisfied, recursively advance; When the boundary conditions are satisfied, recursively returns.

Disadvantages of recursion:

Recursive algorithms. Relatively commonly used algorithms such as ordinary loops are less efficient. Therefore, recursion should be avoided unless there is no better algorithm or in a particular case where recursion is more appropriate.

In the process of recursive calls, the system opens up a stack for each layer of return points, local quantities, etc. to store. Too many recursions can easily cause stack overflows, etc.

The above content reference: Encyclopedia - Recursion.

If all the recursive forms of calls in a function appear at the end of the function, we call the recursive function tail recursive.

When a recursive call is the last statement to be executed in the entire function body and its return value is not part of the expression, the recursive call is tail recursion.

The feature of tail recursive functions is that they don't have to do anything during the regression process, which is important because most modern compilers take advantage of this feature to automatically generate optimized **.

Tail recursion has two more features on the basis of ordinary tail calls:

At the tail of the call is the function itself.

It can be optimized so that the computation only occupies constant stack space.

In the process of recursive calls, the system opens up stacks for the return points and local quantities of each layer to store, and too many recursion times can easily cause stack overflow.

At this time, tail recursion can be used, that is, all recursive forms of calls in a function appear at the end of the Bishen function, and for tail recursion, because there is only one call record, it will never happen"Stack overflow"Mistake.

The above content refers to Encyclopedia-tail recursion.

Both recursion and iteration are types of loops.

To put it simply, recursion is the repeated call of the function itself to implement the loop. The difference between iteration and ordinary loop is that the variable participating in the operation in the loop is also the variable that saves the result, and the current saved result is used as the initial value of the next loop calculation.

In a recursive loop, when the termination condition is met, it returns layer by layer to end. The iteration uses a counter to end the loop. Of course, in many cases, it is a multi-cycle mixture, depending on the specific needs.

An example of recursion, for example, given an array of integers, uses a halved query to return the index of the specified value in the array, assuming that the array is sorted, and for the sake of description, assuming that the elements are all positive and the length of the array is an integer multiple of 2.

A half-split query is a type of query that is much faster than iterating through all the elements.

int find(int *ary,int index,int len,int value)

if(len==1) last element.

if (ary[index]==value)return index;A successful query returns an index.

return -1;Failed, returns -1

If the length is greater than 1, perform a half-fold recursive query.

int half=len/2;

Check whether the checked value is greater than the last value in the upper half, and if so, recursively query the second half.

if(value>ary[index+half-1])

return find(ary,index+half,half,value);

Otherwise, recursively query the top half.

return find(ary,index,half,value);

The classic example of iteration is the accumulation of real numbers, such as the sum of all real numbers from 1 to 100.

int v=1;

for(i=2;i<=100;i++)

v=v+i;

Recursion is a method of solving a problem by repeatedly breaking it down into sub-problems of the same kind. The recursive method can be used to solve computer science problems with many volts, so it is an important concept in computer science.

The vast majority of programming languages support self-calling of functions, where functions can be recursively called by calling themselves. Computational theory can prove that recursion can completely replace loops, so it is customary to use recursion to implement loops in many functional programming languages. In programming languages that support self-calling, recursion can be done with simple function calls.

Tail recursion is when a recursive function calls itself and passes its value back without adding operations to it. Tail recursion is equivalent to loops, and can be optimized as looping instructions in some languages. As a result, tail recursion does not take up call stack space in these languages.