Recursions are interesting events in their own right, but in programming they are of particular importance in individual cases. When first encountering them, a fairly significant number of people have problems understanding them. This is due to the huge field of potential application of the term itself, depending on the context in which “recursion” is used. But one can hope that this article will help to avoid a possible misunderstanding or misunderstanding.
What is recursion in general?
The word "recursion" has a range of meanings that depend on the area in which it is applied. The universal designation is as follows: recursions are definitions, images, descriptions of objects or processes in the objects themselves. They are possible only in those cases when the object is part of itself. Mathematics, physics, programming, and a number of other scientific disciplines determine recursion in their own way. She found practical application in the work of information systems and physical experiments.
What is meant by recursion in programming?
Recursive situations, or recursion in programming, are the moments when a procedure or function of a program calls itself. No matter how strange it is for those who began to study programming, this may sound, there is nothing strange here. It should be remembered that recursion is not difficult, and in some cases they replace cycles. If the computer correctly sets the call to the procedure or function, it simply starts to execute it.
Recursion can be finite or infinite. In order for the first to cease to cause itself, it must also contain the conditions for termination. This can be a decrease in the value of the variable and upon reaching a certain value, the call is stopped and the program is completed / transition to the next code, depending on the needs, to achieve certain goals. By infinite recursion, it is meant that it will be called while the computer or the program in which it works is running.
It is also possible to organize complex recursion using two functions. Suppose there are A and B. Function A has a call B in its code, and B, in turn, tells the computer to perform A. Complex recursions are a way out of a number of complex logical situations for computer logic.
If the reader of these lines studied program cycles, then he probably already noticed a similarity between them and recursion. In general, they can actually perform similar or identical tasks. Using recursion, it’s convenient to simulate a loop. This is especially useful where the cycles themselves are not very convenient to use. The scheme of software implementation does not differ much between different high-level programming languages. But still, recursion in Pascal and recursion in C or another language has its own characteristics. It can be successfully implemented in low-level languages like Assembler, but it is more problematic and time-consuming.
Recursion trees
What is a tree in programming? This is a finite set consisting of at least one node, which:
- It has an initial special node, which is called the root of the whole tree.
- The remaining nodes are in numbers other than zero, pairwise disjoint subsets, while they are also a tree. All such forms of organization are called subtrees of the main tree.
In other words: trees contain subtrees that still contain trees, but in less quantity than the previous tree. This continues until in one of the nodes there is no opportunity to move further, and this will mark the end of the recursion. There is one more nuance about the schematic image: ordinary trees grow from bottom to top, and in programming they are drawn the other way around. Nodes that have no continuation are called end nodes. For the convenience of notation and for convenience, genealogical terminology is used (ancestors, children).
Why is it used in programming?
Recursion in programming found its application in solving a number of complex problems. If you need to make only one call, it is easier to use the integration cycle, but with two or more repetitions, in order to avoid constructing the chain and making them run as a tree, recursive situations are applied. For a wide class of problems, the organization of the computing process in this way is the most optimal from the point of view of resource consumption. So, recursion in Pascal or any other high-level programming language is a call to a function or procedure before conditions are met, regardless of the number of external calls. In other words, there can be only one call to a subprogram in a program, but it will occur until a certain point in advance. In a way, this is an analogue of the cycle with its own specific usage.
Differences in recursion in various programming languages
Despite the general implementation scheme and specific application in each individual case, recursion in programming has its own characteristics. This can lead to difficulty while searching for the necessary material. But you should always remember: if a programming language calls functions or procedures, then calling recursion is a feasible task. But its most significant differences are manifested when using low and high programming languages. This is especially true for software implementation capabilities. Execution ultimately depends on what task is set, and recursion is written in accordance with it. The functions and procedures used are different, but their goal is always the same - to force themselves to be called.
Recursion is easy. How to just remember the content of an article?
For beginners, understanding it may be difficult at first, so we need examples of recursion, or at least one. Therefore, we should give a small example from everyday life, which will help to understand the very essence of this mechanism for achieving goals in programming. Take two or more mirrors, place them so that all the others are displayed in one. You can see that the mirrors display themselves repeatedly, creating the effect of infinity. Here recursions are, figuratively speaking, reflections (there will be many of them). As you can see, it’s easy to understand if there was a desire. And by studying programming materials, you can further understand that recursion is also a very easy task.