Java数据结构与算法笔记——利用栈来消除递归

消除递归

递归对于分析问题比较有优势，但是基于递归的实现效率就不高了，而且因为函数栈大小的限制，递归的层次也有限制。所以消除递归就显得很重要了，这样我们可以在分析阶段采用递归思想，而实现阶段把递归转变成非递归算法。

比如：求1+2+…+n的值：

//利用递归，求1+2+3+....+n的值
    public static int addn(int n){
        if(n==1){
            return n;
        }else {
            return n+addn(n-1);
        }
    }

递归和栈有着紧密的联系，而且大多数编译器都是用栈来实现递归的，这里我们就模拟一下底层编译器的处理方法来转换递归算法。
现在把上面的递归算法，利用栈变成非递归算法：

package recursion;

import java.util.Stack;

public class RecursionTest7 {
    public static void main(String[] args) {
        System.out.println(addn1(4));

    }
    
    
    //依靠栈消除递归
    public static int addn1(int n){
        Stack<Params> stack = new Stack<>();
        int currentReturnValue = 0;//记录累加过程的中间结果和最终结果
        int currentReturnAddress = 1;//初始化为第一个状态
        Params params = null;

        boolean flag = true;
        while (flag){
            switch (currentReturnAddress){
                case 1:
                    //初始化：初始参数封装为对象，压入栈。设置一下走的分支地址
                    params = new Params(n,6);//adress设置为6，这样当处理到这个Params之后，程序就跳转到case6，循环结束
                    stack.push(params);
                    currentReturnAddress = 2;
                    break; //跳出switch语句
                case 2:
                    //模拟递归算法的边界条件，满足边界条件就把值赋给currentReturnAddress，设定下一跳为5.如果不满足，设置下一跳为3
                    params = stack.peek();
                    if(params.getN() == 1){
                        //n等于1时为边界条件，跳转到状态5
                        currentReturnValue = params.getN();
                        currentReturnAddress = 5;
                    }else {
                        //没满足递归停止条件，进入状态3，进行递归
                        currentReturnAddress = 3;
                    }
                    break;
                case 3:
                    // 模拟递归，n-1作为新的参数，压入栈，参数对象类的返回地址4，设置下一跳：2
                    params = stack.peek();
                    params = new Params(params.getN()-1,4);
                    stack.push(params);//n-1入栈
                    currentReturnAddress = 2;
                    break;
                case 4:
                    //实现累加。将栈中参数取出，做叠加操作，叠加到currentReturnValue中，设置下一跳：5
                    params = stack.peek();
                    currentReturnValue += params.getN();
                    currentReturnAddress = 5;
                    break;
                case 5:
                    //把第4分支已经叠加过的参数从栈里删除，根据参数对象中的返回地址，设置下一跳地址
                    params = stack.pop();
                    currentReturnAddress = params.getReturnAddress();
                    break;
                case 6:
                    //结束循环，等同于递归完毕
                    flag = false;//完成运算结束while循环
            }
        }

        return currentReturnValue;
    }


}


/**
 * 封装参数类
 * 将参数n和returnAddress封装在一起
 */
class Params{
    private int n;
    private int returnAddress;

    public Params(int n, int address){
        this.n = n;
        this.returnAddress = address;
    }

    public int getN() {
        return n;
    }

    public int getReturnAddress() {
        return returnAddress;
    }
}