Recursion and recursive algorithms. What is recursion

From lat recursio (return). In general, this is the name for the process of repeating elements in a "self-similar way".

Matryoshka dolls are a striking example of recursion. Recursive definition: "Matryoshka is a split hollow wooden doll with a smaller matryoshka inside." Here's a recursion in Russian. And if it were not for the limit of the masters' capabilities, the ideal matryoshka would go deep into itself to the atomic level. And even deeper. It's just that Lefty didn't have a small scope of sufficient strength. The upper limit is theoretically also unlimited, but suitable size baobabs do not grow on our planet. In general, for technical reasons, the recursion should be finite.

In programming (as in mathematics), recursion is the process of a function calling itself (direct recursion), or a call from within function A of function B, which in turn contains a call to function A (indirect or mutual recursion). Of course, recursive calls must have a satisfiable termination condition, otherwise such a program will "hang" like in an infinite loop - but, unlike an infinite loop, with an infinite recursion, it will crash with a stack overflow.

Recursion example

The most boring example of recursion in mathematical programming is calculating the factorial. Let's not betray glorious traditions. For those who haven't done it yet: N! (factorial N) is the product of all natural numbers from one to N (factorial of zero is 1).
You can stupidly multiply numbers from 1 to N in a loop. Or you can construct a function factorial (n), which will contain a condition and call itself. If n is equal to one, then the function returns the value 1, otherwise it returns the value n multiplied by factorial (n-1).
PHP sketch

Function factorial ($ n) (if ($ n == 1) (return 1;) else (return intval ($ n * factorial ($ n - 1));))

Practical uses of recursion

"Well, and why is this needed here?" - an impatient young reader will ask us - "Scientific nonsense, tediousness, all sorts of factorials ... And practically what to apply this recursion to?"
“To the black eye of web programming” - we will answer without hesitation. And then we will justify it.

In fact, there are many more uses of recursion in web programming than it seems. Because recursion is perhaps the only way to traverse any tree structure, when neither its size nor the nesting depth is known in advance. By the way, the construction and traversal of graphs also cannot do without it. This is a classic, gentlemen - try in some other way to search for the files you need in the unix directory tree, and you will immediately understand that without recursion, you can go nowhere.

Try to do without it by building a sitemap with a hierarchical structure of sections in the form of nested lists. You'd rather hang yourself than build it if you don't know in advance exactly how many levels the nesting depth is limited to. And even if you know, but try to do without recursion, then instead of a simple, transparent and trouble-free function, build a bulky software "shelf on crutches". And when you've finished and wiped off your sweaty forehead, the dark truth of life will reach you: when the depth of nesting changes, your spreading structure will instantly stop working correctly. Therefore, you are unlikely to be able to apply it anywhere else.

Search engine recursion

Yes exactly. Search engines have nowhere to go from recursion either. Since the custom of measuring the authority of a site (document) by the number of links was established, search engines fell into a recursive trap, and let them wander in it forever (this is a sincere good wish of the author). The link "weight" of a site is made up of small chunks of "weight" from all those that link to it. To calculate this weight for A, referred to by B, C and D, you need to calculate their weight, which in turn is transmitted by all sorts of others, the weight of which also needs to be calculated ... and so on throughout the entire Web counted in the search engine. A completely recursive problem. And you say - a solid theory. The most that neither is real practice.

Recursive PageRank from Google

The creators of Google published their basic algorithm for calculating PageRank a long time ago. And no matter how it has changed since then, no matter how much it has been supplemented with improvements, the basis remains the same. You can't know how much PageRank page B is linking to page A until we've calculated how much PageRank Page B got from all the other pages that linked to it, and that can't be known until we calculate the PageRank of those pages ... continue? Probably no longer necessary. It is again She - Her Majesty Recursion .

Hello Habrahabr!

This article will discuss recursion problems and how to solve them.

Briefly about recursion

Recursion is a fairly common phenomenon that occurs not only in the fields of science, but also in everyday life. For example, the Droste effect, the Sierpinski triangle, etc. One of the options to see the recursion is to point the webcam at the computer screen, of course, after turning it on. Thus, the camera will record the image of the computer screen, and display it on this screen, something like a closed loop will turn out. As a result, we will observe something that looks like a tunnel.

In programming, recursion is closely related to functions, more precisely, thanks to functions in programming, there is such a thing as recursion or recursive function. In simple words, recursion is the definition of a part of a function (method) through itself, that is, it is a function that calls itself, directly (in its body) or indirectly (through another function).

A lot has been said about recursion. Here are some good resources:

• Recursion and recursive tasks. Areas of Application of Recursion

It is assumed that the reader is theoretically familiar with recursion and knows what it is. In this article, we will pay more attention to recursion problems.

Tasks

When learning recursion, the most efficient way to understand recursion is problem solving.

How to solve recursion problems?

First of all, you need to understand that recursion is a kind of brute force. Generally speaking, everything that is solved iteratively can be solved recursively, that is, using a recursive function.

from the net

Any algorithm implemented in a recursive form can be rewritten in an iterative form and vice versa. The question remains whether this is necessary, and how effective it will be.

The following arguments can be used to justify this.

For a start, remember the definition of recursion and iteration. Recursion is a way of organizing data processing in which a program calls itself directly, or with the help of other programs. Iteration is a way of organizing data processing in which certain actions are repeated many times without leading to recursive program calls.

After that, we can conclude that they are mutually interchangeable, but not always with the same resource and speed costs. For justification, you can give the following example: there is a function in which, to organize a certain algorithm, there is a cycle that performs a sequence of actions depending on the current value of the counter (it may not depend on it). Once there is a cycle, it means that a sequence of actions is repeated in the body - iterations of the cycle. You can move operations into a separate subroutine and pass the counter value to it, if any. Upon completion of the execution of the subroutine, we check the conditions for the execution of the cycle, and if it is true, we proceed to a new call of the subroutine, if false, we terminate the execution. Because We placed the entire contents of the loop in a subroutine, which means that the condition for the execution of the loop is also placed in a subroutine, and it can be obtained through the return value of the function, parameters passed by reference or pointer to the subroutine, as well as global variables. Further, it is easy to show that the call of this subroutine from the loop can be easily converted into a call, or not a call (return of a value or simply completion of work) of a subroutine from itself, guided by any conditions (those that were previously in the loop condition). Now, if you look at our abstract program, it looks something like passing values ​​to a subroutine and using them, which the subroutine will change upon completion, i.e. we replaced the iterative loop with a recursive subroutine call to solve this algorithm.

The task of converting recursion to an iterative approach is symmetric.

Summing up, we can express the following thoughts: for each approach there is a class of problems, which is determined by the specific requirements for a specific problem.

You can get acquainted with this in more detail.

Just like iteration (loop), recursion must have a stop condition - Base case (otherwise, just like a loop, the recursion will run forever - infinite). This condition is the case to which the recursion goes (step of the recursion). At each step, the recursive function is called until the next call triggers the base condition and stops the recursion (or rather, returns to the last call of the function). The whole solution comes down to solving the base case. In the case when a recursive function is called to solve a complex problem (not a basic case), a number of recursive calls or steps are performed in order to reduce the problem to a simpler one. And so on until we get a basic solution.

So the recursive function consists of

• Stop condition or Base case
• Continuation condition or Recursion step is a way of reducing a task to simpler ones.

Let's consider this using the example of finding the factorial:

Public class Solution (public static int recursion (int n) (// exit condition // Base case // when to stop repeating recursion? If (n == 1) (return 1;) // Recursion step / recursive condition return recursion ( n - 1) * n;) public static void main (String args) (System.out.println (recursion (5)); // recursive function call))

Here the Basic condition is the condition when n = 1. Since we know that 1! = 1 and to calculate 1! we don't need anything. To calculate 2! we can use 1 !, i.e. 2! = 1! * 2. To calculate 3! we need 2! * 3 ... To calculate n! we need (n-1)! * n. This is the step of the recursion. In other words, to get the value of the factorial from the number n, it is enough to multiply the value of the factorial from the previous number by n.

Tags:

• recursion
• tasks
• java

Add tags

Recursion is when a subroutine calls itself. When faced with such an algorithmic construction for the first time, most people experience certain difficulties, but a little practice and recursion will become an understandable and very useful tool in your programming arsenal.

1. The essence of recursion

A procedure or function can contain calls to other procedures or functions. Including the procedure can call itself. There is no paradox here - the computer only sequentially executes the commands it encounters in the program, and if it encounters a procedure call, it simply starts executing this procedure. It doesn't matter which procedure gave the command to do it.

An example of a recursive procedure:

Procedure Rec (a: integer); begin if a>

Consider what happens if a call is placed in the main program, for example, of the form Rec (3). Below is a block diagram showing the sequence of execution of statements.

Rice. 1. Block diagram of the recursive procedure.

The Rec procedure is called with the a = 3 parameter. It contains the Rec call with the a = 2 parameter. The previous call has not finished yet, so you can imagine that another procedure is being created and the first one does not finish its work before it finishes its work. The call process ends when parameter a = 0. At this moment, 4 instances of the procedure are executed simultaneously. The number of simultaneously performed procedures is called depth of recursion.

The fourth called procedure (Rec (0)) will print the number 0 and finish its work. After that, control returns to the procedure that called it (Rec (1)) and the number 1 is printed. And so on until all procedures are completed. The initial call will print four numbers: 0, 1, 2, 3.

Another visual image of what is happening is shown in Fig. 2.

Rice. 2. Executing the Rec procedure with parameter 3 consists of executing the Rec procedure with parameter 2 and printing the number 3. In turn, executing the Rec procedure with parameter 2 consists of executing the Rec procedure with parameter 1 and printing the number 2. And so on.

As a stand-alone exercise, consider what you get when you call Rec (4). Also, think about what happens when you call the procedure Rec2 (4) described below, where the statements are swapped.

Procedure Rec2 (a: integer); begin writeln (a); if a> 0 then Rec2 (a-1); end;

Note that in the above examples, the recursive call is inside a conditional statement. This is a prerequisite for the recursion to end someday. Also note that the procedure calls itself with a different parameter than the one with which it was called. If the procedure does not use global variables, then this is also necessary so that the recursion does not continue indefinitely.

A slightly more complex scheme is possible: function A calls function B, and that in turn calls A. This is called complex recursion... In this case, it turns out that the first described procedure must call the one not yet described. For this to be possible, you need to use.

Procedure A (n: integer); (Forward description (title) of the first procedure) procedure B (n: integer); (Forwarding description of the second procedure) procedure A (n: integer); (Complete description of procedure A) begin writeln (n); B (n-1); end; procedure B (n: integer); (Complete description of procedure B) begin writeln (n); if n

The forward description of procedure B allows it to be called from procedure A. The forward description of procedure A is not required in this example and is added for aesthetic reasons.

If an ordinary recursion can be likened to an ouroboros (Fig. 3), then the image of a complex recursion can be drawn from a well-known children's poem, where "Wolves from a fright, ate each other." Imagine two wolves eating each other, and you understand complex recursion.

Rice. 3. Ouroboros is a snake that devours its own tail. Drawing from the alchemical treatise "Synosius" by Theodore Pelekanos (1478).

Rice. 4. Complex recursion.

3. Simulating a loop using recursion

If a procedure calls itself, then, in fact, this leads to the repeated execution of the instructions contained in it, which is similar to the work of a loop. Some programming languages ​​do not contain looping constructs at all, leaving programmers to organize repetitions using recursion (for example, Prolog, where recursion is the main programming technique).

For example, let's simulate the work of the for loop. To do this, we need a step counter variable, which can be implemented, for example, as a procedure parameter.

Example 1.

Procedure LoopImitation (i, n: integer); (The first parameter is the step counter, the second parameter is the total number of steps) begin writeln ("Hello N", i); // Here are any instructions that will be repeated if i

The result of a call like LoopImitation (1, 10) will execute the instructions ten times with the counter changing from 1 to 10. In this case, it will print:

Hello N 1
Hello N 2
…
Hello N 10

In general, it is not difficult to see that the parameters of the procedure are the limits of changing the values ​​of the counter.

You can swap the recursive call and the statements to be repeated, as in the following example.

Example 2.

Procedure LoopImitation2 (i, n: integer); begin if i

In this case, the procedure will be called recursively before the instructions start executing. A new instance of the procedure will also, first of all, call another instance, and so on, until we reach the maximum counter value. Only after that the last of the called procedures will execute its instructions, then the penultimate will execute its instructions, etc. Calling LoopImitation2 (1, 10) will print the greetings in reverse order:

Hello N 10
…
Hello N 1

If we imagine a chain of recursively called procedures, then in example 1 we go through it from earlier called procedures to later ones. In example 2, vice versa, from later to early.

Finally, a recursive call can be placed between two blocks of instructions. For instance:

Procedure LoopImitation3 (i, n: integer); begin writeln ("Hello N", i); (The first block of instructions may be located here) if i

Here, first, instructions from the first block are sequentially executed, then in reverse order, instructions from the second block. When we call LoopImitation3 (1, 10), we get:

Hello N 1
…
Hello N 10
Hello N 10
…
Hello N 1

It would take two loops at once to do the same without recursion.

The fact that the execution of parts of the same procedure is spaced out in time can be used. For instance:

Example 3: Converting a number to the binary system.

As you know, getting the digits of a binary number occurs by dividing with a remainder by the base of the number system 2. If there is a number, then its last digit in its binary representation is

Taking the whole part from division by 2:

we get a number that has the same binary representation, but without the last digit. Thus, it is enough to repeat the above two operations until the next division field we get the integer part equal to 0. Without recursion, it will look like this:

While x> 0 do begin c: = x mod 2; x: = x div 2; write (c); end;

The problem here is that the digits of the binary representation are calculated in reverse order (last ones first). To print a number in normal form, you will have to remember all the numbers in the array elements and display them in a separate loop.

Recursion makes it easy to get the output in the correct order without the array and the second loop. Namely:

Procedure BinaryRepresentation (x: integer); var c, x: integer; begin (First block. Executed in the order of procedure calls) c: = x mod 2; x: = x div 2; (Recursive call) if x> 0 then BinaryRepresentation (x); (Second block. Executed in reverse order) write (c); end;

Generally speaking, we didn’t get any winnings. The numbers of the binary representation are stored in local variables, which are different for each running instance of the recursive procedure. That is, it was not possible to save memory. On the contrary, we waste extra memory storing many local variables x. Nevertheless, such a solution seems to me beautiful.

4. Recurrence relations. Recursion and iteration

They say that a sequence of vectors is given by a recurrence relation if an initial vector and a functional dependence of the next vector on the previous one are given

A simple example of a quantity computed using recurrence relations is the factorial

The next factorial can be calculated from the previous one as:

Having entered the designation, we get the ratio:

The vectors from formula (1) can be interpreted as sets of variable values. Then the calculation of the required element of the sequence will consist in repeated updating of their values. Specifically for the factorial:

X: = 1; for i: = 2 to n do x: = x * i; writeln (x);

Each such update (x: = x * i) is called iteration, and the process of repeating iterations is iterating.

Note, however, that relation (1) is a purely recursive definition of a sequence and the calculation of the nth element is in fact multiple taking of the function f from itself:

In particular, for the factorial, you can write:

Function Factorial (n: integer): integer; begin if n> 1 then Factorial: = n * Factorial (n-1) else Factorial: = 1; end;

It should be understood that calling functions entails some additional overhead, so the first option for calculating the factorial will be somewhat faster. In general, iterative solutions work faster than recursive solutions.

Before moving on to situations where recursion is useful, consider another example where you shouldn't use it.

Consider a special case of recurrence relations, when the next value in the sequence depends not on one, but on several previous values ​​at once. An example is the well-known Fibonacci sequence, in which each next element is the sum of the two previous ones:

With a "head-on" approach, you can write:

Function Fib (n: integer): integer; begin if n> 1 then Fib: = Fib (n-1) + Fib (n-2) else Fib: = 1; end;

Each Fib call creates two copies of itself at once, each of the copies creates two more, etc. The number of transactions grows with the number n exponentially, although with an iterative solution, a linear in n the number of operations.

In fact, the above example teaches us not to WHEN recursion should not be used, and that HOW it should not be used. After all, if there is a fast iterative (loop-based) solution, then the same loop can be implemented using a recursive procedure or function. For instance:

// x1, x2 - initial conditions (1, 1) // n - number of the required Fibonacci number function Fib (x1, x2, n: integer): integer; var x3: integer; begin if n> 1 then begin x3: = x2 + x1; x1: = x2; x2: = x3; Fib: = Fib (x1, x2, n-1); end else Fib: = x2; end;

Still, iterative solutions are preferred. The question is, when, in this case, should you use recursion?

Any recursive procedures and functions that contain only one recursive call to themselves can be easily replaced with iterative loops. To get something that does not have a simple non-recursive analogue, you should refer to procedures and functions that call themselves two or more times. In this case, the set of called procedures no longer forms a chain, as in Fig. 1, but a whole tree. There are wide classes of problems when the computational process should be organized in this way. For them, recursion will be the easiest and most natural way to solve it.

5. Trees

The theoretical basis for recursive functions that call themselves more than once is the branch of discrete mathematics that studies trees.

5.1. Basic definitions. Ways to represent trees

Definition: the finite set T consisting of one or more nodes such that:
a) There is one special node called the root of this tree.
b) The rest of the nodes (excluding the root) are contained in pairwise disjoint subsets, each of which, in turn, is a tree. The trees are called subtrees this tree.

This definition is recursive. In short, a tree is a set consisting of a root and subtrees attached to it, which are also trees. The tree is defined through itself. However, this definition makes sense, since the recursion is finite. Each subtree contains fewer nodes than its containing tree. In the end, we come to subtrees containing only one node, and this is already clear what it is.

Rice. 3. Wood.

In fig. 3 shows a tree with seven nodes. Although ordinary trees grow from bottom to top, it is customary to draw them the other way around. When drawing a diagram by hand, this method is obviously more convenient. Because of this inconsistency, sometimes confusion arises when it is said that one of the nodes is above or below the other. For this reason, it is more convenient to use the terminology used when describing family trees, calling nodes closer to the root ancestors, and more distant descendants.

The tree can be represented graphically in several other ways. Some of them are shown in Fig. 4. According to the definition, a tree is a system of nested sets, where these sets either do not intersect or are completely contained in one another. Such sets can be depicted as areas on a plane (Fig. 4a). In fig. 4b, the nested sets are not located on a plane, but extended into one line. Rice. 4b can also be regarded as a diagram of some algebraic formula containing nested brackets. Rice. 4c provides another popular way of depicting a tree structure as a ledge.

Rice. 4. Other ways of depicting tree structures: (a) nested sets; (b) nested parentheses; (c) concession list.

The congruent list has obvious similarities to the way program code is formatted. Indeed, a program written in the framework of the structured programming paradigm can be represented as a tree consisting of nested constructs.

You can also draw an analogy between the tabular list and the appearance of tables of contents in books, where sections contain subsections, those in turn contain subsections, etc. The traditional way of numbering such sections (section 1, subsections 1.1 and 1.2, subsection 1.1.2, etc.) is called the Dewey decimal system. Applied to the tree in Fig. 3 and 4 this system will give:

1. A; 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. Passing trees

In all algorithms associated with tree structures, one and the same idea invariably occurs, namely the idea passing or tree traversal... This is a way of visiting the nodes of the tree, in which each node is traversed exactly once. This results in a linear arrangement of tree nodes. In particular, there are three ways: you can go through the nodes in forward, reverse and end order.

Forward traversal algorithm:

• Get to the root,
• Traverse all subtrees from left to right in direct order.

This algorithm is recursive, since traversing a tree contains traversing subtrees, which, in turn, are traversed according to the same algorithm.

In particular, for the tree in Fig. 3 and 4, direct traversal gives a sequence of nodes: A, B, C, D, E, F, G.

The resulting sequence corresponds to a sequential left-to-right enumeration of nodes when represented by a tree using nested brackets and in Dewey decimal system, as well as going from top to bottom when presented as a ledge list.

When this algorithm is implemented in a programming language, hitting the root corresponds to the execution of certain actions by a procedure or function, and traversing subtrees corresponds to recursive calls to itself. In particular, for a binary tree (where no more than two subtrees originate from each node), the corresponding procedure will look like this:

// Preorder Traversal is the English name for direct order procedure PreorderTraversal ((Arguments)); begin // Walk through the root DoSomething ((Arguments)); // Traverse the left subtree if (The left subtree exists) then PreorderTransversal ((Arguments 2)); // Traverse the right subtree if (There is a right subtree) then PreorderTransversal ((Arguments 3)); end;

That is, first, the procedure performs all the actions, and only then all recursive calls occur.

Reverse traversal algorithm:

• Traverse the left subtree,
• Get to the root,
• Traverse the next subtree on the left.
• Get to the root,
• and so on until the rightmost subtree is traversed.

That is, all subtrees are traversed from left to right, and the return to the root is located between these passes. For the tree in Fig. 3 and 4 this gives a sequence of nodes: B, A, D, C, E, G, F.

In the corresponding recursive procedure, actions will be placed in between the recursive calls. Specifically for a binary tree:

// Inorder Traversal is the English name for the reverse order procedure InorderTraversal ((Arguments)); begin // Traverse the left subtree if (The left subtree exists) then InorderTraversal ((Arguments 2)); // Walk through the root DoSomething ((Arguments)); // Traverse the right subtree if (There is a right subtree) then InorderTraversal ((Arguments 3)); end;

End-to-end traversal algorithm:

• Traverse all subtrees from left to right,
• Get to the root.

For the tree in Fig. 3 and 4 this will give a sequence of nodes: B, D, E, G, F, C, A.

In the corresponding recursive procedure, actions will appear after the recursive calls. Specifically for a binary tree:

// Postorder Traversal is the English name for trailing order procedure PostorderTraversal ((Arguments)); begin // Traverse the left subtree if (The left subtree exists) then PostorderTraversal ((Arguments 2)); // Traverse the right subtree if (There is a right subtree) then PostorderTraversal ((Arguments 3)); // Walk through the root DoSomething ((Arguments)); end;

5.3. Tree view in computer memory

If some information is located in the nodes of the tree, then to store it, you can use the appropriate dynamic data structure. In Pascal, this is done using a variable of type record (record), containing pointers to subtrees of the same type. For example, a binary tree where each node contains an integer can be stored using a variable of type PTree, which is described below:

Type PTree = ^ TTree; TTree = record Inf: integer; LeftSubTree, RightSubTree: PTree; end;

Each node is of the PTree type. This is a pointer, that is, each node must be created by calling the New procedure on it. If the node is leaf, then its LeftSubTree and RightSubTree fields are assigned the value nil... Otherwise, the LeftSubTree and RightSubTree nodes are also created by the New procedure.

One such record is shown schematically in Fig. 5.

Rice. 5. Schematic representation of a TTree record. A record has three fields: Inf - some number, LeftSubTree and RightSubTree - pointers to records of the same TTree type.

An example of a tree made up of such records is shown in Figure 6.

Rice. 6. A tree made up of TTree records. Each record stores a number and two pointers, which can contain either nil, or addresses of other records of the same type.

If you have not previously worked with structures consisting of records containing links to records of the same type, then we recommend that you familiarize yourself with the material about.

6. Examples of recursive algorithms

6.1. Drawing a tree

Consider the algorithm for drawing a tree shown in Fig. 6. If each line is considered a node, then this image quite satisfies the definition of a tree given in the previous section.

Rice. 6. Small tree.

The recursive procedure should obviously draw one line (trunk before the first fork) and then call itself to draw two subtrees. Subtrees differ from the tree containing them in the coordinates of the starting point, rotation angle, trunk length and the number of branches they contain (one less). All these differences should be made by parameters of the recursive procedure.

An example of such a procedure, written in Delphi, is presented below:

Procedure Tree (Canvas: TCanvas; // Canvas on which the tree will be drawn x, y: extended; // Root coordinates Angle: extended; // Angle at which the tree grows TrunkLength: extended; // Trunk length n: integer / / Number of forks (how many // recursive calls are yet to be called)); var x2, y2: extended; // The end of the trunk (branch point) begin x2: = x + TrunkLength * cos (Angle); y2: = y - TrunkLength * sin (Angle); Canvas.MoveTo (round (x), round (y)); Canvas.LineTo (round (x2), round (y2)); if n> 1 then begin Tree (Canvas, x2, y2, Angle + Pi / 4, 0.55 * TrunkLength, n-1); Tree (Canvas, x2, y2, Angle-Pi / 4, 0.55 * TrunkLength, n-1); end; end;

To obtain fig. 6 this routine was called with the following parameters:

Tree (Image1. Canvas, 175, 325, Pi / 2, 120, 15);

Note that drawing is done before recursive calls, that is, the tree is drawn in direct order.

6.2. Hanoi towers

According to legend, in the Great Temple of Benaras, under the cathedral that marks the middle of the world, there is a bronze disc on which three diamond rods are fixed, one cubit high and as thick as a bee. A long time ago, at the very beginning of time, the monks of this monastery were guilty before the god Brahma. Enraged, Brahma erected three high rods and placed 64 discs of pure gold on one of them, and so that each smaller disc rests on the larger one. As soon as all 64 discs are transferred from the rod, on which God Brahma put them when creating the world, to another rod, the tower together with the temple will turn to dust and the world will perish under the thunderous rolls.
The process requires that the larger disk never overshoots the smaller one. Monks are in difficulty, in what order should the transpositions be done? It is required to equip them with software to calculate this sequence.

Regardless of Brahma, this puzzle at the end of the 19th century was proposed by the French mathematician Edouard Lucas. The sold version usually used 7-8 discs (Fig. 7).

Rice. 7. Puzzle "Towers of Hanoi".

Suppose there is a solution for n-1 disk. Then for shifting n disks, proceed as follows:

1) Shifting n-1 disk.
2) Shifting n th disc onto the remaining free pin.
3) We shift the stack of n-1 disk obtained in step (1) over n th disk.

Since for the case n= 1, the shifting algorithm is obvious, then by induction using actions (1) - (3) we can shift an arbitrary number of disks.

Let's create a recursive procedure that prints the entire sequence of transfers for a given number of disks. Such a procedure with each of its calls should print information about one transfer (from point 2 of the algorithm). For transfers from items (1) and (3), the procedure will call itself with the number of disks reduced by one.

// n - number of disks // a, b, c - pin numbers. Transfer is performed from pin a, // to pin b with auxiliary pin c. procedure Hanoi (n, a, b, c: integer); begin if n> 1 then begin Hanoi (n-1, a, c, b); writeln (a, "->", b); Hanoi (n-1, c, b, a); end else writeln (a, "->", b); end;

Note that the set of recursively called procedures in this case forms a tree traversed in reverse order.

6.3. Parsing Arithmetic Expressions

The task of parsing is to calculate the value of the expression using the existing string containing the arithmetic expression and the known values ​​of the variables included in it.

The process of calculating arithmetic expressions can be represented as a binary tree. Indeed, each of the arithmetic operators (+, -, *, /) requires two operands, which will also be arithmetic expressions and, accordingly, can be considered as subtrees. Rice. 8 shows an example of a tree matching the expression:

Rice. 8. The syntax tree corresponding to the arithmetic expression (6).

In such a tree, the end nodes will always be variables (here x) or numeric constants, and all internal nodes will contain arithmetic operators. To execute an operator, you must first evaluate its operands. Thus, the tree in the figure should be traversed in end order. Corresponding sequence of nodes

called reverse polish notation arithmetic expression.

When constructing a syntax tree, you should pay attention to the following feature. If there is, for example, the expression

and we will read operations of addition and subtraction from left to right, then the correct syntax tree will contain a minus instead of a plus (Fig. 9a). In fact, this tree corresponds to the expression. It is possible to facilitate the construction of the tree if the expression (8) is analyzed on the contrary, from right to left. In this case, a tree with fig. 9b, which is equivalent to the tree 8a, but does not require replacement of characters.

Similarly, from right to left, you need to parse expressions containing multiplication and division operators.

Rice. 9. Syntax trees for expression a – b + c when reading from left to right (a) and from right to left (b).

This approach does not completely eliminate recursion. However, it allows you to limit yourself to only one call to the recursive procedure, which may be sufficient if the motive is to worry about maximum performance.

7.3. Determining a tree node by its number

The idea behind this approach is to replace recursive calls with a simple loop that will execute as many times as there are nodes in the tree formed by recursive procedures. What exactly will be done at each step should be determined by the step number. Comparing the step number and the necessary actions is not a trivial task and in each case it will have to be solved separately.

For example, suppose you want to execute k nested loops over n steps in each:

For i1: = 0 to n-1 do for i2: = 0 to n-1 do for i3: = 0 to n-1 do ...

If k is not known in advance, then it is impossible to write them explicitly, as shown above. Using the technique demonstrated in Section 6.5, you can get the required number of nested loops using a recursive procedure:

Procedure NestedCycles (Indexes: array of integer; n, k, depth: integer); var i: integer; begin if depth

To get rid of recursion and reduce everything to one loop, note that if you number the steps in the radix n, then each step has a number consisting of digits i1, i2, i3, ... or the corresponding values ​​from the Indexes array. That is, the numbers correspond to the values ​​of the cycle counters. The step number in the usual decimal system:

Total steps will be n k... By going through their numbers in the decimal notation system and translating each of them into a system with a radix n, we get the values ​​of the indices:

M: = round (IntPower (n, k)); for i: = 0 to M-1 do begin Number: = i; for p: = 0 to k-1 do begin Indexes: = Number mod n; Number: = Number div n; end; DoSomething (Indexes); end;

Once again, we note that the method is not universal and you will have to come up with something of your own for each task.

Control questions

1. Determine what the following recursive procedures and functions will do.

(a) What will the following procedure print when Rec (4) is called?

Procedure Rec (a: integer); begin writeln (a); if a> 0 then Rec (a-1); writeln (a); end;

(b) What will be the value of the function Nod (78, 26)?

Function Nod (a, b: integer): integer; begin if a> b then Nod: = Nod (a - b, b) else if b> a then Nod: = Nod (a, b - a) else Nod: = a; end;

(c) What will the following procedures print when calling A (1)?

Procedure A (n: integer); procedure B (n: integer); procedure A (n: integer); begin writeln (n); B (n-1); end; procedure B (n: integer); begin writeln (n); if n

(d) What will the following procedure print when calling BT (0, 1, 3)?

Procedure BT (x: real; D, MaxD: integer); begin if D = MaxD then writeln (x) else begin BT (x - 1, D + 1, MaxD); BT (x + 1, D + 1, MaxD); end; end;

2. Ouroboros - a snake devouring its own tail (Fig. 14) when unfolded has a length L, diameter near the head D, the thickness of the abdominal wall d... Determine how much tail he can fit into himself and in how many layers will the tail be laid after that?

Rice. 14. Unfolded ouroboros.

3. For the tree in fig. 10a indicate the sequence of visiting nodes for forward, backward and end-to-end traversal order.

4. Draw a graphical representation of the tree, defined using nested brackets: (A (B (C, D), E), F, G).

5. Draw the syntax tree for the following arithmetic expression:

Write this expression in reverse Polish notation.

6. For the graph below (Figure 15), write down the adjacency matrix and the incidence matrix.

Tasks

1. Having calculated the factorial a sufficiently large number of times (one million or more), compare the efficiency of the recursive and iterative algorithms. How many times will the execution time differ and how will this ratio depend on the number, the factorial of which is calculated?

2. Write a recursive function that checks the correct parentheses in a string. With the correct placement, the following conditions are met:

(a) the number of opening and closing parentheses is equal.
(b) inside any pair of opening - corresponding closing parentheses, the parentheses are placed correctly.

Examples of incorrect placement:) (, ()) (, ()) ((), etc.

3. The line may contain parentheses, both parentheses and square brackets. Each open parenthesis corresponds to a closing one of the same type (round - round, square - square). Write a recursive function to check if the parentheses are correct in this case.

An example of an incorrect placement: ([)].

4. The number of correct bracket structures of length 6 is 5: () () (), (()) (), () (()), ((())), (() ()).
Write a recursive program to generate all correct bracket structures of length 2 n.

Indication: Correct parenthesis structure with minimum length "()". Longer structures are obtained from shorter structures in two ways:

(a) if the smaller structure is enclosed in parentheses,
(b) if two smaller structures are written sequentially.

5. Create a routine that prints all possible permutations for integers from 1 to N.

6. Create a procedure that prints all subsets of the set (1, 2,…, N).

7. Create a procedure that prints all possible representations of the natural number N as the sum of other natural numbers.

8. Create a function that calculates the sum of the array elements according to the following algorithm: the array is divided in half, the sums of the elements in each half are counted and added. The sum of the elements in half of the array is calculated using the same algorithm, that is, again by dividing in half. Divisions occur until the resulting pieces of the array contain one element each and the calculation of the sum, respectively, becomes trivial.

Comment: This algorithm is an alternative. In the case of real-valued arrays, it usually allows you to get smaller rounding errors.

10. Create a procedure that draws the Koch curve (Fig. 12).

11. Reproduce fig. 16. In the figure, at each next iteration, the circle is 2.5 times smaller (this coefficient can be made as a parameter).

Literature

1.D. Knut. The art of computer programming. v. 1. (Section 2.3. "Trees").
2. N. Virt. Algorithms and data structures.

Functions: recursively given the function in its definition contains itself, in particular, the function defined by the recursive formula is recursive. Thus, one expression can give an infinite set of methods for calculating a function, define a set of objects through oneself using previously given private definitions.

Data

Struct element_of_list (element_of_list * next; / * link to next element of the same type * / int data; / * some data * /);

A recursive data structure often dictates the use of recursion to process that data.

In physics

A classic example of infinite recursion is two mirrors facing each other: two corridors of diminishing reflections of the mirrors are formed in them.

Another example of infinite recursion is the self-excitation (positive feedback) effect of electronic amplification circuits, where a signal from the output enters the input, amplifies, re-enters the input of the circuit, and amplifies again. Amplifiers for which this operating mode is standard are called oscillators.

In linguistics

The ability of a language to generate nested sentences and constructs. Basic offer " the cat ate the mouse"Can be extended by recursion as Vanya guessed that the cat ate the mouse, then as Katya knows that Vanya guessed that the cat ate the mouse etc. Recursion is considered one of the linguistic universals, that is, it is characteristic of any natural language. However, recently there has been an active discussion of the possible absence of recursion in one of the languages ​​of the Amazon - Piraha, which is noted by linguist Daniel Everett ( English) .

In culture

Most of the jokes about recursion concern infinite recursion in which there is no exit condition, for example, the saying is known: "to understand recursion, you must first understand recursion."

A very popular joke about recursion, reminiscent of a dictionary entry:

Several stories by Stanislav Lem are devoted to (possible) incidents with infinite recursion:

• the story about Yon the Tikhiy "Voyage fourteenth" from "The Star Diaries of Iyon the Tikhiy", in which the hero sequentially moves from an article about sepulki to an article about sepulation, from there to an article about sepulcaria, in which there is again a reference to the article "sepulka":

I found the following brief information:
“SEPULKI are an important element of the Ardrit civilization (see) from the planet Enteropia (see). See SEPULCARIA ".
I followed this advice and read:
"SEPULKARIA - devices for separation (see)".
I looked for Sepulenie; it read:
“SEPULENIE is the occupation of the ardrites (see) from the planet Enteropia (see). See SEPULKI ".

Lem S. “The Star Diaries of Iyon the Tikhiy. Journey fourteenth. "

• A story from "Cyberiada" about an intelligent machine that possessed sufficient intelligence and laziness to build a similar one to solve the task and entrust the solution to it (the result was an endless recursion, when each new machine built a similar one and passed the task to it).
• Recursive acronyms: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor), etc.

see also

• Reverse sequence

Notes (edit)

Wikimedia Foundation. 2010.

• Video memory
• Electromagnetic radiation

See what "Recursion" is in other dictionaries:

recursion- return, repetition of the Dictionary of Russian synonyms. recursion noun, number of synonyms: 1 ... Synonym dictionary

recursion- - [] recursion In a general sense, the computation of a function according to a certain algorithm. Examples of such algorithms are recurrent formulas that derive the calculation of a given term ... ... Technical translator's guide

Recursion- in the general sense, the calculation of a function according to a certain algorithm. Examples of such algorithms are recurrent formulas that derive the calculation of a given member of the sequence (most often numeric) from the calculation of several previous ones ... Economics and Mathematics Dictionary

Recursion- A therapeutic pattern, when some condition or criterion formulated in the original statement is taken and applied to the statement itself. For example: I have no time. How much time did you have to spend to make sure you had ... ... Big psychological encyclopedia

RECURSION- a way of defining functions, which is an object of study in the theory of algorithms and other sections of mathematical. logic. This method has long been used in arithmetic to determine numerical sequences (progressions, Fibonacci numbers, etc.). ... ... Encyclopedia of mathematics

recursion- (background.) (lat. recursio return). One of the three phases of articulation of sounds, indentation. Translation of the speech organs into a calm state or the beginning of articulation of the next sound. In the word rest, recursion (indentation) when articulating [t] can overlap with ... ... Dictionary of linguistic terms T.V. Foal

Collegiate YouTube

• 1 / 5

  In mathematics, recursion refers to the method of defining functions and series of numbers: recursively given a function determines its value by referring to itself with other arguments. In this case, two options are possible:

  e = 2 + 2 2 + 3 3 + 4 4 +… = 2 + f (2) (\ displaystyle e = 2 + (\ cfrac (2) (2 + (\ cfrac (3) (3 + (\ cfrac ( 4) (4+ \ ldots)))))) \; = 2 + f (2)), where f (n) = n n + f (n + 1) (\ displaystyle f (n) = (\ cfrac (n) (n + f (n + 1)))) Direct calculation using the above formula will cause an infinite recursion, but it can be proved that the value of f (n) tends to one with increasing n (therefore, despite the infinity of the series, the value of Euler's number is finite). For an approximate calculation of the value of e, it is enough to artificially limit the recursion depth to a certain predetermined number in advance, and upon reaching it, use it instead of f (n) (\ displaystyle f (n)) unit.

  Another example of recursion in mathematics is a numerical series, given by a recursive formula, when each next term in the series is calculated as the result of a function from n previous members. Thus, with the help of a finite expression (which is a combination of a recurrent formula and a set of values ​​for the first n members of a series), an infinite series can be defined.

  Struct element_of_list (element_of_list * next; / * pointer to the next element of the same type * / int data; / * some data * /);

  Since an infinite number of nested objects cannot be accommodated in finite memory, in reality such recursively defined structures are always finite. In the final (terminal) cells, null pointers are usually written, which are at the same time flags indicating to the program processing the structure that its end has been reached.