“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Recently, I want to review C language, so I will update an article about C language in nuggets every day! Freshmen who are just learning C, and those who want to review C /C++, don’t miss it! Solid foundation, slow down is fast!

What is recursion?

The programming technique by which a program calls itself is called recursion. Recursion as an algorithm is widely used in programming languages. A procedure or function in the introduction to the definition or call their own, directly or indirectly, with a kind of method, it is usually the problem of a large complex layers into a similar to the original problem of smaller problems to solve, the recursion strategy only a small number of procedures can be required to describe the problem solving process of repeatedly calculation, greatly reduces the amount of program code.

What’s good about recursion?

Two necessary conditions for recursion 1. there is a constraint condition, when this constraint condition is met, recursion will not continue. 2. Each recursive call gets closer and closer to this constraint

The importance of recursion

Recursion is a powerful descriptive tool, not an algorithm. The only thing it does is help your mind, like sometimes it's easy to construct recursions from a recursive point of view. Whether existing languages can support recursion efficiently syntactically is not a central issue. Recursive thinking is used in many interfaces of binary trees in data structuresCopy the code

When to use recursion?

1. When solving a problem, both recursion and non-recursion can be used, and there is no obvious problem, recursion is used

2. When solving a problem, recursion is easy to write, non-recursion is more complex to write, and recursion has no obvious problem, then use recursion.

3. If you use recursion to solve a problem, it is easy to write, but there are obvious problems, then do not use recursion, use a non-recursive way to solve the problem

Note: recursion cannot continue indefinitely, otherwise it will cause an infinite loop and stack overflowCopy the code

Exercises:

Practice is the sole criterion for testing truth. Let’s use recursive and non-recursive ways to see how to write each question.

1. Print each digit of a number in recursive order

//1. Print each digit of a number recursively and then split it when n is two digits. Print(1234) Print(123) Print(12) Print(1) // void Print(int n) {if (n >9) {Print(n / 10); } printf("%d ", n % 10); } int main() { int n = 0; // Enter the number to print scanf("%d", &n); Print(n); return 0; }Copy the code

Running results:

2. Print a number in reverse order recursively

void Print(int n) { if (n > 0) { printf("%d ", n % 10); n /= 10; Print(n); Print(n); Print(n); } else return; } int main() { int n = 0; // Enter the number to print scanf("%d", &n); Print(n); return 0; }Copy the code

Running results:

3. Factorial in a non-recursive way

Factorial: n! = 123… N E.g. : 3! * * = 321 = 6

What is factorial?

Factorial is a mathematical term invented by Christian Kramp (1760 ~ 1826) in 1808. The factorial of a positive integer (factorial) is the product of all positive integers less than or equal to that number, and 0 factorial is 1. The factorial of the natural number n is written as n! . This notation was introduced by Keith Karman in 1808.Copy the code
// Use recursive + non-recursive factorial // // note: negative numbers do not have factorials. // A factorial is the product of successive natural numbers from 1 to n. Symbol is: n! // So I artificially specify that when the input is negative, the output is 1 // non-recursiveCopy the code
int Fac1(int n) { int i = 0; int sum = 1; // Sum cannot be initialized to 0 because 0 times anything is 0. // I cannot start from 0. i <= n; i++) { sum *= i; } return sum; } int main() { int n = 0; scanf("%d", &n); int ret = Fac1(n); printf("%d\n", ret); return 0; }Copy the code

4. Factorial recursively

Write the code from the diagram above!

Int Fac2(int n) {return n < 1? 1 : Fac2(n - 1) * n; } int main() { int n = 0; scanf("%d", &n); int rett = Fac2(n); printf("%d\n", rett); return 0; }Copy the code
That’s all for today. Thank you for seeing us! Hope to help you! You are welcome to click on this topic and subscribe! At the same time, welcome the bigwigs to criticize and correct!