Recursion is called the situation when the subroutine causes itself. First faced with such an algorithmic design, most people are experiencing certain difficulties, but some practices and recursion will become a clear and very useful tool in your programmer's arsenal.
1. Essence of recursion
The procedure or function may contain a call to other procedures or functions. Including the procedure can cause itself. There is no paradox here - the computer only sequentially performs the commands encountered in the program and if the procedure is called, it just begins to perform this procedure. Without a difference, what procedure gave the team to do it.
An example of a recursive procedure:
Procedure REC (A: Integer); Begin if a\u003e
Consider what will happen if in the main program to make a call, for example, the form REC (3). Below is a block diagram showing the sequence of execution of operators.
Fig. 1. Block operation scheme of the recursive procedure.
The REC procedure is called with the parameter A \u003d 3. It contains the REC procedure with the parameter A \u003d 2. The previous call has not yet completed, so you can imagine that another procedure is created and until the end of its work does not finish its work. The call process ends when the parameter A \u003d 0. At this point, 4 copies of the procedure are performed simultaneously. The number of simultaneously executed procedures is called depth recursion.
The fourth induced procedure (REC (0)) will print the number 0 and finish its work. After that, the control returns to the procedure that caused it (REC (1)) and the number 1. The number 1. and so on until all procedures are completed. The result of the source call will be the seal of four numbers: 0, 1, 2, 3.
Another visual image of what is happening is shown in Fig. 2.
Fig. 2. The execution of the REC procedure with parameter 3 consists of execution of the REC procedure with parameter 2 and the sext number 3. In turn, the execution of the REC procedure with parameter 2 consists of execution of the REC procedure with parameter 1 and the print number 2., so.
Think as an independent exercise that it turns out when calling REC (4). Also think what happens when the Rec2 procedure described below (4) is called, where the operators have changed in places.
Procedure Rec2 (A: Integer); Begin Writeln (A); IF A\u003e 0 THEN REC2 (A-1); end;
Please note that in the examples given, the recursive call is within the conditional operator. This is a prerequisite for recursion to ever end. Also note that the procedure itself calls with another parameter, not as caused by it itself. If the procedure does not use global variables, it is also necessary that recursion does not continue to infinity.
A slightly more complex scheme is possible: the function A causes the function B, and that in turn causes A. It is called complex recursion. In this case, it turns out that the first procedure described must be not yet described. To make it possible, you need to use.
Procedure A (N: Integer); (Advanced description (header) of the first procedure) Procedure B (N: Integer); (Advanced Description of the second procedure) Procedure A (N: Integer); (Full description of the procedure a) Begin Writeln (N); B (n-1); end; Procedure B (N: Integer); (Full description of the procedure B) Begin Writeln (N); IF N.
The advanced description of the procedure B allows you to call it out of procedure A. The outpacing description of the procedure A in this example is not required and added from aesthetic considerations.
If the usual recursion can be likened to the Uroboros (Fig. 3), the image of a complex recursion can be leaning from a well-known children's poem, where "Wolves with a fright, they buried each other." Imagine two wolves eating each other, and you will understand a complex recursion.
Fig. 3. Uroboros - snake devouring your tail. Figure from the alchemical treatise "Synosius" Theodore of Perekanosa (1478g).
Fig. 4. Complex recursion.
3. Imitation of the operation of the cycle using recursion
If the procedure causes itself, then, in fact, this leads to a re-execution of the instructions contained in it, which is similar to the operation of the cycle. Some programming languages \u200b\u200bdo not contain cyclic designs at all, providing programmers to organize repetitions using recursion (for example, a prologue where recursion is the main programming method).
For example, modify the work of the FOR cycle. To do this, we will need a variable steps counter, which can be implemented, for example, as the parameter of the procedure.
Example 1.
Procedure Loopimitation (I, N: Integer); (The first parameter - the steps counter, the second parameter - the total number of steps) Begin Writeln ("Hello N", I); // here any instructions that will be repeated IF I The result of the call view of the Loopimitation (1, 10) will be tenfold execution of instructions with a change of counter from 1 to 10. In this case, it will be printed: Hello N 1. In general, it is not difficult to see that the parameters of the procedure are the limits of changing the values \u200b\u200bof the counter. You can change the recursive challenge and the instructions to be repetitive as in the following example. Example 2.
Procedure Loopimitation2 (I, N: Integer); Begin IF I. In this case, before the instructions are run, a recursive challenge of the procedure will occur. A new instance of the procedure also, first of all, will call another instance and so on until we reach the maximum counter value. Only after that the latter of the procedures caused will execute their instructions, then execute its instructions penultimate, etc. The result of calling Loopimitation2 (1, 10) will print greetings in the reverse order: Hello N 10. If you imagine a chain of recursively caused procedures, then in example 1 we pass it from before the procedures caused to later. In example 2, on the contrary, from later to early. Finally, the recursive call can be placed between two blocks of instructions. For example: Procedure Loopimitation3 (I, N: Integer); Begin Writeln ("Hello N", I); (Here can be the first instruction block) if i Here, first, instructions are sequentially performed from the first unit then in the reverse order of the instruction of the second block. When calling Loopimitation3 (1, 10) we get: Hello N 1. Two cycles will be required to do the same without recursion. The fact that the execution of parts of the same procedure is spaced over time can be used. For example: Example 3: Translation of a number into a binary system.
Getting a binary number, as is known, occurs by dividing with the residue on the base of the number system 2. If there is a number, its last digit in its binary representation is equal to Taking a whole part of the division by 2: we get a number having the same binary representation, but without the last digit. Thus, it is enough to repeat the two operations below. While the field of the next division does not get a whole part of equal to 0. Without recursion it will look like this: While x\u003e 0 do begin c: \u003d x MOD 2; x: \u003d x div 2; WRITE (C); end; The problem here is that the digits of the binary representation are calculated in the reverse order (first the latter). To print a number in a normal form, you will have to remember all the numbers in the elements of the array and output in a separate cycle. With the help of recursion it is not difficult to achieve output in the correct order without an array and second cycle. Namely: Procedure BinaryRepresentation (X: Integer); VAR C, X: Integer; begin (first unit. It is performed in order of calling procedures) C: \u003d x MOD 2; x: \u003d x div 2; (Recursive call) if x\u003e 0 Then binaryRepresentation (X); (Second block. It is performed in reverse order) WRITE (C); end; Generally speaking, we did not get any win. The digits of the binary representation are stored in local variables that are for each working instance of the recursive procedure. That is, the memory could not be saved. Even on the contrary, we spend extra memory for storing many local variables x. However, such a solution seems to me beautiful. It is said that the sequence of vectors is set by a recurrent ratio if the initial vector and the functional dependence of the subsequent vector from the previous Simple example of the value calculated using recurrent relations, is a factorial Another factorial can be calculated by the previous one as: By introducing the designation, we obtain the ratio: Vector from formula (1) You can interpret as sets of variable values. Then the calculation of the desired sequence element will consist in a recurring update of their values. In particular, for factorial: X: \u003d 1; For i: \u003d 2 to n Do x: \u003d x * i; Writeln (X); Each such update (x: \u003d x * i) is called iteration, and the process of repetition of iterations - lettering. We turn, however, attention is that the ratio (1) is a purely recursive determination of the sequence and the calculation of the N-th element there is actually repeatedly taking the function F from itself: In particular, for factorial can be written: FUNCTION FACTORIAL (N: INTEGER): Integer; Begin IF n\u003e 1 Then Factorial: \u003d N * Factorial (N-1) Else Factorial: \u003d 1; end; It should be understood that the challenge of functions entails some additional overhead costs, so the first option for calculating the factorial will be somewhat faster. In general, iterative solutions work faster than recursive. Before switching to situations where recursion is useful, we will pay attention to another example, where it should not be used. Consider a particular case of recurrent relations when the next value in the sequence is not depends on one, but immediately from several previous values. An example is the well-known Fibonacci sequence, in which each next element is the sum of the previous two: With the "Lobov" approach can be written: FUNCTION FIB (N: INTEGER): Integer; Begin if n\u003e 1 Then FIB: \u003d FIB (N-1) + FIB (N-2) ELSE FIB: \u003d 1; end; Each FIB call creates two copies at once, each from the copies - two more, etc. The number of operations is growing with the number n. exponentially, although the iterative solution is quite linear n. number of operations. In fact, the example given us does not WHEN Recursion should not be used, and AS It should not be used. In the end, if there is a quick iterative (based on cycles) solution, the same cycle can be implemented using a recursive procedure or function. For example: // 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\u003e 1 Then Begin x3: \u003d x2 + x1; x1: \u003d x2; x2: \u003d x3; FIB: \u003d fib (x1, x2, n-1); END ELSE FIB: \u003d X2; end; Nevertheless, iterative solutions are preferred. The question is, when in this case, should the recursion be used? Any recursive procedures and functions containing only one recursive challenge themselves are easily replaced with iterative cycles. In order to get something that does not have a simple non-erased analogue, you should contact the procedures and functions that cause yourself two or more times. In this case, the set of the procedures forms no longer a chain, as in Fig. 1, and a whole tree. There are wide classes of tasks when the computing process should be organized in this way. Just for them, recursion will be the easiest and most natural way to solve. The theoretical basis for recursive functions causing more than once, serves a section of discrete mathematics, studying trees. Definition:
We will call the final set T.consisting of one or more nodes, such that: This definition is recursive. If briefly, the tree is a set consisting of the root and connected to it, which are also trees. The tree is determined through itself. However, this definition is meaningful, since the recursion is finite. Each subtree contains less nodes than a tree containing it. In the end, we come to the subtildings containing only one node, and this is already clear what. Fig. 3. Tree. In fig. 3 shows a tree with seven nodes. Although ordinary trees grow up from the bottom up, draw them accepted on the contrary. When drawing a scheme from hand such a way is obviously more convenient. Because of this inconsistency, it sometimes arises confusion when they say that one of the nodes is above or under one. For this reason, it is more convenient to use the terminology used in describing the genealogical trees, calling the nodes closest to the root, and more distant descendants. Graphically, the tree can be portrayed by some other ways. Some of them are presented in Fig. 4. According to definition, the tree is a system of nested sets, where these sets or do not intersect or completely contain one in the other. Such sets can be depicted as areas on the plane (Fig. 4a). In fig. 4B Nested sets are not located on the plane, but stretched into one line. Fig. 4B can also be considered as a diagram of some algebraic formula containing nested brackets. Fig. 4B gives another popular way of image of a tree structure in the form of a discusing list. Fig. 4. Other ways of image of tree structures: (a) nested sets; (b) nested brackets; (c) the adhesive list. The plug-down list is obvious similarity with the method of formatting the program code. Indeed, the program written under the paradigm of structural programming can be represented as a tree consisting of furnaces invested in each other. You can also make an analogy between the discusible list and the appearance of the table of contents in the books where the sections contain subsections, they in turn are published, etc. The traditional method of numbering of such sections (Section 1, subsections 1.1 and 1.2, subproduction of 1.1.2, etc.) is called a decimal Dewey system. In applied to a 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; In all algorithms associated with tree structures, the same idea is invariably found, namely the idea passing or own tree. This is a way to visit the tree nodes, in which each node is exactly once. This turns out a linear arrangement of tree nodes. In particular, there are three ways: you can pass nodes in direct, reverse and end order. Bypass algorithm in direct: This algorithm is recursive, since the passage of wood contains the passage of subtrees, and they, in turn, are passing along the same algorithm. In particular for wood in fig. 3 and 4 Directly bypass gives a sequence of nodes: A, B, C, D, E, F, G. The resulting sequence corresponds to the sequential left to refer to the listing of nodes when the tree is presenting using nested brackets and in the decimal Dewey system, as well as the passage from top to bottom when viewed in the form of a discrepan list. When implementing this algorithm in the programming language, the root hit corresponds to the implementation of the procedure or the function of certain actions, and the passage of subtrees - recursive calls for itself. In particular, for binary wood (where no more than two subtrees come from each node) the corresponding procedure will look like this: // Preorder Traversal - English name for direct procedure Procedure PreorderTraversal ((arguments)); begin // Passage of the root of Dosomething ((arguments)); // Passage of the left subsection if (there is a left subtree) THEN PREORDERTRANSVERSAL ((arguments 2)); // Passage of the right subtree if (there is a right subtree) THEN PREORDERTRANSVERSAL ((arguments 3)); end; That is, at first, the procedure produces all actions, and only then all recursive calls occur. Algorithm bypass in reverse order: That is, all the supports are held on the left to the right, and returning to the root is located between these passages. For wood in fig. 3 and 4 This gives a sequence of nodes: B, A, D, C, E, G, F. In the relevant recursive procedure, the action will be located between the recursive challenges. In particular for binary wood: // INORDER TRAVERSAL - English name for reverse order Procedure InorDertraversal ((arguments)); Begin // Passage of the left subsection if (there is a left subtree) THEN INORDERTRAVERSAL ((arguments 2)); // passage of the root of Dosomething ((arguments)); // passing the right subtree if (there is a right subtree) THEN INORDERTRAVERSAL ((arguments 3)); end; Control algorithm in case: For wood in fig. 3 and 4 This will give a sequence of nodes: B, D, E, G, F, C, A. In the relevant recursive procedure, the action will be located after recursive calls. In particular for binary wood: // PostOrder Traversal - English name for terminal order Procedure PostOrdertraversal ((arguments)); Begin // Passage of the left subsequent if (there is a left subtree) Then PostOrdertraversal ((arguments 2)); // passing the right subsequent if (there is a right subtree) Then PostOrdertraversal ((arguments 3)); // passage of the root of Dosomething ((arguments)); end; If some information is located in the nodes of the tree, then it is possible to use the corresponding dynamic data structure to store it. In Pascal, this is done using a record type variable (Record) containing pointers to the supporting of the same type. For example, a binary tree, where each node contains an integer can be saved using a variable type Ptree, which is described below: Type Ptree \u003d ^ Ttree; TTREE \u003d RECORD INF: INTEGER; LeftSubtree, RightSubtree: Ptree; end; Each node has a type of Ptree. This is a pointer, that is, each node must be created, causing a NEW procedure for it. If the node is a terminal, then his leftsubtree and rightsubtree fields are assigned to the value nil.. Otherwise, the LEFTSUBTREE and RightSubtree nodes are also created by the NEW procedure. Schematically, one such entry is shown in Fig. five. Fig. 5. Sketchy image of TTREE type record. The entry has three fields: INF - some number, leftsubtree and RightSubtree - pointers on records of the same TTREE type. An example of a tree compiled from such entries is shown in Figure 6. Fig. 6. A tree composed of TTREE type records. Each entry stores the number and two pointers that may contain either nil.or addresses of other records of the same type. If you have not previously worked with the structures consisting of records containing links to records of the same type, we recommend familiarizing yourself with the material about. Consider the algorithm for drawing the village shown in Fig. 6. If each line is considered a node, this image completely satisfies the definition of the tree given in the previous section. Fig. 6. Drop. The recursive procedure should obviously draw one line (trunk to the first branching), and then cause itself for drawing two subtrees. The supports differ from the coordinates of the starting point containing their tree, the corner, the length of the trunk and the amount of branches contained in them (permanently). All these differences should be made by the 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 X, Y tree will be drawing: extended; // root coordinates Angle: Extended; // Corner, under which the Tree Tree grows: extended; // Stem length N: Integer / / Number of branches (how much still have // \u200b\u200brecursive calls)); VAR X2, Y2: EXTENDED; // end of the trunk (branching point) begin x2: \u003d x + trunklength * cos (angle); y2: \u003d y - trunklength * sin (angle); Canvas.moveto (Round (x), Round (Y)); Canvas.Lineto (Round (x2), Round (Y2)); IF N\u003e 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 procedure was called up with the following parameters: Tree (image1.canvas, 175, 325, PI / 2, 120, 15); Note that drawing is carried out to recursive calls, that is, the tree is drawn in direct order. According to the legend in the Great Temple of the city of Benaras, under the cathedral celebrating the middle of the world, there is a bronze disk, on which 3 diamond rods are strengthened, alone in one elbow and thickness with a bee. Long ago, at the very beginning of the time the monks of this monastery were guilty before God's God. An angry, Brama has erected three high rods and one of them placed 64 discs of pure gold, and so that each smaller disk lies on more. As soon as all 64 disks are transferred from the rod to which God Brahm folded them when creating peace, to another rod, the tower along with the temple will turn into dust and the world will die under thunder. Regardless of Brand, this puzzle at the end of the 19th century proposed French mathematician Edward Luke. In the sold version, 7-8 disks were usually used (Fig. 7). Fig. 7. Puzzle "Hanoi Towers". Suppose that there is a solution for n.-1 disc. Then for shifting n. Does need to act as follows: 1) shift n.-1 disc. Since for the case n. \u003d 1 The transition algorithm is obvious, then by induction by performing actions (1) - (3) we can shift an arbitrary number of disks. Create a recursive procedure that prints the entire sequence of shifting for a given number of disks. Such a procedure should print information about one shocking (from paragraph 2 of the algorithm). For shifting from items (1) and (3), the procedure will cause itself with the amount of disks reduced per unit. // n - the number of disks // A, B, C - Pin numbers. Passing is made from pin A, // on the pin B with auxiliary pin C. Procedure Hanoi (N, A, B, C: INTEGER); Begin IF n\u003e 1 Then Begin Hanoi (N-1, A, C, B); Writeln (A, "-\u003e", b); Hanoi (N-1, C, B, A); END ELSE WRITELN (A, "-\u003e", B); end; Note that many recursively caused procedures in this case forms a tree passing in reverse order. The task of the syntax analysis is that according to the existing row containing an arithmetic expression and the known values \u200b\u200bof variables in it, calculate the value of the expression. 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 support. Fig. 8 shows an example of a tree appropriate: Fig. 8. The syntax tree corresponding to the arithmetic expression (6). In such a tree, the terminal nodes will always be variables (here x.) or numeric constants, and all internal nodes will contain arithmetic operators. To execute the operator, you must first calculate its operands. Thus, the tree in the figure should be bypassed in the case. The corresponding sequence of nodes called inverse Polish record arithmetic expression. When building a syntactic tree, pay attention to the following feature. If there is, for example, expression and the addition and subtraction operations we will read the left to the right, then the correct syntax tree will contain minus instead of the plus (Fig. 9a). In fact, it corresponds to the expression tree to facilitate the preparation of the tree can be, if we analyze the expression (8), on the contrary, from right to left. In this case, a tree is obtained with rice. 9b, equivalent to wood 8a, but not requiring signs. Similarly, on the right to left, it is necessary to analyze expressions containing multiplication and division operators. Fig. 9. Syntactic trees for expression a. – b. + c. When reading from left to right (a) and right to left (b). This approach does not save us from recursion completely. However, it allows you to restrict ourselves to only one appeal to the recursive procedure, which may be enough if the motive is concern for maximum performance. The idea of \u200b\u200bthis approach is to replace the recursive calls simple cycle, which will be executed as many times as nodes in the tree formed by a recursive procedure. What exactly will be done at every step, should be determined by step number. Match the number of the step and the necessary actions - the task is not trivial and in each case it will have to be solved separately. For example, let it be required to perform k. Nested cycles in n. Steps in each: For i1: \u003d 0 to N-1 DO FOR I2: \u003d 0 TO N-1 DO FOR I3: \u003d 0 TO N-1 DO ... If a k. It is not known in advance, then write them explicitly, as shown above is impossible. Using the reception, shown in Section 6.5, you can obtain the required number of nested cycles using the 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 cycle, let us note that if the numbered steps in the radix n., each step has a number consisting of numbers I1, I2, I3, ... or corresponding values \u200b\u200bfrom the indexes array. That is, the numbers correspond to the values \u200b\u200bof cycles. Step number in a conventional decimal number system: Total steps will be n K.. After passing their numbers in a decimal system of number and translating each of them into the system with a base n., We obtain the values \u200b\u200bof the indexes: M: \u003d Round (Intpower (N, K)); For i: \u003d 0 to M-1 DO Begin Number: \u003d i; For p: \u003d 0 to k-1 Do Begin Indexes: \u003d Number MOD N; Number: \u003d Number Div N; end; Dosomething (indexes); end; Once again, we note that the method is not universal and for each task will have to come up with something. 1. Determine that they will make the following recursive procedures and functions. (a) What will printed the following procedure when calling REC (4)? Procedure REC (A: Integer); Begin Writeln (A); IF A\u003e 0 THEN REC (A-1); Writeln (A); end; (b) What will be the value of the NOD function (78, 26)? FUNCTION NOD (A, B: INTEGER): Integer; begin if a\u003e b Then nod: \u003d nod (a - b, b) else if b\u003e ae nod: \u003d nod (a, b - a) else nod: \u003d a; end; (c) What will be printed by the procedures below 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 print the following procedure when calling BT (0, 1, 3)? Procedure BT (X: REAL; D, MAXD: Integer); begin if d \u003d maxd then writeln (x) Else Begin BT (X - 1, D + 1, MAXD); Bt (X + 1, D + 1, MAXD); end; end; 2. Umoboros - snakes, devouring his own tail (Fig. 14) in the deployed form has a length L., diameter near the head D., the thickness of the abdominal wall d.. Determine how much tail he can shove into himself and how many layers will the tail be laid after that? Fig. 14. Deployed Ubboros. 3. For wood in Fig. 10a Specify the sequences of visiting nodes with direct, reverse and end bypass order. 4. Picture graphically a tree specified using nested brackets: (A (B (C, D), E), F, G). 5. Picture a graphically syntax tree for the following arithmetic expression: Write down this expression in the inverse Polish record. 6. For the graph below (Fig. 15), write down the arrangement matrix and the incidence matrix. 1. Calculate factorial sufficiently large number of times (million or more), compare the effectiveness of recursive and iterative algorithms. How many times will the time of execution be different and how does this ratio be dependent on the number that the factorial is calculated? 2. Write a recursive function that checks the correctness of the layout of the brackets in the string. With the correct arrangement, conditions are satisfied: (a) The number of opening and closing brackets is equal. Examples of incorrect arrangement:) (, ()) (, ()) ((), etc. 3. Brackets both round and square brackets may be present in the row. Each opening bracket corresponds to a closing of the same type (round - round, square-square). Write a recursive function that checks the correctness of the layout of the brackets in this case. An example of incorrect arrangement: ([)]. 4. The number of proper bracket structures of length 6 is 5: () () (), (()) (), () (()), ((())), (() ()). Note: Proper storage structure of the minimum length "()". Structures of greater length are obtained from smaller length structures, in two ways: (a) if a smaller structure is taken into brackets, 5. Create a procedure 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. Write a function that counts the amount of elements in the array using the following algorithm: array is divided in half, counted and added the sum of elements in each half. The amount of elements in the middle of the array is calculated on the same algorithm, that is, again by dividing in half. The divisions occur until the array in the resulting pieces will not be on one element and the calculation of the amount, respectively, will not become 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, drawing a koch curve (Fig. 12). 11. Play Fig. 16. In the figure on each of the next iteration of the circle 2.5 times less (this coefficient can be made by parameter). 1. D. Knut. Art programming art. t. 1. (Section 2.3. "Trees"). The presentation on the theme "Recursive algorithms" was created to prepare students in computer science and ICT. The paper discusses the identification of recursion, shows examples of recursively-specific graphic objects. The presentation contains ways to solve the task number 11 from the draft demo version of the EGE - 2015 on computer science. The first method involves building a call tree, the second method solves the problem by substitution. 4 examples of solving tasks with the use of both methods are considered. Next, the presentation contains 25 tasks for training with answers from the site Konstanta Polyakova. To enjoy previewing presentations, create yourself an account (account) Google and log in to it: https://accounts.google.com Task number 11 EGE (Basic level, time - 5 min) Recursive algorithms. Author - Savoon O.V., Teacher of Informatics MOU "Sosh No. 71" What you should know: Recursion - in the definition, description, image of an object or a process within itself the object or process, that is a situation where the object is a part of himself. Coat of arms Russian Federation It is a recursively-defined graphic object: in the right paw depicted on it, the double-headed eagle is groping a scepter, which is crowned with a reduced copy of the coat of arms. Since on this coat of arms in the right paw of Eagle is also a scepter, it turns out an endless recursion. Recursive coat of arms of Russia In programming recursion - a call to the function from it itself, directly or through other functions, for example, the function A calls the function B, and the function B is a function A. The number of nested calls of the function or procedure is called a recursion depth. An example of recursion: if you have a fat stain on the dress, do not worry. The stains from the oil are cleaned with gasoline. It's safely from gasoline with a solution of a lump. Shoe is removed by the essence. Love from the essence of the essence. Job example: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Job example: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Job example: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N Slide 9 Job example: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N Slide 10 Job example: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N Slide 11 15 Example number 2: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Example number 2: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N Slide 13 Example number 3: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-2); F (n div 2) End End; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? 7 5 3 2 3 1 1 1 1 In this example, no values \u200b\u200bof the parameter n are displayed on the screen, but * -2 Div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 Example number 3: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-2); F (n div 2) End End; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? * Counting the number of "stars", we get 21 in this example displays the value of the parameter is not n, and the symbol * * * * * * * * * * * * * * * * * * * * * Example number 3: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-2); F (n div 2) End End; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? We will solve the task without a tree. Let s (n) be the number of "asterisks", which will be derived when calling F (N). Then 1 + s (n-2) + s (n div 2), n\u003e 0 1, n we need to know S (7). S (7) \u003d 1 + S (5) + S (3) S (5) \u003d 1 + S (3) + S (2) S (3) \u003d 1 + S (1) + S (1) S ( 2) \u003d 1 + S (0) + S (1) \u003d 1 + 1 + S (1) \u003d 2 + S (1) S (1) \u003d 1+ S (-1) + S (0) \u003d 1 + 1 + 1 \u003d 3 We make the reverse move: s (2) \u003d 2 + 3 \u003d 5 s (3) \u003d 1 + 3 + 3 \u003d 7 s (5) \u003d 1 + 7 + 5 \u003d 13 s (7) \u003d 1 + 13 + 7 \u003d 21 s (n) \u003d Example number 4: Procedure F (N: Integer); Begin IF N Slide 18 Example number 4: Procedure F (N: Integer); Begin IF N Slide 19 Example number 4: Procedure F (N: Integer); Begin IF N. Example number 4: Procedure F (N: Integer); Begin IF N. Tasks for training Task 1: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-2); F (n div 2); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when it is called F (5)? Answer: 34. Task 2: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-2); F (n-2); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when you call F (6)? Answer: 58. Task 3: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-3); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? Answer: 15. Task 4: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-3); F (n-2); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? Answer: 55. Task 5: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 THEN BEGIN F (N-3); F (n-2); F (n div 2); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when you call F (6)? Answer: 97. Task 6: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 Then Begin Writeln ("*"); F (n-2); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? Answer: 31. Task 7: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 Then Begin Writeln ("*"); F (n-2); F (n div 2); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? Answer: 81. Task 8: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln ("*"); IF N\u003e 0 Then Begin Writeln ("*"); F (n-2); F (n-2); F (n div 2); End End; How many characters "asterisk" will be printed on the screen when you call F (6)? Answer: 77. Task 9: Dan recursive algorithm: Procedure F (N: Integer); Begin IF n\u003e 0 Then Begin F (N-2); F (n-1); F (n-1); end; Writeln ("*"); end; How many characters "asterisk" will be printed on the screen when it is called F (5)? Answer: 148. Task 10: Dan recursive algorithm: Procedure F (N: Integer); Begin if n\u003e 0 Then Begin Writeln ("*"); F (n-2); F (n-1); F (n-1); end; Writeln ("*"); end; How many characters "asterisk" will be printed on the screen when it is called F (5)? Answer: 197. Task 11: Dan recursive algorithm: Procedure F (N: Integer); begin if n\u003e 1 then begin f (n-2); F (n-1); F (n div 2); end; Writeln ("*"); end; How many characters "asterisk" will be printed on the screen when the call F (7) is performed? Answer: 88. Task 12: Dan recursive algorithm: Procedure F (N: Integer); Begin if n\u003e 2 Then Begin Writeln ("*"); F (n-2); F (n-1); F (n div 2); end; Writeln ("*"); end; How many characters "asterisk" will be printed on the screen when you call F (6)? Answer: 33. Task 13: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 14: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 15: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 16: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 17: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 18: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 19: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 20: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 21: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 22: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 23: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 24: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N. Task 25: Dan recursive algorithm: Procedure F (N: Integer); Begin Writeln (N); IF N.
Hello N 2.
…
Hello N 10.
…
Hello N 1.
…
Hello N 10.
Hello N 10.
…
Hello N 1.4. Recurrent relations. Recursion and iteration
5. Trees
5.1. Main definitions. Ways image of trees
a) There is one special node called the root of this tree.
b) the rest of the nodes (excluding root) are contained in pairwise disseminating subsets, each of which in turn is a tree. Trees are called supporting This tree.
5.2. Passage of trees
5.3. Tree view in computer memory
6. Examples of recursive algorithms
6.1. Drawing of a tree
6.2. Khanaya Towers
In the process it is required that a larger disk never turns out to be over smaller. Monks in difficulty, in what sequence it is worth making shifts? It is required to provide them with software to calculate this sequence.
2) shift n.-y disk for the remaining pin.
3) shift the stack from n.-1 disc received in paragraph (1) on top n.-Ho disc.6.3. Syntactic analysis of arithmetic expressions
7.3. Defining a tree node by its number
Control questions
Tasks
(b) inside any pair opening - the corresponding closing bracket, the brackets are arranged correctly.
Write a recursive program for generating all the correct stuffing structures of length 2 n..
(b) if two smaller structures are written sequentially.
Literature
2. N. Wirth. Algorithms and data structures.Download:
Preview:
Signatures for slides:
Currency courses
