Recurrent traversal and non-recursion
I have written some articles about recursive, because I haven't written it yet, so I can't give more convincing examples, just explain "recursion is a kind of thinking", just like netizens evaluation, "an article Getting started. " But as long as you can build "recursive is a kind of thinking" this concept, my efforts have no white feet. Now, the binary search tree is finished, and finally there is an example that can explain the problem. According to the code provided earlier, you should be able to debug the following program.
#include
Using namespace std;
#include
#include
#include "bstree.h"
#include "timer.h"
#define random (NUM) (Rand ()% (NUM))
#define randomize () SRAND (NULL) TIME (NULL)
#define nodenum 200000 // Node Number
Int data [nodenum];
Void Zero (INT & T) {T = 0;
int main ()
{
BSTREE
For (i = 0; i For (i = 0; i T.Start (); for (i = 0; i Cout << "Insert Time:" << T.gettime () << "/ tnode number:" << nodenum << endl; T.Start (); for (a.first (); a.get ()! = null; a.next ()) a.get () -> DATA = 0; COUT << "Non-Stack Time:" << T.gettime () << endl; T.Start (); a.LEVELORDER (ZERO); cout << "LevlORDER TIME:" << T.gettime () << endl; T.Start (); A.PREORDER (ZERO); cout << "preorder time:" << T.gettime () << endl; T.Start (); a.inorder (zero); cout << "inorder time:" << T.gettime () << endl; T.Start (); a.postorder (zero); cout << "PostORDER TIME:" << t.gettime () << endl; Return 0; } The following is the content of Timer.h #ifndef Timer_H #define Timer_H #include Class Timer { PUBLIC: Timer () {QueryperFormanceFrequency (& Frequency);} inline void start () {queryperformancecounter (& Timerb); Inline Double GetTime () { QueryperFormanceCounter (& Timere); Return (Timere.quadpart - Timerb.quadpart) / (Double) Frequency.quadpart * 1000.0; } Private: Large_integer Timerb, Timere, Frequency; } #ENDIF In the above program, the hierarchical traversal is the queue, which should represent the case where the stack is decatible, and the result of running on my machine C500 is: INSERT TIME: 868.818 Node Number: 200000 Non-Stack Time: 130.811 LevlORDER TIME: 148.438 Preorder Time: 125.47 Inorder Time: 129.125 PostORDER TIME: 130.914 The above is the result of the Release version of VC6, and the time unit is MS, and it does not mean that some people will think is a crash, ^ _ ^. It can be seen that recursive traverses is actually not slow, the opposite, faster, and the result of the debug version is this: INSERT TIME: 1355.69 Node Number: 200000 Non-Stack Time: 207.086 LevlORDER TIME: 766.023 Preorder Time: 183.287 Inorder Time: 179.835 PostORDER TIME: 190.674 The speed of recursive traversal is the fastest This is probably the most direct conclusion that the above results are obtained. I don't know where to listen to "The recursive speed is slow, in order to improve the speed, you should use the stack to understand recursive", the evidence is the calculation of the Fiboacci number, and unfortunately the non-intended algorithm of the Fiboaccai number is the loop. Not a stack undeterained; if he really took the stack to simulate, he will find that there is a slower use of the stack. Let's take a look at why. The recursive implementation is to stack the parameters, then Call itself, and finally returned according to the layer, a series of actions are operated on the stack, using instructions such as PUSH, POP, CALL, RET. The ADT stack is used to simulate recursive calls, and the functions of the above instructions are achieved, and the ADT implementation of those instructions can be not just a directive. Who understands that the implementation efficiency of the simulation is definitely better than the true difference, how can I become in this question? Of course, you have to add ISTREAM FILE1 ("Input.txt") in the Visit function, and then put this on the loop with the stack simulation, and finally you said that the stack simulation is fast, I There is no way to say that I have seen someone, http://www.9cbs.net/develop/read_article.asp? Id = 18342 put the database connection in the Visit function, and then the recursive speed is slow. If a recursive process is implemented with a non-recursive method, the speed is improved, that is just because of the recursive doing some useless work. For example, with a loop digestion, it is a non-use stack and out of the stack to make the speed damage; the recursive recursive recursive cycle iteration of the Fiboacciped number is greatly improved, because it has changed repeated Calculated problems. If a recursive process must be remelted with a stack, then the result will not be improved at the speed after full simulation, will only slow down; if you have improved it, then you only prove your recreation function There is a problem, such as many duplicate operations - open the shutdown file, connect the disconnect database, and these can be exactly the outside. The recursive method itself is concise and efficient, but people use non-payment methods. In this way, the research recursive stack eliminates it is useless, in fact, it is still a bit meaningful to use stack simulation, but not large, the example will be given below. The advantage of the stack simulation is to save the stack. The value of the above program // node number is changed to 15000 - do not change, don't react, don't find me, please comment on // random swap, run the debug version, wait patiently for 30 seconds, will throw anomalia The final output is like this: INSERT TIME: 27555.5 NODE NUMBER: 15000 Non-Stack Time: 16.858 LevlORDER TIME: 251.036 This can only explain the stack overflow. You can see that levels of traversal can work (such push, stack simulation can work), but recursive can't work. This is because the total memory space is rare, and the stack space is very small. If the recursive level is too deep, the stack overflows. So, if you are in advance, you may have excessive levels, you have to consider using the stack to digest. However, if you have to use recursive, the recursive level is deeply overflow, it is definitely your algorithm has problems, or that program is not suitable for running on the PC - running, like a crazy, so Who dares to use? Therefore, it means that the stack simulation recursive is meaningful, but it is not large because it is rarely used. For the tree structure, if there is no double-friend pointer, the recursive recursive is necessary, and what stack is not asked to add a double-pro-pointer, which actually exchanges a method of stack space with a heap space, just than the ADT stack. Direct, high efficiency. In summary, the recursive stack is decomposed, in fact, can only save the stack space, not only will not increase the speed, but the opposite will be reduced - there is a white lunch in the world, which will save the stack space and improve the speed. The rumors of those "stack elutable recursive energy" are just the irresponsible quotation of "Elimination of tailings to improve the speed", but a group of people are rumored, really like that, this is three people tiger. When I went back to the head and read the textbook, I didn't see a book "Stack eligibility recursive energy improvement speed." Really, I have been misleading before, I don't know who is misleading - the book is not written at all. Additionally conclusion In contrast the above two sets of results, it can be seen that inserting 15,000 nodes consumes more than 200,000 nodes, the reason is that the order of inserting data is different, resulting in different efficiency of the Find. The random order can generally guarantee that the left and right subtree distribution of the tree is uniform, and the orderly sequence will give the tree to a single linked list, so that the time complexity of the O (logn) is O (N). At the same time, this is also why 200,000 nodes of tree will be able to work, while recursively traversing 15,000 nodes of tree stacks overflow - there are too few nodes corresponding to each layer of recursive.
