java 递归速度和内存_java递归传递字节数组特别慢

通常来说，java递归函数运行一般比循环函数慢，有时候甚至是一倍的差距，看下面的代码

public class RecursiveCall {
    public static void main(String[] args) {
        int total = 0;
        int first = 100;
        for (int x = 0; x < first; x++) {
            int n = 1000000;
            long start = System.currentTimeMillis();
            for (int i = 0; i < n; i++) {
                r(10);
            }
            total += (System.currentTimeMillis() - start);
        }
        System.out.println("average:" + total / first);

    }

    public static int r(int x) {
        if (x == 1) return 1;
        return x * r(x - 1);
    }

    public static int l(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}
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

测试结果如下

虽然不知道为什么循环函数平均是0，但是，目测应该是jvm做了某些优化，而我不知道，同时，我们看jvm消耗，发现一个小小的测试方法，却消耗了大量的内存

当循环10000次的时候，内存消耗大概为6M，这对于一个小小的计算问题，消耗算是时分巨大的。为什么会消耗如此多的内存，我们需要看看java 递归时的内存stack frame中的变化情况。进入idea的debug模式，

代码是最简单的递归

 public static void main(String[] args) {
        int result = r(10);
        System.out.println(result);
    }
1
2
3
4

这是刚进入main函数的时候的stack frame的情形，为了更加简化的显示我们只截图frame，就是最左边两个（frame + variable）。

第一个递归。

第2个递归。

第9个递归：

我们可以很清楚的看到，对于一个递归来说，它需要调用自己10次（最后一次debug不显示）,知道最后一次才会返回结果，同时抛出这个stack frame，可以看见，在一个简单的方法中，这里消耗了10倍（仅仅这个例子）的内存，这增加了9倍的消耗，这是很难接受的。

时序图（也许不合适），在终止条件前，所有的自我调用都会消耗一个stack frame，如果自我调用次数多的话，那么，那是非常容易造成内存溢出的。

综上所述，递归一般是不被推荐的，当然，适当的利用递归的确可以简化代码，却是在好好思考之后做出的决定。