Pictures come from the Internet
At first glance, you must feel that reading this sentence is confusing and difficult.
In fact, it is very simple if you use recursion to read:
Recursion must have an end point (little carp)
When the recursion has not reached the end point, the function will call itself repeatedly.
Obviously, outputting the sentence “My little carp” is the recursive termination condition.
Then the code written is:
#include <stdio.h> void Recursion(int depth){ printf(“holding”); if (!depth) printf(“My little carp”); else Recursion(–depth); printf(“我”); } int main(){ printf(“I was so scared that I hugged\n”); Recursion(2); putchar(’\n’); }
The most appropriate metaphor for recursion that I have found so far is to look it up in a dictionary. The dictionary we use is itself recursive. In order to explain a word, more words need to be used. When you look up a word, you find that you still don’t understand a certain word in the explanation of the word, so you start to look up the second word. Unfortunately, there is still a word in the second word that you don’t understand, so you look up the third word, and keep looking until there is a word whose explanation you can completely understand. Then the recursion comes to an end, and then you start to step back and understand each word you looked up before, and finally you understand the meaning of the first word. . .
The arrow lines represent the actual steps of the program.
After reading many answers upstairs, most of them focus on describing the phenomenon of recursion, but do not explain why recursion is used or what the idea of recursion is. I happened to read something a while ago and tried to sort it out. If there are any mistakes, please feel free to correct me.
- **What is recursion? **
1.Definition
**Wiki [1]：**Recursion is the process of repeating items in a self-similar way.
Specifically to the computer [2]:
Recursion (English: Recursion), also translated as Recursion, in mathematics and computer science, refers to the method of using the function itself in the definition of the function.
From the etymological analysis, the English Recursion is just “re- (again)” + “curs- (come, happen)”, which means to happen again and again. The corresponding Chinese translation “recursion” expresses two meanings: “recursion” + “return”. These two meanings are the essence of recursive thinking. From this perspective, the Chinese translation is more expressive.
2. Difference from loop
Just looking at the wiki definition above, it seems to be very similar to what is commonly known as an infinite loop. What is the difference between them?
Recursion is movement in stillness, going and returning.
The cycle is the consistency of movement and stillness, and there is no return.
For example, you are given a key, you stand in front of the door, and you are asked how many doors you can open with this key.
Recursion: You open the door in front of you and see another door in the room (this door may be the same size as the door opened before (quiet), or it may be smaller (moving)). You walk over and find that the key in your hand can still open it. You push the door and find that there is another door inside. You continue to open it. . . , after several times, you open a door in front of you and find that there is only one room and no door. You start walking back the same way, and every time you walk back to a room, you count once. When you reach the entrance, you can answer how many doors you opened with this key.
Loop: You open the door in front of you and see another door in the house (this door may be the same size as the door opened before (quiet), or it may be smaller (moving)). You walk over and find that the key in your hand can still open it. You push the door open and find that it is inside. There is another door, (if the previous door is the same, this door is also the same, if the second door is smaller than the first door, this door is also smaller than the second door (the movement is the same, either there is no change, or the same change)), you continue to open this door. . . , keep going like this. The person at the entrance never waits for you to come back and tell him the answer.
3. Recursive thinking
**Recursion means going (passing) and returning (returning). **
**Specifically, why can we “go”? ** This requires that the recursive problem needs to be able to use the same problem-solving ideas to answer similar but slightly different questions (the key in the above example can open the lock on the back door).
**Why can there be a “return”? ** This requires that in the process of these problems constantly moving from big to small, from near to far, there will be an end point, a critical point, a baseline, a point where you no longer need to go to smaller or farther places when you reach that point, and then start from that point and return to the original point.
The author of this blog post[3] summarizes it as:
The basic idea of recursion is to convert large-scale problems into small-scale similar sub-problems to solve. When implementing a function, because the method of solving big problems and the method of solving small problems are often the same, the function calls itself. In addition, the function that solves the problem must have an obvious end condition, so that infinite recursion will not occur.
**4. When does recursion need to be used? **
When the definition of some problems itself is in a recursive form, it is most suitable to use recursion to solve it.
Students majoring in computer science are most familiar with the definition of “tree”[4,5]. There are also some definitions, such as factorial, Fibonacci sequence [6], etc. Using recursion to solve these problems often solves some seemingly “scary” problems in just a few lines of code. Of course, recursive performance issues are another matter. Stack allocation and function call costs must be considered in specific engineering practices. But if we are just discussing recursive thoughts now, we might as well put those aside and appreciate the beauty of recursion.
-—The above are all responses from netizens