Yyds dry goods counting tail recursion is better than recursion

Many programmers know that recursive calls , But I don't know what tail recursion is . Today, I will mainly analyze tail recursion .

recursive

Function call itself .

​ The conditions that constitute recursion ：

1. The sub problem must be the same thing as the original problem , And it's simpler ;
2. You can't call itself unlimited , There must be an exit , Reduction to non recursive state processing .

Implementing factorials recursively ：

Log in and copy

      
      

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

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
      
      

working principle

Stack is also called stack , Store local variables of the program （ Static local variables are not included ,static The variable has a static area ）. in addition to , When a function is called , The stack is used to pass parameters and return values . Due to the last in first out feature of the stack , So stacks are very convenient for storing / Resume call site . In this sense , We can think of the stack as a register 、 Memory area for exchanging temporary data .

When C When a function is called in the program , A space will be allocated in the stack to hold the information related to the call , Each call is considered active . The storage space on the stack is called active record or stack frame

Stack frame by 5 It's made up of regions ： Input parameters 、 Return value space 、 Temporary storage space used to evaluate expressions 、 State information and output parameters saved during function call .

Stack is a great way to store function call information , However, the stack also has some shortcoming ：

The stack maintains the information of each function call until the function returns , This takes up a considerable amount of space , Especially when many recursive calls are used in the program . besides , Because there is a lot of information that needs to be saved and restored , Therefore, it takes some time to generate and destroy active records .

In short , Recursive stack pressing and stack pushing , Both time and space are consumed .

To avoid consuming too much time and space , Next, we introduce tail recursion .

Tail recursion

When the recursive call is in the whole function body The last executed statement And its The return value is not part of the expression when , This recursive call is tail recursion .

Tail recursive function is characterized by no operation in the regression process , This feature is important , Because most modern compilers use this feature to automatically generate optimized code .

The factorial function is realized by tail recursion ：

Log in and copy

      
      

       
       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);
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
      
      

The implementation principle of tail recursion

When the compiler detects that a function call is tail recursive , It overwrites the current activity record instead of creating a new one on the stack . The compiler can do this , Because the recursive call is the last statement to be executed in the current active period , So when the call returns, there is nothing else to do in the stack frame , So there is no need to save the stack frame . By overwriting the current stack frame instead of adding a new one over it , In this way, the stack space used is greatly reduced , This makes the actual operation efficiency become higher .