Shulou(Shulou.com)06/02 Report--

This article shows you how C++ explicit stack to achieve recursion, the content is concise and easy to understand, absolutely can make your eyes bright, through the detailed introduction of this article, I hope you can get something.

Preface

In the university class, the teacher has taught, that is, to use loops to achieve recursion, now review and take notes.

1. Recursion

Suppose there are function An and function B, function B is a recursive function, and function A calls function B.

This recursive process is divided into:

Function A calls function B, and function A passes data to function B. At this point, inside function B, function B gets the data from function A by passing parameters. The operation that performs this call passes the new data into function B as an argument (recursive procedure, internally performing step 2-3 again, and so on). Exit recursive end.

two。 The idea of explicit Stack implementation

From the above process, it is not difficult to see that the recursive process follows such a rule of late entry and exit. Then it is easy to think of a data structure such as a stack with the same characteristics. The idea of explicit stack recursion is given here:

Suppose you have applied for a container for stack

First, press the initial data on the stack, which is similar to the operation in which function A first calls function B in the recursive process. Then there is the loop operation, the condition is true, that is, the dead loop, which is similar to the recursive call within function B, and when it ends depends on when the recursive exit is encountered; in this dead loop, a conditional decision should be made in each loop, which is equivalent to the conditional decision in the recursive function to determine when to return. Next, go inside the loop, first take the data from the top of the stack, which is similar to function B, which takes the key operation of passing parameters to perform this loop, and the task of processing the data presses the new data on the stack. This part is equivalent to passing the new data into the function B as a parameter. If the loop exit condition is triggered, the loop will exit.

3. Code parsing

The above said the specific ideas, now use the code to explain, first of all on the recursive writing, using traversing the binary tree as an example.

# includeusing namespace std;class Node {public: int value; Node* left_child; Node* right_child; Node (int data) {this- > data = data; this- > left_child = nullptr; this- > right_child = nullptr;}} Void B (Node* node) {/ / has gone through step 2 at this time. Function B gets the data root / / step 3 and performs the key operations of this recursive call: cout dataleft_child and root- > right_child / / call function B if (node- > left_child) B (node- > left_child); if (node- > right_child) B (node- > right_child) / / step 5, recursively end} void A () {Node root (10); / / simulate a tree B (& root); / / step 1, pass parameters} int main () {A ();} the order of steps 3 and 4 above is not fixed, and their different order constitutes different tree traversal methods (first order, middle order, later order traversal). Next is the explicit stack implementation # include#includeusing namespace std;class Node {public: int value; Node* left_child; Node* right_child; Node (int data) {this- > data = data; this- > left_child = nullptr; this- > right_child = nullptr;}} Int main () {Node root (10); / / simulate a tree stack massistack; m_stack.push (& root); / / step 1, stack the root node, which is equivalent to passing the parameter while (true) {if (m_stack.empty ()) {break when function A calls function B. / / this is equivalent to step 5 to determine the end condition of the loop, or you can write it on the while condition / / for a clearer idea, so write it in the loop, and it is better to compare it with the recursive version} / / step 2 Take the top stack element Node* current_node = m_stack.top () M_stack.pop (); / / step 3, perform the key operations of this cycle: cout dataleft_child) m_stack.push (current_node- > left_child); if (current_node- > right_child) m_stack.push (current_node- > right_child) In the version of explicit stack implementation, one detail is that after fetching the data at the top of the stack, you need to unstack the data at the top of the stack, so that you can use the stack to determine whether the stack is empty or not. The above is how C++ explicit stack implements recursion. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.