递归和非递归

二叉树的遍历中

• 有两种实现
• 递归
• 非递归（迭代）

事实上，在解决一些问题的时候，经常使用到递归函数。
万一哪天为了追求效率，非要写迭代呢。

迭代就是：

考虑，递归其实是让系统来做栈的操作。
所以迭代，其实，就是我们来做系统本来要做的事情。

系统对于一个函数入栈会存储哪些东西？

• 正在操作的数据
• PC
• 返回指针

我们需要的是：正在 ** 操作的数据，PC**，记录当前程序运行到哪个位置，以确定下一步做什么。

但是往往，PC 不需要被记录。

例子

#前序遍历，中序遍历，后续遍历

后面会聊下后续吧

static void swap(int[] array,int i,int mark){
    if(i!=mark) {
        int tmp = array[i];
        array[i] = array[mark];
        array[mark] = tmp;
    }
}

#快速排序
    //常见的快速排序实现
    static void quick_sort(int array[],int start,int end){
        if(end<=start){return;}
        int middle = array[start];
        int mark =start;
        for(int i=start+1;i< end+1;i++){
            if(array[i] < middle){
                swap(array,i,mark+1);
                mark++;
            }
        }
        swap(array,start,mark);
        quick_sort(array,start,mark-1);
        quick_sort(array,mark+1,end);
    }

#一个非递归的快速排序
static class QS{
    int start,end;
    int pc;
    QS(int start,int end){
        this.start=start;
        this.end = end;
    }
}//可以注意到，存储的就是传入的操作数。
//其他的数，在每一轮里面都是由这两个数来决定的，所以这里只存储两个数

#不知道还有没有别的情况，但是至少遍历和这个都是存储的，递归中的
#输入参数

    static void qs2(int array[]){
        Stack<QS> stack =new Stack<QS>();
        QS node = new QS(0,array.length-1);
        while(!stack.isEmpty()|| node!=null){

            while(node.end<=node.start){
                if(!stack.isEmpty())
                    node=stack.pop();
                else{
                    return;
                }
            }
            int middle = array[node.start];
            int mark = node.start;
            for(int i=node.start + 1;i< node.end + 1;i++){
                if(array[i] < middle){
                    swap(array,i,mark + 1);
                    mark ++;
                }
            }
            swap(array,node.start,mark);
            stack.push(new QS(mark+1,node.end));
            node = new QS(node.start,mark-1);

        }
    }

#关于非递归的后序遍历
伪代码：

void post(Node node){
    post(node.left);
    post(node.right);
    node.print();
}
void postTravel(Node node){
    while(node!=null){
        Stack.push(node);
        node =node.left;
    }
    node.pop();
    if(pc==1){//压入的位置
        node.Sprint
    }else{
        node.push(node);
        node=node.right;
    }
}

什么时候要用PC

为什么前序和中序遍历，不需要用PC呢？
而后序要。
看了前序，中序，后序的递归函数，没有看出什么差别。

差别就在于stack.pop()之后的操作有几种。
前序和中序，pop()之后都是直接打印出来，后面操作只有一种。
{
1.打印出来
}
但是后序，pop()的时候，有两种情况
{
1.node=node.right
2.node打印出来
}