Let’s look at an example of recursion

#include <iostream><br/><br/>
using namespace std;
void func(int n) {
	if (n >= 10) return ;
	int i = 0;
	i++;
	printf("%d\n", i);
	func(n+1);
}
int main() {
	func(0);
	return 0;
}
Copy the code

The printed output is a bunch of ones, local variables in the recursive process still maintain the life cycle and scope of local variables, so the key factor of recursion is parameter, recursive process is the process of parameter stack, recursive process is the process of stack




Let’s do a recursive problem

Symmetric binary tree

recursively
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return comRoot(root->left, root->right);
    }
    bool comRoot(TreeNode* left, TreeNode* right){
        if(left == NULL)
            return right == NULL;
        if(right == NULL)
            return false;
        if(left->val != right->val)
            return false;
        return comRoot(left->left, right->right) && comRoot(left->right, right->left);
    }
};
Copy the code
Through debugging

The essence of recursion is that parameters are being pushed and pushed

The iterative method uses queues
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root) { if (root == NULL) return true; queue<TreeNode*> que; que.push(root->left); Que. push(root->right); que.push(root->right); // queue the right subtree header while (! Que.empty ()) {TreeNode* leftNode = que.front(); que.pop(); TreeNode* rightNode = que.front(); que.pop(); if (! leftNode && ! RightNode) {// the left node is empty, the rightNode is empty, and the statement is symmetric continue; } // Return false if ((! leftNode || ! rightNode || (leftNode->val ! = rightNode->val))) { return false; } que.push(leftNode->left); Que. push(rightNode->right); // Add left node left child que.push(rightNode->right); Que. push(leftNode->right); Que. push(rightNode->left); que.push(rightNode->left); } return true; }};Copy the code

In this iteration method, the elements to be compared between the left and right subtrees are put into a container in order, and then taken out in pairs for comparison. In fact, it is also possible to use the stack. Just change the queue to the stack.

Iterative methods use stacks
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root) { if (root == NULL) return true; stack<TreeNode*> st; // stack st.push(root->left); st.push(root->right); while (! st.empty()) { TreeNode* leftNode = st.top(); st.pop(); TreeNode* rightNode = st.top(); st.pop(); if (! leftNode && ! rightNode) { continue; } if ((! leftNode || ! rightNode || (leftNode->val ! = rightNode->val))) { return false; } st.push(leftNode->left); st.push(rightNode->right); st.push(leftNode->right); st.push(rightNode->left); } return true; }};Copy the code

All recursion can be changed cycle, the function of the stack process, their own manual implementation to complete the requirements of violent recursion change rules