Recursive algorithm and its application
http://www.mydrs.org 2002-7-4
Large banyan
[Removable description]
As can be seen from the example above, in general, recursive needs to have boundary conditions, recursive front feedback and recursive return segments. When the boundary condition is not satisfied, recursive advances; when the boundary condition is satisfied, the recursive returns. Therefore, when considering writing programs using a recursive algorithm, two points should be satisfied:
1
This problem can be described in form;
2
There is a boundary condition for recursive end.
The ability to recursively define an unlimited set of objects with a limited statement. The procedures written with recursive thinking are often very simple and easy.
[
Example 2
The order and rear sequence arrangement of a binary tree is given. Ask its order.
[
analysis]
By comparing the order and rear sequence of the binary tree, we can find the root node and left and right bonus. Similarly, there is a root node that can be found by comparing the order and rear sequence of the left subtree.
......
It can be seen that this problem can be recursively described. When the last root node is found, the recursive cannot be done again, which is the boundary condition of the recursive end. It can be seen that the recursive algorithm often implicitly implicitly implicit. The procedure is as follows:
Program CHU01_3;
Var Z, H: String;
Procedure Find (A, B: String);
VAR
S, L: integer;
Begin
L: = Length (b);
IF L = 1 Then Write (b) {
Boundary condition and recursion return segment
}
Else
Begin {
Before recurring
}
Write (B [L]);
S: = POS (B [L], A);
IF S-1> 0 THEN FIND (COPY (A, 1, S-1), COPY (B, 1, S-1)); {
Recutive left subtree
}
IF L-S> 0 THEN FIND (COPY (A, S 1, L-S), COPY (B, S, L-S)); {
Recutive right
}
END;
Begin
Readln (z);
Readln (h);
Find (z, h);
Readln; End.
[Recursive application]
1.
Classic recursive
E.g
Hanoi
Tower Problem: Classic Recursive, the original problem contains sub-problems. Some problems or data structures are originally written, and it is natural to use it.
2.
Recurrence and recursive
Use the recursive ideas to establish a post-push relationship, such as rabbit
Fibonacci
sequence. But since the recursive is not returned, it is more simple, sometimes it can be implemented directly.
3.
Divide
Many division management methods are stem from recursive thinking or recursive decomposition.
Merger handling.
4.
Backtrack
Smaller problems are more natural. Pay attention to the recursion to ensure the preservation and recovery of the site, the correct conversion problem.
5.
Dynamic planning
Substantile properties of dynamic planning are similar to their recursive. Recursion
Dynamic Modifying Table is a good way to establish a dynamic planning model.
6.
other
Other, it is not good to classify. For example, expression processing, arrangement combination, etc. It is still very convenient to come with the problem of recursive printing schemes.
[
Example 3
Seeking an integer
n
Unordered
k
The total number of generic numbers of the interactive interactions.
[
analysis]
This is a dynamic programming question, the dynamic equation is as follows:
F [i-1, j] f [i, j-i] 1
(
(j mod i = 0) and (j Div i = 1)
)
f [i, j]: = f [i-1, j] (i> = j)
F [i-1, j] f [i, j-i]
(
Else
)
S: = f (k, n-k)
This question can be used to realize the recursive
,
You can also consider recursion. The main process is as follows: Scenary one:
Procedure Work (i, j: longint; var s: longint);
VAR T: longint;
Beginif (i = 1) or (j = 1) THEN S: = 1
ELSE IF (i = 0) or (j = 0) THEN S: = 0
Else Begin
IF (j mod i = 0) and (j div i = 1) THEN
Begin
Work (i-1, j, s);
T: = S;
Work (i, j-1, s);
S: = S T 1;
end
Else IF (i> = j) THEN
Work (I-1, J)
Else Begin
Work (i-1, j, s);
T: = S;
Work (i, j-1, s);
S: = S T;
END;
END;
Option II:
Procedure Search (V, W, Last: Byte); VAR i: byte; begin
IF W = 0 THEN INC (count)
Else
IF w = 1 THEN
IF v> = Last Ten Search (0,0,0) Else
Else for i: = Last TO V-1 Do Search (V-I, W-1, I); END;
It can be seen that the program is less frequent, the stack is large; the plan is more concise, and the stack space used is small, the efficiency is high. Therefore, there is also an optimization problem using the recursive algorithm. The simplicity of the algorithm directly restricts the feasibility and efficiency of the program.
[
to sum up]
Regeneration makes some complex issues simply, especially in the design of learning algorithms, and it can understand this when the data structure is designed. However, recursive should be partial variables at each execution, return the address assignment stack space, which reduces the operational efficiency and limits the depth of recursive. Therefore, you can solve only recursive ideas when necessary, and the program is transferred to non-recursive ways.
