Recursion is what? Recursion in programming (examples)

Recursions are interesting events forthemselves, but in programming they are of particular importance in individual cases. For the first time encountering them, quite a considerable 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 one can hope that this article will help to avoid a possible misunderstanding or misunderstanding.

What is "recursion" in general?

recursion is
The word "recursion" has a whole range of meanings,which 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, mathematics, physics, programming and a number of other scientific disciplines define recursion. Practical application, she found in the work of information systems and physical experiments.

What do you mean by recursion in programming?

recursion in pascal
Recursive situations, or recursion inprogramming, are called the moments when the procedure or function of the program calls itself. As strange as it may seem for those who started learning programming, it does not sound strange. Remember that recursion is not difficult, and in some cases they replace cycles. If the 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. By 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 withusing 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 is reading the programcycles, 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

recursion in programming
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: The trees contain subtrees that contain trees, but in a smaller amount than the previous tree. This continues until one of the nodes has the opportunity to move forward, and this will indicate the end of the recursion. There is one more nuance about the schematic image: ordinary trees grow from the bottom up, 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?

recursion function
Its use of recursion in programming has foundin solving 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 from the point of view of resource consumption. Thus, a recursion in Pascal or any other high-level programming language is a function or procedure call before the conditions are fulfilled, regardless of the number of external calls. In other words, there can be only one access to the subroutine in the program, but it will occur until a certain moment in advance. In a way, this is an analog of the cycle with its own specific use.

The differences of recursion in different programming languages

Despite the overall implementation scheme and the specificapplication in each case, recursion in programming has its own characteristics. This can lead to difficulty while searching for the required material. But we 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?

examples of recursion
For beginners to understand it, maybe at firstIt is difficult, therefore, 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.