catalogue

What is recursion?

Two necessary conditions of recursion

1, Accept an integer value (unsigned) and print its bits in order.

2, Recursively find the factorial of n.

3, Recursive calculation of Fibonacci number

4, Hanoi Tower problem

5, Rewrite recursion to non recursion.

What is recursion?

The programming skill of the program calling itself is called recursion. As an algorithm, recursion is widely used in programming languages. A process or function has a method of directly or indirectly calling itself in its definition or description. It usually transforms a large and complex problem layer by layer into a smaller problem similar to the original problem to solve. The recursive strategy can describe the multiple repeated calculations required in the problem-solving process with only a small number of programs, which greatly reduces the amount of code of the program. The main way of thinking about recursion is to make big things small

Two necessary conditions of recursion

1. There is a constraint. When this constraint is met, recursion will not continue.

Get closer and closer to this limit after each call.

1, Accept an integer value (unsigned) and print its bits in order.

For example: input: 1234, output 1 2 3 4

#include<stdio.h>
int fun(int n)
{
    if(n > 9)
        {
            fun(n / 10);
        }
    printf("%d", n % 10);
       return 0;
}
int main()
{
     int num = 1234;
     print(num);
     return 0;
}

2, Recursively find the factorial of n.

#include<stdio.h>
 int fun(int n)
{
    if(1 == n)
    {
            return 1;
    }
    else
    {
        return n * fun(n -1);
    }
}
int main()
{
    int n, ret;
    scanf("%d", &n);
    ret = fun(n);
    printf("%d", ret);
    return 0;
}

3, Recursive calculation of Fibonacci number

Fibonacci sequence 1, 1, 2, 3, 5, 8... And Lucas sequence 1, 3, 4, 7, 11, 18... Have the same property: starting from the third term, each term is equal to the sum of the first two terms, which we call Fibonacci Lucas recursion. all accord with Fibonacci Lucas recursive series It is called Fibonacci Lucas sequence.

Find the nth Fibonacci number. (overflow is not considered)

#include<stdio.h>
int fun(int n)
{
    if(1 == n  || 2 == n)
        {
            return 1;
        }
    else
        {
            return fun(n -1) + fun (n - 2);
        }
}
int main()
{
    int n, ret;
    scanf("%d", &n);
    ret = fun(n);
    printf("%d", ret);
    return 0;
}

4, Hanoi Tower problem

It is said that in ancient Indian holy temples, there was A game called Hanoi. The game is on A copper plate device with three rods (numbered A, B and C). 64 gold plates are placed in order from bottom to top and from large to small in rod A (as shown in Figure 1). The goal of the game: move all the gold plates on pole A to pole C, and keep the original order. Operating rules: only one plate can be moved at A time, and the large plate is always kept under the three rods and the small plate is on the top. During the operation, the plate can be placed on any rod A, B and C.

#include<stdio.h>


int hannuota(int n, char Scr, char Dst, char Tmp)  //This function means that from seat A to seat B to seat C
{
	if (1 == n)                                        //N stands for n-storey tower
	{
		printf("%c -> %c\n", Scr, Dst);    //If there is only one floor, move directly from A to C to complete the task
	}
	else
	{
		hannuota(n - 1, Scr, Tmp, Dst);   //If there is more than one floor, the problem can be seen as moving his n-1 floor from A to B
		printf("%c -> %c\n", Scr, Dst);    //Then move the remaining floor from A to C;
		hannuota(n - 1, Tmp, Dst, Scr);  //Then move the n-1 layer from B to C and complete the task
	}                                     //The task is constantly simplified by n-1
	return 0;
}
int main()
{
	int n;
	char TA = 'A';      //ABC stands for three tables
	char TB = 'B'; 
	char TC = 'C';
	scanf("%d", &n);
	hannuota(n, 'A', 'B', 'C');
	return 0;
}

Run the program and enter 3, which means we want to move the three-story Hanoi tower. We get the moving order of the three-story Hanoi tower.  

 

5, Rewrite recursion to non recursion.

By practicing the above two questions, we find that:

When using fun # this function, if we want to calculate the 50th Fibonacci number, it takes a lot of time.

Using the fun function to find the factorial of 10000 (regardless of the correctness of the result), the program will crash.

Why?

When debugging the fun function, if your parameter is relatively large, you will report an error: ` stack overflow (stack overflow) such information. The stack space allocated by the system to the program is limited, but if there is an dead loop or (dead recursion), it may lead to the continuous development of stack space and eventually the depletion of stack space. This phenomenon is called stack overflow.

If there is such a problem, we can Use static objects instead of nonstatic local objects.

In recursive function design, static objects can be used to replace nonstatic local objects (i.e. stack objects), which can not only reduce the overhead of generating and releasing nonstatic objects during each recursive call and return, but also save the intermediate state of recursive calls and can be accessed by each call layer.