Hello everyone from CSDN, today I will bring you knowledge about function recursion in C language. This piece of knowledge is a little difficult to understand, but it is also really easy to use!
Without further ado, let’s get started with today’s content!
Table of Contents
1. Function recursion
1.1 What is recursion?
1.2 Two necessary conditions for recursion
1.3 Recursive example exercises
2. Function iteration
2.1 What is iteration
2.2 Recursion and iteration examples
2.2.1 Find the nth Fibonacci number
2.2.2 Implementing the factorial of n
3. Summary
1. Function recursion
1.1 What is recursion?
Recursion is a programming technique in which a program calls itself. It is also an algorithm 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 converts a large and complex program into a program. The problem is converted layer by layer into a smaller problem similar to the original problem to solve. In this way, only a small amount of programs can be used to describe the multiple repeated calculations required to solve the problem, greatly reducing the amount of program code. .
Recursive way of thinking: reduce the big to the small
1.2 Two necessary conditions for recursion
·Be sure to set restrictions when using recursion. When this restriction is met, the recursion will no longer continue;
·After each recursive call, it gets closer and closer to this limit.
1.3 Recursive Example Exercise
1. Receive an unsigned integer value and print each bit of it in sequence
For example: enter 1234 to print 1 2 3 4
The code is implemented as follows:
#include<stdio.h>
void print(int n)
{
if (n > 9)
{
print(n/10);
}
printf("%d ", n % 10);
}
int main()
{
int num = 0;
scanf("%d", & amp;num);
print(num);
return 0;
}
Let’s take a look at the results after entering 1234:
As you can see, the running results meet our needs. Now let’s read this code together and see where the recursion of the function is reflected:
We use scanf in the main function to input and assign the defined num variable, and call the print function to pass the value of num to print. After completing the writing of the main function, we return to the front of the main function (after the function is first declared (defined) Use) to start the implementation of the print function;
Here the implementation of the print function is explained to everyone through drawing (very important!!!):
2. Iteration of function
2.1 What is iteration
Iteration is a function that uses its own existing variables to calculate the new variables it needs. There is a certain difference between iteration and recursion directly calling itself. The two can be converted into each other in some cases. In the same situation, these two methods give priority to iteration. , because recursion can easily cause stack overflow, let’s use two examples to feel the difference between iteration and recursion.
2.2 Recursion and Iteration Examples
2.2.1 Find the nth Fibonacci number
The Fibonacci sequence is a special sequence. Starting from the third item, each item is the sum of the previous two items.
1,1,2,3,5,8,…,(n-2),(n-1),(n-2) + (n-1)
Now let’s implement it recursively:
#include<stdio.h>
//Recursive implementation to find the nth Fibonacci number
int fib(int n)
{
if (n <= 2)
return 1;
else
return fib(n - 2) + fib(n - 1);
}
int main()
{
int n = 0;
scanf("%d", & amp;n);
printf("%d", fib(n));
return 0;
}
But in fact, using recursion to find the nth Fibonacci number will cause a lot of repeated calculations. We can see it by drawing a picture:
Suppose we ask for the 50th Fibonacci number:
Then you have to call the fib function to find the 49th and 48th. To find the 49th and 48th, you have to call the fib function again to find the 48th, 47th, and 46th. Among them, the 47th is called twice, and the more you go The more repeated calculations there are, this will waste memory space and may cause stack overflow.
In order to let everyone feel more clearly the number of times the fib function needs to be called to find the nth Fibonacci number, we will improve it on the basis of the original code:
#include<stdio.h>
int count = 0;
int fib(int n)
{
//What is calculated here is how many times the third Fibonacci number is repeatedly calculated.
if(n==3)
count + + ;
if (n <= 2)
return 1;
else
return fib(n - 2) + fib(n - 1);
}
int main()
{
int n = 0;
scanf("%d", & amp;n);
/*printf("%d\
", fib(n));*/
printf("%d", count);
return 0;
}
Let’s find the 40th Fibonacci number and run it to see what the value of count is:
As you can see, the value of count is as high as 39088169, which means that the third Fibonacci number has been repeatedly calculated 39088169 times.
In order to avoid this unnecessary large number of repeated calculations, we improved the code in a non-recursive form, that is, iteration. The code is implemented as follows:
#include<stdio.h>
int fib(int n)
{
int result;
int pre_result;
int next_older_result;
result = pre_result = 1;
while (n > 2)
{
n--;
next_older_result = pre_result;
pre_result = result;
result = pre_result + next_older_result;
}
return result;
}
int main()
{
int n = 0;
scanf("%d", & amp;n);
int ret = fib(n);
printf("%d", ret);
return 0;
}
It can be seen that in the fib function, the program continuously uses two known variables to find the third required variable through the while loop. This method reduces a lot of repeated calculations than directly calling the function itself (that is, recursion).
2.2.2 Realizing the factorial of n
#include<stdio.h>
//Recursive implementation
int factorial(int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n - 1);
}
//Iterative implementation
int factorial(int n)
{
int result = 1;
while (n > 1)
{
result *= n;
n--;
}
return result;
}
int main()
{
int n = 0;
scanf("%d", & amp;n);
printf("%d", factorial(n));
return 0;
}
The same is true for realizing the factorial of n and finding the nth Fibonacci number. You can explore on your own how much repeated calculations will be caused by using recursion to find the factorial of n.
3. Summary
We need to know that the space allocated by the system to the program is limited. If an infinite loop or infinite recursion occurs, it may cause the system to continuously open up stack space and eventually exhaust the stack space, causing stack overflow.
Many problems are explained in the form of recursion, which will make the problem clearer and easier to understand, but iterative implementation of these problems is often more efficient than recursive implementation, but similarly, the code of iterative implementation is not as easy to understand as recursive.
When iteration can be used, try not to use recursion, unless the iterative implementation of the problem is very complex, then the simplicity of the recursive implementation is enough to make up for a series of problems it generates when running.
That’s it for this article. Regarding the knowledge of recursion and iteration, you still need to find more questions to practice. Although recursion is good, don’t use it often.
The next article will explain to you the Tower of Hanoi problem and the frog jumping problem about recursive applications to help you better understand the knowledge of recursion.
If you think this article is helpful to you, please move your little hand and give me a like. Your like is the motivation for my creation!