Algorithms that can be described recursively usually have the following characteristics: in order to solve the problem of scale n, try to decompose it into smaller problems, and then conveniently construct the solutions of large problems from the solutions of these small problems. These smaller problems can also be decomposed into smaller problems by the same decomposition and synthesis method, and the solutions of larger problems can be constructed from the solutions of these smaller problems. Especially, when the scale N= 1, the solution can be obtained directly.
The implementation process of recursive algorithm is divided into two stages: recursion and regression. In the recursive stage, the solution of a more complex problem (scale n) is pushed to the solution of a simpler problem (scale less than n) than the original problem. For example, in the above example, solve fib(n) and deduce fib(n- 1) and fib(n-2). That is to say, in order to calculate fib(n- 1) and fib(n-2), fib(n- 1) and fib(n-2) must be calculated first, and fib(n-3) and fib(n-4) must be calculated first. And so on, until fib( 1) and fib(0) are calculated, the results of 1 and 0 can be obtained immediately. In the recursion stage, there must be circumstances to terminate recursion. For example, in the function fib, when n is 1 and 0.
In the regression stage, when the solution of the simplest case is obtained, it returns to the solution of a slightly complicated problem step by step, for example, after obtaining fib( 1) and fib(0), it returns the result of fib(2), ..., after obtaining fib(n- 1) and fib(n-2).
When writing a recursive function, it should be noted that the knowledge of local variables and parameters in the function is limited to the current calling layer. When it is pushed to the Simple Problem layer, the parameters and local variables in the original layer are hidden. In a series of simple problem layers, they all have their own parameters and local variables.
Because recursion causes a series of function calls, and there may be a series of repeated calculations, the execution efficiency of recursive algorithm is relatively low. When recursive algorithm can be easily converted into recursive algorithm, programs are usually written according to recursive algorithm. For example, in the above example, the function fib(n) of the nth term of Fibonacci sequence is calculated by recursive algorithm, that is, the next term is calculated one by one from the first two terms of Fibonacci sequence until the required nth term is calculated.
Selective sorting method is an improvement of positioning comparison exchange method. Before talking about the selective sorting method, let's first understand the positioning comparison exchange method. For easy understanding, 10 numbers are set in array elements A [0] ~ A [9] respectively. The positioning comparison exchange method locates the appropriate values in A [0] ~ a[9] from large to small (similar to the Wulin Congress), and the number placed in a[9] is naturally the smallest. If a[0] is located, it is assumed that the current value in a[0] is the maximum number, and a[0] is compared with the following elements one by one. If a[4] is relatively large, a[0] and a[4] are exchanged, and a[0] has been updated and then compared with the following A [5] ~ a[9]. If A [4] is relatively large, after a round of competition, a[0] is the largest number, and the Wushu champion of this competition is born. Next, start with a[ 1], because the champion is going to have a rest, and another round of a[ 1] is the second largest number, that is, the second place, and then start with a[2], and it will really be a competition.
Let's give an example:
Mai ()
{
int a[ 10]；
int i，j，t；
for(I = 0； I< 10; i ++ ) scanf("%d "，& ampa[I])； /* Enter the number 10 to sign up for the tournament, and the registration fee is 10000 _ */
for(I = 0； I<9; i ++)
for(j = I+ 1； j & lt 10; j ++)
if(a[I]& lt； a[j]){ t = a[I]； a[I]= a[j]； a[j]= t； }/* If you can't beat it, you should give way to the top spot, but a[ i] has more face. I was sad to see a[ j], so I asked T to help */
for(I = 0； I< 10; i ++) printf("%4d "，a[I])； /* Display sorting results */
}
Well, after a long time, I finally finished the positioning comparison sorting method. This method is good and easy to understand, but it is a bit troublesome. I have to change my chair, hey ~
So there is the following selection sorting method. At first, no one will be given chairs. Everyone will watch, find someone to record the results of the game, and then give chairs. Specifically, it is to improve the positioning comparison sorting method, but this improvement is only a part, the number of comparisons has not changed, how to play or how to play, that is, there is no need to change chairs. In each outer loop, the I value of the small label of the positioning element is recorded to k first, and it is considered that a[k] is the largest element. In fact, i=k or a[ i] is the largest. Compare a[k] with the following elements one by one, exchange them without changing the value of K, and finally exchange a[k] with a[ i] to make A the largest element. Then enter the next round of comparison. Compared with the positioning comparison sorting method, the selection sorting method has the same comparison times and reduces the exchange times.
Here's an example:
Master ()
{
int a[ 10]；
int i，j，t，k；
for(I = 0； I< 10; i ++ ) scanf("%d "，& ampa[I])； /* Enter the number 10 to sign up for the tournament, and the registration fee is 10000 _ */
for(I = 0； I<9; i ++)
{ k = I； /* Referees and reporters track and report the game in real time */
for(j = I+ 1； j & lt 10; j ++)
if(a[k]& lt； a[j])k = j；
t = a[I]； a[I]= a[k]； a[k]= t； /* Don't give prizes */
}
for(I = 0； I< 10; i ++) printf("%4d "，a[I])； /* Display sorting results */
}