Recursion is what? Recursion in programming (examples)

Recursions are interesting events in themselves, but in programming they are of particular importance in individual cases. For the first time encountering them, quite a significant number of people have problems with their understanding. This is due to the huge field of potential application of the term itself, depending on the context in which "recursion" is used. But you can hope that this article will help to avoid a possible misunderstanding or misunderstanding.

What is "recursion" in general?

The word "recursion" has a whole range of values that depend on the area in which it is applied. The universal notation is this: recursions are definitions, images, descriptions of objects or processes in the objects themselves. They are possible only in those cases when the object is a part of itself. In their own way define the recursion of mathematics, physics, programming and a number of other scientific disciplines. Practical application, she found in the work of information systems and physical experiments.

What do you mean by recursion in programming?

Recursive situations, or recursion in programming, are the moments when the procedure or function of the program calls itself. However strange it may sound for those who started learning programming, there is nothing strange about it. Remember that recursion is not difficult, and in some cases they replace cycles. If a computer correctly assigns a procedure or function call, it simply starts executing it.

The recursion can be finite or infinite. In order for the former to stop calling itself, there must also be conditions for termination. This can be a decrease in the value of the variable and when a certain value is reached, call stop and program termination / transition to the subsequent code, depending on the needs to achieve certain goals. Under infinite recursion, it is meant that it will be called while the computer or program in which it is running is running.

It is also possible to organize complex recursion using two functions. Let's say there are A and B. A function has a call in its code B, 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 reading these lines studied the program cycles, then he probably already noticed the similarity between them and recursion. In general, they can actually perform similar or identical tasks. With the help of recursion it is convenient to make an imitation of the work of the cycle. This is especially useful where the cycles themselves are not very convenient. The scheme of software implementation does not differ much from different high-level programming languages. But still the recursion in "Pascal" and the recursion in C or another language has its own peculiarities. It can be successfully implemented in low-level languages like "Assembler", but this is more problematic and time-consuming.

Trees of recursion

What is a "tree" in programming? This is a finite set consisting of at least one node that:

1. It has an initial special node, which is called the root of the whole tree.
2. The remaining nodes are in a quantity different from zero, pairwise disjoint subsets, and they are also a tree. All such forms of organization are called subtrees of the main tree.

In other words: trees contain subtrees that contain trees, but in less quantity than the previous tree. This continues until one of the nodes has the opportunity to move further, and this will indicate 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 backwards. Nodes that do not have an extension are called end nodes. For convenience of designation and for convenience, genealogical terminology (ancestors, children) is used.

Why is it used in programming?

Its use of recursion in programming has found a solution to a number of complex problems. If you only need to make one call, then it's easier to use an integration cycle, but with two or more repetitions, to avoid building a chain and make them execute as a tree, and recursive situations are applied. For a wide class of problems, the organization of the computational process in this way is the most optimal in terms of resource consumption. Thus, a recursion in Pascal or any other high-level programming language is a call to a function or procedure before the conditions are fulfilled, regardless of the number of external calls. In other words, the program can have only one access to the subroutine, but it will occur until a certain moment in advance. In a way, this is an analog of the cycle with its own specific uses.

The differences of recursion in different 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 required material. But you should always remember: if a programming language calls functions or procedures, then the recursion call is a workable thing. But its most significant differences are manifested when using low and high programming languages. Especially it concerns the possibilities of software implementation. Execution ultimately depends on what task is set, in accordance with it, recursion is written. Functions and procedures are used differently, but their goal is always the same - to force themselves to call themselves.

Recursion is easy. How to just remember the content of the article?

For beginners to understand it, 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 of achieving the goals in programming. Take two or more mirrors, set them so that all the others are displayed in one. You can see that the mirrors display themselves repeatedly, creating an effect of infinity. Here recursions are, figuratively speaking, reflections (there will be many of them). As you can see, it is easy to understand, there would be a desire. And by studying programming materials, you can further understand that recursion is also a very easy task.