C language explanation series -- understanding of functions (5) function recursion and iteration

Function recursion

What is function recursion ？ Functions call their own programming skills, which we call recursion , Function recursion usually transforms a large and complex problem layer by layer into a smaller problem similar to the original problem to solve , Recursive strategy only needs a few programs to describe the multiple repeated calculations needed in the problem-solving process , Greatly reduces the amount of program code . The main way to think about recursion is Simplify complex problems , Turn the big thing into a small one .
Let's demonstrate function recursion in a piece of code

#include<stdio.h>
void print(int n)
{
    
	if (n > 9)
	{
    
		print(n / 10);
	}
	printf("%d ", n % 10);
}

int main()
{
    
	int num = 1234;
	print(num);
	return 0;
}

In the above code, we use recursive method , Print each bit of an integer value in sequence , So how to realize it specifically , We draw pictures , Let us have a more intuitive experience .

We say that function recursion is divided into two parts , First, we need to recurse, and then we have to return , Like the code above, we will num Pass the value of to the parameter n, Then judge if n>9 We need to call the function again and put the parameters n except 10, until n<9 When we print n%10, This process is called recursive process , Then they are returning , After one execution, return to the upper level function to complete the execution of this level function , Return to the previous function , Finally, back to our main function , end of execution .
Through the process of this code, we find , Function recursion must have two conditions

1. Function recursion requires constraints , When this constraint is met , Recursion will not continue
2. After each recursive call, it gets closer and closer to this limit

To sum up , The meaning of this restriction lies in , That is, recursive function calls cannot be made infinitely , There must be a constraint . What would happen without this constraint ？

As shown in the figure, when we remove the restriction of function recursion , The compiler will prompt us that there may be stack overflow, which is what we call dead recursion , Because every time we call a function, we will open up a memory space in the stack , When we recurse infinitely, we will always open up new memory space , And the space of our stack area is limited , So when recursion reaches a certain limit, it will appear Stack overflow—— Stack overflow .

Iteration of function

We say that loop is actually an iterative way , Then why do we already have the programming skills of recursion, which can simplify the code , There are still iterations ？ What's the use ？ We look for the answer in the code .
Please n Fibonacci Numbers , Fibonacci number is 1 1 2 3 5 8 13 21 34 55… The number of such permutations , We can see that starting from the third number , His value is the sum of the first two numbers .

int fib(int n)
{
    
	if (n <= 2)
		return 1;
	else
		return fib(n - 1) + fib(n - 2);
}
int main()
{
    
	int n = 0;
	scanf("%d", &n);
	int num = fib(n);
	printf("%d ", num);
}

Through our analysis, we can easily write code using function recursion , It also looks very simple , There's no problem running , But when we want to ask for the first 50 When we find Fibonacci number

No number is output , That's because our code is wrong , It's not , The reason why there is no output is , We do too much double counting , It's time consuming , Believe it or not, we can calculate how many times the third Fibonacci number has been calculated

When we calculate the number 40 A Fibonacci number , The third Fibonacci number has been calculated 39088169 Time , Then how can we solve such a problem , We optimize the code .

int fib(int n)
{
    
	int c = 1;
	int a = 1;
	int b = 1;
	while (n > 2)
	{
    
		n -= 1;
		c = a + b;
		a = b;
		b = c;
	}
	return c;
	
}
int main()
{
    
	int n = 0;
	scanf("%d", &n);
	int num = fib(n);
	printf("%d \n", num);

}

We just replace recursion with iteration , It can also meet our needs

Let's calculate again 50 Fibonacci Numbers

We can see that the results are output soon , The output result is incorrect because the number is too large .
To sum up ：

1. Through the above cases, we can find , Recursion can explain the problem well , Especially those with formula type , It is clearer than non recursive
2. However, the iterative implementation of these problems is often more efficient than recursive implementation
3. When a problem is quite complex , When it is difficult to implement iteratively , At this point, the simplicity of recursive implementation can compensate for the runtime opening caused by it
pin

So what specific programming skills to use depends on our actual needs , Well, speaking of the basic knowledge of recursion and iteration , I have shared with you , Then for better understanding , I will share two typical examples of function recursion .