通过递归调用来测试虚拟机栈的深度

小鱼儿 2021-12-13 20:17 103阅读 0赞

我们知道在JVM内存模型中有个虚拟机栈的存在，它存在的目的是保存方法以及局部变量。

栈其原理是：它本身是一个栈的结构，那么栈的结构特点是，压栈和弹栈，当调用一个方法时，就创建一个该方法的栈帧，将其压入到虚拟机栈中，当该方法执行结束时，就将该栈帧弹出虚拟机栈。

按照这种原理，如果给定一个虚拟机的栈的深度，即栈的缓存容量，并且入栈和弹栈的效率假设是一样的话，那么就不存在神马StackOverFlowException异常了，那么到底是不是这样呢？我们用一个斐波那契数列测试一下：

package org.chenjianwen.test;
    
    public class Fibonacci {
    
        //F(0)=1,F(1)=1;当n>=2的时候，F(n)=F(n-1)+F(n-2)
        //例如：F(2)=F(1)+F(0)=2;F(3)=F(2)+F(1)=3...
        //F(0)~F(n)依次为：1,1,2,3,5,8,13,21...
        public static int fibonacci(int n){
            if(n < 0){
                throw new RuntimeException("n不可为负数");
            }
            if(n == 0){
                return 1;
            }
            if(n == 1){
                return 1;
            }
            return fibonacci(n-1) + fibonacci(n-2);
        }
    
        public static void main(String[] args){
            System.out.println(fibonacci(18));
        }
    }

当递归调用比较少的时候，例如10～20之间是可以运行的，但到50以上时，运行就卡壳了，当1000000时就会报出如下栈溢出异常。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JveV9jaGVuOTM_size_16_color_FFFFFF_t_70][]

由此可见，实际结果并不是像我们所想的那样，入栈和弹栈效率是一样的，那结果肯定是入栈的效率远远大于出栈的效率，导致栈帧的在虚拟机栈中的积压，从而导致栈帧数超出虚拟机的深度。

那么，有什么解决方法呢？两种，第一减少递归调用的次数，第二，如果不想减少递归调用次数，可以用循环代替，如下：

public static int[] circulationInvoke(int n) {
            int[] arr = new int[n];
            if (n == 1) {
                arr[0] = 1;
            }
            if (n == 2) {
                arr[0] = 1;
                arr[1] = 1;
            }
            if(n > 2){
                arr[0]=1;
                arr[1]=1;
                for (int i = 2; i < n; i++) {
                    arr[i] = arr[i - 1] + arr[i - 2];
                }
            }
            return arr;
        }
    
    public static void main(String[] args) {
            int[] arr = circulationInvoke(8);
            for (int x : arr) {
                System.out.println(x);
            }
        }

end。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JveV9jaGVuOTM_size_16_color_FFFFFF_t_70]: /images/20211213/b8e4cdcac3bd4c918058c47ca77cb40c.png