What Is a Tail Recursion?

If all recursive 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 executed in the entire function body and its return value is not part of the expression, the recursive call is tail recursive. The feature of tail recursive function is that it does not need to do any operation during the regression process. This feature is important because most modern compilers will use this feature to automatically generate optimized code.

Tail recursion

If all recursive 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 executed in the entire function body and its return value is not part of the expression, the recursive call is tail recursive. The feature of tail recursive function is that it does not need to do any operation during the regression process. This feature is important because most modern compilers will use this feature to automatically generate optimized code.

Chinese name

Tail recursion

When detected

It overwrites the current activity record

Instead of

Create a new one in the stack

translater

Can do it

when

To understand how tail recursion works, let's calculate the factorial again in recursive form. First, this makes it easy to understand why the recursion defined earlier is not tail recursion. Recall the previous definition of computing n !: Calculate n times (n-1)! In each active period, let n = n-1 and continue this process until n = 1. This definition is not tail-recursive, because the return value of each active period depends on multiplying the return value of the next active period by n, so the stack frame generated by each call will have to be saved on the stack until the next sub-call The return value is OK. Now let us consider defining the process of computing n! In the form of tail recursion ^[1] .

This definition also needs to accept the second parameter a, but there is not much difference. a (initialized to 1) maintains the depth of the recursion level. This prevents us from having to multiply the return value by n each time. However, in each recursive call, let a = na and n = n-1. Continue the recursive call until n = 1, which meets the end condition, and then just return a directly.

Code Example 3-2 shows a C function facttail that takes an integer n and calculates the factorial of n in tail-recursive form. This function also accepts a parameter a, the initial value of a is 1. Facttail uses a to maintain the depth of the recursive hierarchy, except that it is similar to fact. The reader can notice the similarities between the specific implementation of the function and the definition of tail recursion.

Example 3-2: Implementation of a function to calculate factorials in tail recursion form ^[1]

  /*facttail.c*/

 #include "facttail.h"

 / * facttail * /


 int facttail (int n, int a)
 {

 / * Compute a factorialina tail-recursive manner. * /

 if (n <0)
 return 0;
 else if (n == 0)
 return 1;
 else if (n == 1)
 return a;
 else
 return facttail (n-1, n * a);

 }

The function in Example 3-2 is tail-recursive because a single recursive call to facttail is the last statement executed before the function returned. It happens that the last statement in facttail is also a call to facttail, but this is not required. In other words, there can be other statements executed after the recursive call, but they can only be executed when the recursive call is not executed ^[1] .

Tail recursion is extremely important. Without tail recursion, the stack consumption of a function is incalculable and it is necessary to save the stack of many intermediate functions. For example, f (n, sum) = f (n-1) + value (n) + sum; will save n function call stacks, and use tail recursion f (n, sum) = f (n-1, sum + value (n)); In this way, only the latter function stack can be retained, and the previous optimization can be deleted.

There may be many special cases in the C language, but the programming language is not only C. In the functional language Erlang (also a stack language), if you want to maintain the high concurrency of the language, you must use tail recursion to replace the traditional Recursion.

The original statement is wrong:

An algorithm used in computer programming techniques.

Tail recursion is for traditional recursive algorithms. Traditional recursive algorithms are often regarded as flood beasts. Its fame is as if it is always associated with inefficiency.

Tail recursion is calculated from the end, and the corresponding result is calculated every recursion, that is, the function call appears at the end of the caller function, because it is the tail, so there is no need to save any local variables. Let the called The function returns over the caller and returns to the caller's caller.

The following are specific examples:

Linear recursion:

  long Rescuvie (long n) {

 return (n == 1)? 1: n * Rescuvie (n-1);

 }

Tail recursion:

  long TailRescuvie (long n, long a) {

 return (n == 1)? a: TailRescuvie (n-1, a * n);

 }


 long TailRescuvie (long n) {//
 return (n == 0)? 1: TailRescuvie (n, 1);

 }

When n = 5

For linear recursion, his recursive process is as follows:

Rescuvie (5)

{5 * Rescuvie (4)}

{5 * {4 * Rescuvie (3)}}

{5 * {4 * {3 * Rescuvie (2)}}}

{5 * {4 * {3 * {2 * Rescuvie (1)}}}}

{5 * {4 * {3 * {2 * 1}}}}

{5 * {4 * {3 * 2}}}

{5 * {4 * 6}}

{5 * 24}

120

For tail recursion, his recursion process is as follows:

TailRescuvie (5)

TailRescuvie (5, 1)

TailRescuvie (4, 5)

TailRescuvie (3, 20)

TailRescuvie (2, 60)

TailRescuvie (1, 120)

120

It is easy to see that ordinary linear recursion consumes more resources than tail recursion. In terms of implementation, the process is repeated every time

Calls make the call chain continuously longer. The system has to use the stack to save and restore data. Tail recursion

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