1 Introduction Problem Problem can be divided into two categories: The first category is a mathematical recursive function, requires a function value, such as a step multiplier function, and a Fibonacci function; the second type of problem has recursive feature, the purpose is to meet some Conditional sequence of operations, such as Hanoi Tower and Eighthuang Question. The programming of the first type of problem is simple, mechanical, and second types of questions. Otherwise, due to the broad, there is no unified rule, so the programming process is often more complicated, and the procedures have not been well understood. . The reason is that the first type of problem has a ready-made function formula, and the second category is not. If we can write its recursive formula for the second type of question, the encoding process will greatly simplify, and the readability of the program can also be improved. This article will discuss this method with two program instances.
2 Formulating method programming can be divided into two phases: logical phase and implementation phase. The logical phase is to determine the algorithm without having to consider the programming language and implementation. Usually, the algorithm can be expressed in a natural language, flow chart, and NS map. For a second type of problem, it can be detrimentary formula in a logical stage, then there are at least a few benefits: 1. That is truse in the same implementation stage Separate, greatly simplify the programming. 2. Division of recursive formulas with mathematical methods should be much simpler than the calculation of other methods. 3. Since the formula is the most accurate and simple description form of the algorithm, there is a recursive formula, and the encoding work becomes unusually simple, and the readability of the program will be good. The so-called formula method for the recursive programming, first to expose the problem into a recursive function in mathematical sense, then the key is to determine the meaning of the function value, although the problem does not necessarily need to calculate what functionality. The selection of function values may not be unique, but the improvement of the improvement of the performance is better. The Hanoi Tower requires that the action to take several plates from a column to another column, we can take the number of movements as a function value. So the recursive function h (d, f, t, u) having four arguments is to move the D plate (Disks) from the F column (from) to the T column with the U.SING. TO). It is easy to obtain the following recursive formula: h (1, f, t, u) = 1 h (d, f, t, u) = H (D-1, f, u, t) h (1, f, t, u) h (D-1, U, T, F), if D> 1 is very significant: move a tray only one action; and move the D plate on the F column to T The column, you need to move the above D-1 tray from the F column to the U column, then move the lowermost plate from the F column to the T column, and finally move the D-1 tray on the U column to T to T The column, therefore the total number of movements is equal to the sum of three sets of action. With recursive formula, programming is extremely simple. The structure of the program is a multi-branch structure, and it is better to correspond to the recursive formula, and the programming has almost become mechanical translation. In the following program, the difference between the recursive function and the recursive formula only is set to 1 when D is 1, but also to display this action. Main () {INT D, V, H (int, int, int, int); Printf ("disks ="); scanf ("% d", & d); v = H (D, 1, 2, 3) PRINTF ("/ N% D Actions for% D Disks! / N", V, D);} int h (int D, int F, int T, int u) {INT I, V; IF (D == 1) {v = 1; Printf ("% d ->% d", f, t);} else v = H (D-1, f, u, t) h (1, f, t, u) h (D-1, U, T, F); RETURN V;} The running session of this program is as follows: disks = 31-> 2 1-> 3 2-> 3 1-> 2 3-> 1 3-> 2 1-> 27 Actions for 3 Disks!
3 examples: The eight queen of the eight queen [2] is a more representative and more complex recursive example, requiring 8 Queens on 8 × 8 chess boards, making them not attacking each other. The algorithm we take is still putting a queen from the first line of the chessboard. It is placed from the first column of the line from the line, and it is judge whether it attacks each other with each of the Queen's queen, if you replace it into the next column. Otherwise, continue to place the next queen until 8 Queen. According to this idea, we define a function of 9 arguments: q (k, A1, A2, A3, A4, A5, A6, A7, A8) where K indicates the number of queen the queen, and Ai (this I <= k) represents the column number of the queen on the first line, so the 9 index can represent the state of any time during the solution, and the function value is defined as the solution that can be obtained from this state. number. According to this idea, it is not difficult to get the following recursive formula: Q (k, a1, ..., ak, 0, ... 0) = 0 If there is 0
