Tips: When you see this prompt, it indicates that the current article has been migrated from the original emlog blog system. The publication date of the article is quite old, and the formatting and content may not be complete. Thank you for your understanding.
What is Recursion?
Date: 2017-8-9 A Jue Chatting and Discussing Views: 1616 Comments: 5
Image source from the internet
At first, you must feel that reading this sentence is quite convoluted and difficult.
In fact, it becomes very simple when you read it recursively:
Recursion must have an endpoint (little carp)
When recursion has not yet reached the endpoint, the function will repeatedly call itself.
Obviously, outputting the phrase "my little carp" is the termination condition of the recursion.
So, writing it in code would be:
Currently, the most appropriate metaphor I have found for recursion is looking up a word in a dictionary. The dictionary we use is itself recursive; to explain a word, more words are needed. When you look up a word and find that a word in its explanation is still not understood, you start looking up this second word. Unfortunately, there is still an unfamiliar word in the second word, so you look up a third word, and so on, until you find a word whose explanation you completely understand. Then recursion reaches its end, and you start to backtrack, gradually understanding each word you looked up previously, until you finally understand the meaning of the original word...
After reading many answers above, most focus on describing
recursion
phenomena, but do not explain why recursion is used and what the essence of recursive thinking is. Recently, I happened to read some materials and tried to organize my thoughts. If there are any mistakes, please feel free to correct me.
- What is recursion?
Wiki [1]: Recursion is the process of repeating items in a self-similar way.Specifically in computing [2]:
Recursion (English: Recursion), also translated as recursive return , refers to the method of using the function itself in the definition of the function in mathematics and computer science.
The English word Recursion etymologically breaks down to "re- (again)" + "curs- (come, happen)", which means to occur repeatedly or to reappear. The corresponding Chinese translation "递归" expresses two meanings: "递" + "归". These two meanings encapsulate the essence of recursive thinking. From this perspective, the Chinese translation is actually more expressive.
2. Difference from loops
Looking at the above wiki definition, it seems very similar to what is usually referred to as an infinite loop. What is the difference?Recursion is dynamic within stillness, with both going and returning.
A loop is static in motion, with only going and no returning.
For example, if you are given a key and you stand in front of a door, asking how many doors you can open with this key.
Recursion: You open the door in front of you and see another door inside (this door may be the same size as the previous one (still), or it may be smaller (dynamic)). You walk over, find that the key in your hand can still open it, you push the door open, and discover another door inside. You continue to open doors... After several times, you open a door in front of you and find only one room with no more doors. You start to return, counting each room you pass, and when you reach the entrance, you can tell how many doors you opened with this key.
Loop: You open the door in front of you and see another door inside (this door may be the same size as the previous one (still), or it may be smaller (dynamic)). You walk over, find that the key in your hand can still open it, you push the door open, and discover another door inside (if the previous door was the same, this door is also the same; if the second door is smaller than the first, this door is also smaller than the second (static and dynamic as one, either no change or the same change)). You continue to open this door... and keep going like this. The person at the entrance is always waiting for you to return and tell them the answer.
3. Recursive thinking
Recursion involves both going (going) and returning (coming back).
Specifically, why can there be "going"?
This requires that the recursive problem can be answered using the same problem-solving approach for similar but slightly different problems (the key in the above example can open the locks on the doors behind).
Why can there be "returning"?
This requires that these problems continuously progress from large to small, from near to far, and there will be an endpoint, a critical point, a baseline, a point where you do not need to go further into smaller or more distant areas, and then from that point, you start to return to the origin.
The basic idea of recursion is to transform large-scale problems into smaller, similar subproblems for resolution . In function implementation, because the method for solving large problems and small problems is often the same, it leads to the situation where the function calls itself. Additionally, this problem-solving function must have a clear termination condition , so that infinite recursion does not occur.
4. When is recursion needed?
When the definition of some problems is itself recursive, it is most suitable to use recursion to solve them.
For computer science students, the most familiar definition is that of a tree [4,5]. There are also definitions like factorial, Fibonacci sequence [6], etc. Using recursion to solve these problems often resolves seemingly "daunting" issues in just a few lines of code. Of course, the performance issues of recursion are another matter; stack allocation and function call costs are considerations in practical engineering. But for now, if we are just discussing the idea of recursion, let's set those aside and appreciate the beauty of recursion.
Netizen Comments:
Railgun 丶 Infinite 2 years ago (2019-03-14)
Using recursion for Fibonacci will definitely cause a stack overflow and is very slow. All recursion has its non-recursive implementation (though some may be faster than others). For functions whose output values only depend on parameters, like Fibonacci, memoization should be used...
However, sometimes iterative methods are really faster than recursion~ (runs away)
A Jue 2 years ago (2019-03-14)
@Railgun 丶 Infinite: College students are different [#aru_9]
@A Jue: But I might not even get to college after high school Orz
@Railgun 丶 Infinite: You guessed wrong this time QAQ
Tianjin Website Construction 4 years ago (2017-08-15)
The article is quite good, thank you to the blogger.