尾递归和单向递归的消除不需要借用栈

单向递归和尾递归可直接用迭代实现其非递归过程

其他情形必须借助栈实现非递归过程。

证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i

   i

   若Pi>Pj 说明大的数先于小的数出栈，那么在Pi出栈前Pj一定在栈中

证明：1）j

   2）iPk 说明Pi出栈前，Pk在栈中

   3）iPj 说明Pi出栈前Pj在栈中

   而Pi是最先出栈的那么在Pi为栈顶的时候，Pj和Pk一定都同时被压入栈中，那么就与1矛盾了，1要求Pj要在Pk入栈前出栈，而此时Pk Pj都在栈中所以假设不成立。