C language function recursion and call instance analysis

I. basic contents:

Functions in C can be called recursively, that is, they can call themselves directly (simple recursion) or indirectly (indirect recursion).
Key points:
1. C language functions can be called recursively.
2. Can be directly or indirectly called in two ways. Only direct recursive calls are discussed for now.

Two, recursive conditions

To solve the problem by recursion, the following three conditions must be met:
1. The problem to be solved can be transformed into a new problem, and the solution of this new problem is still the same as the original solution, only the objects to be processed increase or decrease regularly.
Note: the method to solve the problem is the same, the parameters of the call function is different each time (regular increase or decrease), if there is no rule is not applicable to recursive call.
2. This transformation process can be applied to solve the problem.
Note: other methods are more cumbersome or difficult to solve, and the use of recursive methods can be a good solution.
3. There must be a clear condition for ending recursion.
Note: be sure to be able to end the recursive call at the appropriate place. Otherwise, the system might crash.

Examples of recursion

Example: using recursion to find n!
When n > At 1, n factorial Can be converted to n times n minus 1 factorial. New problems.
Such as n = 5:
Part one: 5*4*3*2*1 n*(n-1) factorial
Part two: 4*3*2*1 (n-1)*(n-2)!
Part three: 3*2*1 (n-2)(n-3) factorial
Part four: 2 times 1 times n minus 3 times n minus 4 factorial.
Part 5:1 (n-5)! 5 minus 5 is 0, you get a value of 1, and you end the recursion.
Source program:

　　fac(int n)
　　{int t;
　　if(n==1)||(n==0) return 1;
　　else
　　{ t=n*fac(n-1);
　　return t;
　　}
　　}
　　main( )
　　{int m,y;
　　printf( " Enter m: " );
　　scanf( " %d " ,&m);
　　if(m<0) printf( " Input data Error!n " );
　　else
　　{y=fac(m);
　　printf( " n%d! =%d n " ,m,y);
　　}
　　}

Fourth, recursive explanation

1. When the function calls itself, the system will automatically keep the current variables and parameters in the function temporarily. In the new round of calling, the system will open up another storage unit (memory space) for the variables and parameters used by the newly called function. Each function is called using a variable in a different memory space.
2. The more levels of recursive calls there are, the more memory locations the variable with the same name occupies. Keep in mind that every time a function is called, the system opens up new memory space for the function's variables.
3. When the function of this call is finished, the system will free the memory space occupied by this call. The flow of the program returns to the calling point of the previous layer and retrieves the data of the memory space occupied by the variables and parameters in the function when it first entered the layer.
4. All recursive problems can be solved by non-recursive methods, but for some relatively complex recursive problems, the use of non-recursive methods often makes the program very complex and difficult to understand, and the recursive call of functions in solving such problems can make the program concise and clear with good readability; However, recursive calls to functions generally reduce the efficiency of the program, because the system has to allocate memory space for variables in each layer of the call, remember the return point after each layer of the call, and add a lot of extra overhead.

Five, procedure flow

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

A function that calls itself in its body is called a recursive call. This function is called a recursive function. The C language allows recursive calls to functions. In recursive calls, the calling function is called again. Executing a recursive function calls itself repeatedly, each time into a new layer. For example, the function f is as follows:

    int f(int x)
    {
      int y;
      z=f(y);
      return z;
    }

This function is a recursive function. But running this function calls itself endlessly, which is certainly not true. In order to prevent a recursive call from going on indefinitely, there must be a means within the function to terminate the recursive call. The usual way is to add a conditional judgment, after a certain condition is met, no recursive call, and then return layer by layer. The following example illustrates the execution of a recursive call.

Calculate n! By recursion

So let's calculate n factorial recursively It can be expressed by the following formula:
      N! = 1                 (n = 0, 1)
      N * (n - 1)!       (n > 1)
According to the formula, it can be programmed as follows:
Long ff (int n)
{
      Long f;
      If (n < 0) printf (" n < 0, input error ");
      Else if (n = = 0 | | n = = 1) f = 1;
      The else f = ff (n - 1) * n;
      Return (f);
}

The main ()
{
      Int n;
      Long y;
      Printf (" \ ninput a inteager number: \ n ");
      The scanf (" % d ", & n);
      Y = ff (n);
      Printf (" % d! = % ld ", n, y);
}

The function ff given in the program is a recursive function. The main function calls ff and then enters the function ff to execute, if n < 0,n==0 or n=1 ends the execution of the function, otherwise the ff function itself is called recursively. Since the argument of each recursive call is n-1, that is, the value of n-1 is assigned to the parameter n, and then the recursive call is made when the value of n-1 is 1, and the parameter n is also 1, which will cause the recurrence to terminate. Then you can go back layer by layer.

Let's give an example of this process. Let the program when the input is 5, that is to find 5! . The call statement in the main function is y=ff(5), after entering the ff function, because n=5, not equal to 0 or 1, so it should be executed f=ff(n-1)*n, that is, f=ff(5-1)*5. This statement makes a recursive call to ff, or ff(4).

After four recursive calls, the value of the ff function parameter becomes 1, so the recursive call is not continued and the primary function is returned layer by layer. Ff (1) returns 1, ff(2) returns 1*2=2, ff(3) returns 2*3=6, ff(4) returns 6*4=24, and ff(5) returns 24*5=120.

Example 8.5 can also be done without recursion. If you can use the recursive method, namely from 1 times 2, and then times 3... Until n. Recursion is easier to understand and implement than recursion. But some problems can only be solved by recursive algorithm. The typical problem is Hanoi tower.

Hanoi tower problem
      There are three needles on A board, A, B, C. There are 64 disks of different sizes on the top of pin A, the big one is on the bottom and the small one is on the top. See figure 5.4. To move the 64 disks from pin A to pin C, only one disk can be moved at A time. But at all times, the disk on any needle must be kept large and small. Find the steps to move.

The algorithm analysis of this problem is as follows. Let's say there are n plates on A.

If n is equal to 1, you move the disk directly from A to C.

If n=2, then:
          1. Move n-1(equal to 1) disks on A to B;
          2. Move another disk on A to C;
          3. Finally, move n-1(equal to 1) disks on B to C.

If n=3, then:
          A. Move n-1(equal to 2, make it n ') disks on A to B(with the help of C), as follows:
                  (1) move n '-1 on A to C.
                  (2) move one of the disks on A to B.
                  (3) move n '-1 on C to B.
          B. Move one of the disks on A to C.
          C. Move n-1(equal to 2, make it n ') disks on B to C(with the help of A), as follows:
                  (1) move n '-1 on B to A.
                  (2) move one of the plates on B to C.
                  (3) move n '-1 on A to C.

  At this point, we have completed the movement of the three disks.

From the above analysis, it can be seen that when n is greater than or equal to 2, the moving process can be decomposed into three steps:
          The first step   I'm going to move n minus 1 disks from A to B;
          The second step   Move A disk from A to C;
          The third step   I'm going to move n minus 1 disks from B to C; The first and third steps are the same.

When n=3, the first step and the third step are decomposed into three steps of the same kind, namely, to move n '-1 disks from one needle to another, where n' =n-1. Obviously, this is a recursive process, so the algorithm can be programmed as follows:
Move (int n,int x,int y,int z)
{
      If (n = = 1)
          Printf (" % c - > % c \ n ", x, z);
      The else
      {
          Move (n - 1, x, z, y);
          Printf (" % c - > % c \ n ", x, z);
          Move (n - 1, y, x, z);
      }
}
The main ()
{
      Int h;
      Printf (" \ ninput number: \ n ");
      The scanf (" % d ", & h);
      Printf ("the step to moving %2d diskes:\n",h);
      Move (h, 'a', 'b', 'c');
}

      As you can see from the program, the move function is a recursive function with four parameters n,x,y, and z. N is the number of disks, and x,y, and z are the three needles. The move function moves n disks on x to z. When n==1, directly move the disk on x to z, output x - z. Such as n! =1 is divided into three steps: recursively call the move function to move n-1 disks from x to y; Output x and z; Recursively call the move function to move n-1 disks from y to z. In the recursive call process, n=n-1, so the value of n decreases successively, and when n=1, the recursion is terminated and returned layer by layer. When n=4, the result of the program is:
      Input the number:
      4
      The step to moving 4 diskes:
      A and b
      A and c
      B and c
      A and b
      C - > a
      C to b
      A and b
      A and c
      B and c
      B -
      C - > a
      B and c
      A and b
      A and c
      B and c