This recursive process is very simple, but it is not easy to understand if a complex recursive algorithm can be understood. The following method can help you analyze, I hope.
One. Example (description from C ):
Line number program
0 p (int W)
1 {IF (w> O)
2 {cout << w;
3 p (W-1);
4 p (W-1);
5}
6}
end
Print results after executing statement P (4): 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1
two. Description:
1. Recursive calls are the same as the principle of ordinary calls, but it is only the functions of each call.
2. We can fully program the settings of the stack (user stack) to implement the same features as "recursive calls".
3. 3. When "recursive call", the system will automatically set and manage the stack (system stack), and
No need to intervention, but this also increases the mystery of "recursive call". For better
Geographical solution "recursive call", now the system stack is expressed in a table.
4. Some instructions on the "stack" format
The format of the stack is:
Checkered A Grid B Quality C Function Call the value of the function W returned
Each time the function is called, "into the stack" once; the function is executed, "out of the stack" once
three. Program explanation:
1. Start calling p (4), the statements performed at this time are: 1, 2, 3
End P (4) 4
Perform P (4) Statement 2: Cout << W; Print 4 (this is the first result)
However, because of the statement 3, P (3) is also called during the execution process, and only P (3) is completed, and P (4) can be continued.
2. Start calling P (3), the statements performed at this time are: 1, 2, 3
4 p (3) 3 End P (4) 4
When P (3) is executed, the statement 4 in P (4) is performed (so in square a, "4").
Perform P (3) statement 2: cout << W; Print 3 (this is the second result)
Similarly to the above situation, when executed to the statement 3, also call P (2), only P (2) is executed, can continue to perform P (3).
3. Start calling P (2), the statement executed at this time is: 1, 2, 3
4 p (2) 2 4 p (3) 3 End P (4) 4
Perform P (2) statement 2: cout << W; Print 2 (this is the third result)
Similarly to the above situation, when executed to the statement 3, P (1), only P (1) is executed, can continue to perform P (2).
4. Start calling P (1), the statements performed at this time are: 1, 2, 3
4 p (1) 1 4 p (2) 2 4 p (3) 3 End P (4) 4
Perform P (2) statement 2: cout << W; Print 1 (this is the fourth result)
Similarly to the above situation, when executed to the statement 3, also call P (0), only P (0) is executed, in order to continue P (1).
5. Start calling P (0), the statement performed at this time is: 14 p (0) 0 4 p (1) 1 4 p (2) 2 4 p (3) 3 end P (4) 4
Because W = 0 does not satisfy the statement 1, it is only possible to jump directly to the statement 5, 6, so that P (0) is executed, P (0) is to perform "out of the stack" operation.
6. The statement executed at this time is: 4
4 p (1) 1 4 p (2) 2 4 p (3) 3 End P (4) 4
Since P (0) is performed, the square A of P (0) is 4, thus continues to perform the statement 4: p (W-1) of P (W-1); another due to P (1) square C The value is 1, so P (0) is called.
