Recursive algorithm design method

This is the 16th day of my participation in the August Text Challenge.More challenges in August

Recursive algorithm design method

Since binary tree is a kind of recursive data structure, a lot of recursive algorithm design of binary tree is involved in the following, and the general method of recursive algorithm design is specially introduced.

1.1 What is Recursion

When defining a procedure or function, it is called recursion if there is a component that calls the procedure or function. If you call itself directly, it’s called direct recursion. If a procedure or function P calls a procedure or function Q and Q calls P, it is called indirect recursion. This is mainly direct recursion. For example, there is the following recursive function:

F (1) = 1, f (2) = 1, f (n) = f (n - 1) + f (n - 2) n 3 or higherCopy the code

The corresponding recursive algorithm Fun () for solving f (n) is as follows.

The procedure for calculating Fun (5) is shown in Figure 6.16, where the downward arrow (represented by a solid line) represents the recursion or decomposition process, the upward arrow (represented by a dashed line) represents the evaluation or return process, and the value above Fun (n) represents its solution result.

Figure 6.16 Calculation process of Fun (5)

Call the previous description of f () a recursive model, and fun () is the corresponding recursive algorithm. We can see that the recursive model is an abstraction of the recursive algorithm, and it reflects the recursive structure of a recursive problem.

Generally, the recursive model consists of two parts, one is the recursive exit, which gives the termination conditions of recursion. For example, f (1) =1 and F (2) =1 in the previous examples are the recursive exit. The other part is the recursion body, which determines the recursion relation when solving the recursion. For example, f (n) = F (n — 1) +f (n — 2) in the previous example is the recursion body.

The solving process of recursive algorithm is characterized by: firstly, the problem that cannot be solved directly is transformed into several similar small problems, and finally, the solution of the whole problem is obtained by solving each sub-problem separately. When these subproblems cannot be solved directly, they can be transformed into several smaller subproblems, and so on until a recursive exit is reached. This kind of top-down decomposition of the problem, solution, and then bottom-up reference, merger, the final solution of the process is called the recursive solution process. This is a divide-and-conquer approach to algorithm design.

1.2 General method of recursive algorithm design

The design method of recursive algorithm is to determine the corresponding recursive model, and then transform it into recursive algorithm. Its core idea is to simplify the problem into several sub-problems, whose form and algorithm are similar to the original problem algorithm, but simpler than the original.

Therefore, when designing recursive algorithm, we should focus on analyzing the recursive operation of recursive data structure, and make full use of the characteristics of this kind of operation for recursive design. The general steps for obtaining a recursive model for solving a problem are as follows.

(1) Analyze the original problem F (s) and assume a reasonable “small problem” F (S ‘) (similar to the equation assuming n=k — 1 in mathematical induction);

(2) Assuming that F (S ‘) is solvable, the solution of F (s) is determined on this basis, that is, the relationship between F (s) and F (S ‘) is given (similar to the process of proving the equality when n=k in mathematical induction);

(3) Determine the solution of a particular case (such as f (1) or f (0)), and thus serve as a recursive exit (similar to the mathematical induction method to prove that n=1 or n=0 is true).

Design a recursive algorithm to find the sum of all elements in an array of integers.

Solution: let f (a, I) be the sum of the elements a[0]~a[I — 1] of the array A, which is a big problem; The small problem is f (a, I — 1), which is the sum of the I * — 1 elements a[0]~ A [I — 2]. If f (a, I — 1) has been found, then f (a, I) = f (a, I — 1) +a[I — 1], in addition, f (a, 1) =a[0], that is, the sum of an element is equal to the value of the element. The corresponding recursive model is as follows.

F (a,1)=a[0] F (a, I)= F (a, I - 1)+a[I - 1] When I >1Copy the code

The corresponding recursive algorithm is as follows.

int fun(int a[],int i) { if(i==1) return a[0]; The else return (fun (a, I - 1) + a) [I - 1]. }Copy the code

For the non-empty singly linked list L without leading nodes (node type is denoted by SLinkNode), whose node values are all integers and all nodes have different values, the following recursive algorithm is designed.

(1) Calculate the maximum node value;

(2) Find the minimum node value;

(3) Forward output of all node values;

(4) Reverse output of all node values.

Solution :(1) for unleaded list L, L is the pointer to the first data node, L — >next is also a unleaded list, which has only one less node than L. Let f1 (L) calculate the maximum node value in single linked list L, which is the original problem. The minor problem is F1 (L — > Next), which calculates the maximum node value in single linked list L — > Next, as shown in Figure 6.17.

Figure 6.17. Singly linked list without leading node

Assuming f1 (L – >next) has been calculated, it is obvious that f1 (L) = Max (L – >data, f1 (L – >next)); F1 (L) =L – >data when there is only one node in single list L. The corresponding recursive model is as follows.

The corresponding recursive algorithm is as follows.

(1) What is the meaning of the passage? The corresponding recursive algorithm is as follows.

(3) Let F3 (L) forward output all node values of single linked list L, which is the original problem. The minor problem is F3 (L — > Next), which is printing forward all node values of a single linked list L — > Next. Assuming f3 (L — > Next) is printed, it is clear that F3 (L) is equivalent to printing L — >data and then calling F3 (L — > Next). When L is empty, no output is done. The corresponding recursive model is as follows.

Where, “≡” represents the equivalence relation, and the corresponding recursive algorithm is as follows.

(4). The corresponding recursive algorithm is as follows.

It can be seen from the above algorithm design that small changes in recursive body will lead to widely different results of recursive algorithm execution. For example, the order of only two statements in algorithm (3) and (4) is reversed. The result is that the former outputs all node values forward and the latter outputs all node values backward.

Note: The single linked list without the lead node is usually used when the recursive algorithm is designed for single linked list. With headers, L and L — >next are inconsistent (the former has headers and the latter has none).