An in depth analysis of recursive algorithm in C language

Many textbooks use computer factorials and Fibonacci sequences to illustrate recursion, and unfortunately our lovely famous teacher Lao tan's book C programming is a recursive function that starts with the calculation of factorials. So the first thing that led those of you who read this book to see the factorial calculation was recursion. But in the calculation of factorial, recursion does not provide any advantage. In the Fibonacci sequence, it's even more horribly inefficient.

Here is a simple program to illustrate recursion. The purpose of the program is to convert an integer from binary form to printable character form. For example, given a value of 4267, we need to generate the characters' 4', '2',' 6', and '7' in turn. Just as the %d format code is used in the printf function, it performs a similar process.

Our strategy is to divide this value repeatedly by 10 and print out the remainder. For example, 4267 has a remainder of 7 into 10, but we cannot print the remainder directly. What we need to print is the value of the number '7' in the machine character set. In ASCII, the character '7' has a value of 55, so we need to add 48 to the remainder to get the correct character, but using character constants instead of integer constants improves the portability of the program. The ASCII code of '0' is 48, so we use the remainder plus' 0', so we have the following relation:

                  '0' + 0 = '0'
                  '0' + 1 = '1'
                  '0' + 2 = '2'
                .
From these relationships, it is easy to see that adding '0' to the remainder produces the code for the corresponding character. And then you print out the remainder. And then the quotient, 4267/10 is equal to 426. Then repeat the steps with this value.

The only problem with this approach is that it produces Numbers in exactly the opposite order; they are printed backwards. So we use recursion in our program to fix this problem.

The function in our program is recursive because it contains a call to itself. At first glance, functions seem to never end. When a function is called, it calls itself, the second call calls itself, and so on, seemingly forever. And this is the last thing we thought about when we first started with recursion. But that is not the case.

The recursion of this program implements some type of spiral while loop. The while loop must make some progress each time the loop body executes, gradually approaching the loop termination condition. The same is true of recursive functions, which must get closer and closer to some constraint after each recursive call. When the recursive function meets this constraint, it no longer calls itself.

In a program, the limiting condition of recursive functions is that the variable quotient is zero. Before each recursive call, we divide the quotient by 10, so each recursive call gets closer and closer to zero. When it finally becomes zero, the recursion terminates.

#include <stdio.h>
int binary_to_ascii( unsigned int value)
{
          unsigned int quotient;

   　　quotient = value / 10;
   　　if( quotient != 0)
       　　　　binary_to_ascii( quotient);
   　　putchar ( value % 10 + '0' );
}

How does recursion help us print these characters in the right order? Here's how the function works.
1. Divide the parameter value by 10
If the value of a quotient is non-zero, call binary-to- ASCII to print the digits of the current value of the quotient
3. Next, print the remainder of the division operation in step 1

Notice that in step 2, we need to print the digits of the current value of the quotient. The problem we face is exactly the same as the original one, except that the quotient of the variable becomes smaller. We solved this problem with the function we just wrote, which converts integers to individual numeric characters and prints them out. As the quotient gets smaller and smaller, the recursion eventually terminates.

Once you understand recursion, the easiest way to read a recursive function is not to obsess over its execution, but to trust the recursive function to do its job. If you get each step right, your constraints right, and you get closer to the constraints after each call, the recursive function always gets the job done correctly.

However, in order to understand how recursion works, you need to track the execution of recursive calls, so let's do that. The key to tracking the execution of a recursive function is to understand how variables declared in the function are stored. When a function is called, its variable space is created on the runtime stack. The variables of the previously called function are left on the stack, but they are hidden by the variables of the new function and therefore cannot be accessed.

This is the case when the recursive function calls itself. Each time a new call is made, a number of variables are created that mask the variables created by the previous call to the recursive function. When I trace the execution of a recursive function, I have to distinguish between variables that are scored in different calls to avoid confusion.

Functions in a program have two variables: the parameter value and the local variable quotient. The following figures show the state of the stack, with currently accessible variables at the top of the stack. All other called variables are shaded in gray to indicate that they cannot be accessed by the currently executing function.

Suppose we call the recursive function with the value 4267. When the function first executes, the stack looks like this:

After performing division, the stack looks like this:

    Next, the if statement determines that the quotient value is non-zero, so a recursive call is made to the function. When the function is called a second time, the stack looks like this:   A new set of variables is created on the stack, hiding the previous set of variables, which cannot be accessed unless the current recursive call returns. After performing the division operation again, the stack looks like this:

The value of the quotient is now 42 and still non-zero, so you need to continue with the recursive call and create another set of variables. After performing the starting operation of this call, the stack is as follows:   At this point, the value of the quotient is still non-zero and a recursive call still needs to be made. After performing the division operation, the stack looks like this:

Not counting the recursive call statement itself, the statements executed so far are just division operations and tests on the values of the quotient. Since these statements are recursively called and executed repeatedly, the effect is similar to that of a loop: when the value of a quotient is non-zero, the loop starts again with its value as the initial value. However, a recursive call will hold some information (unlike a loop), which is the value of a variable stored on the stack. This information will soon become very important.

Now that the value of the quotient becomes zero, the recursive function stops calling itself and starts printing the output. The function then returns and begins destroying the value of the variable on the stack.

Each time putchar is called to get the last number of the variable value, the method is to carry out mod 10 mod 10 to the value, the result is an integer between 0 and 9. Add it to the character constant '0', the result is the ASCII character corresponding to the number, and print it out.

Output 4:

The function then returns, and its variables are destroyed from the stack. The previous call to the recursive function then resumes, using her own variables, which are now at the top of the stack. Because its value value is 42, the number printed after calling putchar is 2.

Output 42:

Then the call to the recursive function returns, its variables are destroyed, and at the top of the stack is the variable that the recursive function called the previous time. The recursive call continues from this location, and this time the number printed is 6. Before this call returns, the stack looks like this:

The output of 426:

Now that we've expanded the whole recursion, we're back to the original call to the function. This call prints out the number 7, which is the remainder of its value argument over 10.

The output of 4267: and then, the recursive function is completely return to other function calls its location.
If you line up the printed characters one by one and they appear on the printer or screen, you will see the correct value: 4267
The use of recursion must have a jump condition:
This is one of the simplest recursions, but it will continue to execute, terminated by Ctrl+C.

#include <stdio.h>
void prn(int num) {
    printf("%d/n", num);
    if (num > 0) prn(--num);  
}
int main(void)
{
    prn(9);
    getchar();
    return 0;
}

 The instance :  Flip string 
#include <stdio.h>
void revers(char *cs);
int main(void)
{
    revers("123456789");
    getchar();    
    return 0;
}
void revers(char *cs)
{
    if (*cs)
    { 
        revers(cs + 1);
        putchar(*cs);
    }
}

 The instance :  factorial 
#include <stdio.h>
int factorial(int num);
int main(void)
{
    int i;
    for (i = 1; i <= 9; i++)
    printf("%d: %d/n", i, factorial(i));
    getchar();    
    return 0;
}
int factorial(int num)
{
    if (num == 1)
        return(1);
    else
        return(num * factorial(num-1));
}

 The instance :  Integer to binary 
#include <stdio.h>
void IntToBinary(unsigned num);
int main(void)
{
    IntToBinary(255); 
    getchar();
    return 0;
}
void IntToBinary(unsigned num) {
    int i = num % 2;
    if (num > 1) IntToBinary(num / 2);
    putchar(i ? '1' : '0'); 
//    putchar('0' + i);  
}

 Analyze the recursive :
#include <stdio.h>
void prn(unsigned n);
int main(void)
{
    prn(1);
    getchar();
    return 0;
}
void prn(unsigned n) {
    printf("%d: %p/n", n, &n);  
    if (n < 4) 
        prn(n+1);               
    printf("%d: %p/n", n, &n);  
}

Example output effect diagram:

Analysis:
The program runs to A and outputs the first line.
So n is equal to 1, that satisfies < Condition of 4, continue to execute B to start the self-invocation (then will output the second line); Note that statement C has yet to be executed at n=1.
. And so on, all the way to n equals 4, A can execute, but B can't because it doesn't satisfy this condition; And finally, at n equals 4, we get to execute C.
But at this time, there are four functions in memory waiting to return (when n=1, 2, 3, 4, respectively), let's call it f1, f2, f3, f4.
F4 execute C output the fifth line, function return, return to f3(n=3), f3 can continue to execute C, output the sixth line.
F3 - > F2 - > I'm going to continue with C, and I'm going to print out the seventh row.
F2 - > F1 - > Continue C, output line 8, done!

So recursive functions are still memory intensive (sometimes not as efficient as using loops), but they are clever.