recursive

define

Recursion, you call yourself while you’re running.

Conditions required to form recursion:

  1. The subproblem must be the same thing as the original problem and simpler;
  2. Cannot invoke itself without limit, must have an exit, simplify to non-recursive condition handling.

Code implementation

To recursively implement the factorial function:

int fact(int n) {
    if (n < 0)
        return 0;
    else if(n == 0 || n == 1)
        return 1;
 else  return n * fact(n - 1); } Copy the code

The working principle of

The stack, also called the stack, stores the local variables of the program (not including static local variables, static variables exist in the static area). In addition, the stack is used to pass arguments and return values when the function is called. Because of the last-in, first-out nature of the stack, the stack is particularly convenient for saving/recovering call scenes. In this sense, we can think of the stack as an area of memory where temporary data is stored and exchanged.

When a function is called in a C program, a chunk of the stack is allocated to hold the information related to the call, and each call is considered active. That chunk of storage on the stack is called an active record or stack frame

The stack frame consists of five areas: input parameters, return value space, temporary storage space for evaluating expressions, state information for function calls, and output parameters.

Stacks are a great way to store function call information. However, stacks have some disadvantages:

The stack maintains information about each function call until the function returns, which can take up quite a bit of space, especially if a program uses a lot of recursive calls. In addition, it takes time to generate and destroy active records because of the amount of information that needs to be saved and recovered.

In short, the recursion of the stack and the stack, time and space are very large consumption.

Tail recursion

Fortunately, a special recursion called tail recursion can be used to avoid the disadvantages mentioned earlier.

define

A recursive call is tail-recursion when it is the last statement executed in the body of the function and its return value is not part of the expression.

The feature of tail-recursive functions that do nothing during regression is important because most modern compilers take advantage of this feature to automatically generate optimized code.

Code implementation

To realize the factorial function in tail recursion:

int facttail(int n, int res)
{
    if (n < 0)
        return 0;
    else if(n == 0)
 return 1;  else if(n == 1)  return res;  else  return facttail(n - 1, n *res); } Copy the code

The principle of tail recursion

When the compiler detects that a function call is tail-recursive, it overwrites the current active record rather than creating a new one on the stack. The compiler can do this because the recursive call is the last statement to execute during the current active period, so there is nothing else to do in the stack frame when the call returns, so there is no need to save the stack frame. By overwriting the current stack frame rather than adding another one on top of it, the amount of stack space used is greatly reduced, which makes the actual performance much more efficient.