栈与递归

发表于 | 更新于: | 分类于 |

栈与递归的关系

  • 递归的本质其实就是栈，这点没错。之前一直认为可以用递归解的题，那么一定存在一个循环的方法，从而降低存储开销。而且递归和循环这两种方法可以画等号。但是并不是这样。递归和循环有时可以近似地看作等同(斐波那契数列)，有时不能(372超级次方)。
  • 递归其实是操作系统已经做好了栈的封装，每一次递归的时候，将当时的运行环境备份入栈，也就是说，这些都是操作系统已经帮我们做好的了。

    372题 超级次方

  • 毫无疑问，这道题无论是递归还是循环都能做。但是两者的思路截然不同，递归是从顶层n深入到底层，直到指数为0，才从栈顶返回。
  • 循环的思路是，利用位运算(二进制),只有当二进制的末尾为1时，才需要更新结果。其余时刻，只需要计算当前的乘法的结果就行了。
  • 其次，斐波那契的递归同样是从顶层n深入到底层，当n=1||n==0返回。斐波那契的递推方法用到的思路是动态规划。

真正用栈去模拟实现递归

拿超级次方这道题来说。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int pow(int a,int b){
    Stack<Long> stack=new Stack<>();
    while (b != 0) {
        //b为偶数
        if (b % 2 == 0) {
            stack.push(1L);
            b>>=1;
        }
        else if(b%2==1){
            stack.push(a*1L%MOD);
            b-=1;
        }
    }
    long base = 1;
    while(!stack.isEmpty()){
        Long pop = stack.pop();
        if(pop==1){
            base=base*base%MOD;
        }else{
            base=base*a%MOD;
        }
    }
    return (int) base;
}

  • 以上代码模拟了真实栈的出栈与入栈。虽然入栈的规则是自己定义的(真实环境中可能还会保存段基址和指令地址).
  • 同样，斐波那契数列的栈实现如下.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    public int fib(int n) {
            if(n==0) return 0;
            if(n==1) return 1;
            Stack<FiboNode[]> stack=new Stack<>();
            FiboNode f1 = new FiboNode(n - 1, false);
            FiboNode f2 = new FiboNode(n - 2, false);
            FiboNode[] arr=new FiboNode[2];
            arr[0]=f1;arr[1]=f2;
            stack.push(arr);
            int base=0;
            while(!stack.isEmpty()){
                FiboNode[] pop = stack.pop();
                FiboNode n1 = pop[0];
                FiboNode n2 = pop[1];
                int val = n1.val;
                if(!n1.visited){
                    stack.push(pop);
                    if (val == 0) {
                        base += 0;
                    } else if (val == 1) base += 1;
                    // 入栈
                    else {
                        FiboNode[] array=new FiboNode[2];
                        FiboNode fiboNode = new FiboNode(val - 1, false);
                        FiboNode fiboNode1 = new FiboNode(val - 2, false);
                        array[0]=fiboNode;
                        array[1]=fiboNode1;
                        stack.push(array);
                    }
                    n1.visited=true;
                }else if(!n2.visited){
                    int val1 = n2.val;
                    if (val1 == 0) {
                        base += 0;
                    } else if (val1 == 1) base += 1;
                    // 入栈
                    else {
                        FiboNode[] array=new FiboNode[2];
                        FiboNode fiboNode = new FiboNode(val1 - 1, false);
                        FiboNode fiboNode1 = new FiboNode(val1 - 2, false);
                        array[0]=fiboNode;
                        array[1]=fiboNode1;
                        stack.push(array);
                    }
                }
            }
            return base;
        }
    }
    class FiboNode{
        int val;
        boolean visited;
    }