Java中的递归调用

时间:2022-06-22 08:38:44

  Java中不合理的使用递归调用,可能会导致栈内存溢出,这点是需要注意的。

  

  java将为每个线程维护一个栈,栈里将为每个方法保存一个栈帧,栈帧代表了一个方法的运行状态。 也就是我们常说的方法栈。最后一个为当前运行的栈帧。

  那么每一次方法调用会为新调用方法的生成一个栈帧,保存当前方法的栈帧状态,栈帧上下文切换,切换到最新的方法栈帧。

  在递归和循环之间选择时,应该优先选择的是循环而非递归,特别是要避免深度的递归。

  

  关于递归还需要了解的是尾递归调用,尾递归调用是可以被进行优化的。

  尾调用指的是一个方法或者函数的调用在另一个方法或者函数的最后一条指令中进行。下面定义了一个foo()函数作为例子:

int foo(int a) {
a = a + 1;
return func(a);
}

  尾调用,不只是尾递归,函数调用本身都可以被优化掉,变得跟goto操作一样。这就意味着,在函数调用前先把栈给设置好,调用完成后再恢复栈的这个操作(分别是prolog和epilog)可以被优化掉。

  函数式语言的开发人员经常使用递归,所以大多数函数式语言的解释器都会进行尾调用的优化。但是在Java中使用深度的递归一定要非常的小心,否则很有可能会导致栈溢出的发生。

  

  下面是不合理使用递归的例子:

package test;

public class RecursiveTest {
/**
* 递归实现
*
* @param n
* @return
*/
public static double recursive(long n) {
if (n == 1) {
return Math.log(1);
} else {
return Math.log(n) + recursive(n - 1);
}
} /**
* 非递归实现
*
* @param n
* @return
*/
public static double directly(long n) {
double result = 0;
for (int i = 1; i <= n; i++) {
result += Math.log(i);
}
return result;
} public static void main(String[] args) {
int i = 5000000;
long test = System.nanoTime();
long start1 = System.nanoTime();
double r1 = recursive(i);
long end1 = System.nanoTime();
long start2 = System.nanoTime();
double r2 = directly(i);
long end2 = System.nanoTime(); System.out.println("recursive result:" + r1);
System.out.println("recursive time used:" + (end1 - start1));
System.out.println("non-recursive result:" + r2);
System.out.println("non-recursive time used:" + (end2 - start2));
}
}

  

  JVM中可能导致内存溢出的其他原因还包括: 

  • 引用变量过多使用了Static修饰 如public staitc Student s;在类中的属性中使用 static修饰的最好只用基本类型或字符串。如public static int i = 0; //public static String str;
  • 使用了大量的递归或无限递归(递归中用到了大量的建新的对象)
  • 使用了大量循环或死循环(循环中用到了大量的新建的对象)
  • 是否使用了向数据库查询所有记录的方法。即一次性全部查询的方法,如果数据量超过10万多条了,就可能会造成内存溢出。所以在查询时应采用“分页查询”。
  • 是否有数组,List,Map中存放的是对象的引用而不是对象,因为这些引用会让对应的对象不能被释放。会大量存储在内存中。
  • 是否使用了“非字面量字符串进行+”的操作。因为String类的内容是不可变的,每次运行"+"就会产生新的对象,如果过多会造成新String对象过多,从而导致JVM没有及时回收而出现内存溢出。

  如String s1 = "My name";

  String s2 = "is";

  String s3 = "xuwei";

  String str = s1 + s2 + s3 +.........;这是会容易造成内存溢出的