循环？还是递归？
前言
前几天群里有几个小伙伴，展开了如下讨论：
--------------------------------------------------------------------------
【西安-Java-小白】
谁遇上过？
【杭州-Java-JOEL】
你要打断点看哪行出错了
【西安-Java-小白】
栈溢出，mybatis执行查询的时候，循环查询，1000条查询一次，到160多次的时候栈溢出
【北京-Android-背影】
你有递归么
【西安-Java-小白】
嗯。刚把递归干掉了，换成循环试试。
【北京-Android-背影】
@西安-Java-小白 你去掉递归还会报错么
一般栈溢出都是有递归调用方法体导致的
【西安-Java-小白】
嗯
去掉了，在测试
换成while了
【北京-Android-背影】
嗯嗯，等会给我们说下结果
【西安-Java-小白】
感觉速度比递归快太多了
【杭州-Java-JOEL】
查询的时候批量去查稍微好点
【北京-Android-背影】
递归方法体内的变量会一直保存，但是有的变量没任何意义。
循环的话，方法体内的变量会被回收掉，不会一直占内存。
【杭州-Java-JOEL】
这个解释赞
【西安-Java-小白】
嗯呢
改成循环就OK了
【西安-Java-xcbeyond】
栈，主要是用来存放栈帧的，每执行一个方法就会出现压栈操作，所以采用递归的时候产生的栈帧比较多，递归就会影响到内存，非常消耗内存。而使用循环就执行了一个方法，压入
栈帧一次，只存在一个栈帧，所以比较节省内存。
--------------------------------------------------------------------------
都是递归惹的祸！接下来，我们就一起讨论下递归和循环吧，该如何用，他们都有哪些区别呢？时间复杂度，空间复杂度又是多少呢
循环、递归验证
循环：当满足某一条件时，进行反复执行某一操作(循环体)。如：for、while循环
递归：在一个方法内调用方法本身，并且要有递归结束的判断。
循环和递归两者之间是可以相互替换实现的，但他们之间却有很大的差异，其时间复杂度，空间复杂度有着很大的差异的。
接下来，我们就直接撸起代码见效果吧，以一个整数递减到0输出为例。
package com.xcbeyond.test;
/**
* 递归测试
* @Auther: xcbeyond
* @Date: 2019/9/12 11:26
*/
public class RecursionTest {
public static void main(String [] args) {
int number = 5000;
long startTime = System.currentTimeMillis();
loop(number);
long endTime = System.currentTimeMillis();
System.out.println();
System.out.println("循环耗时：" + (endTime-startTime));
long startTime2 = System.currentTimeMillis();
recursion(number);
long endTime2 = System.currentTimeMillis();
System.out.println();
System.out.println("递归耗时：" + (endTime2-startTime2));
}
/**
* 递归
* @param n
* @return
*/
public static void recursion(int n) {
if(n <= 0) {
return;
}else {
System.out.print(n + " ");
recursion(n - 1);
}
}
/**
* 循环
* @param n
* @return
*/
public static void loop(int n) {
for(int i = n; i> 0;i--) {
System.out.print(i + " ");
}
}
}结果分析：
number分别为1000、5000、10000，其耗时结果如下:
情况1：1000
循环耗时：34
递归耗时：18情况2：5000
循环耗时：48
递归耗时：11情况3：10000
循环耗时：142
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:691)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:579)
at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:271)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:125)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:207)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:129)
at java.io.PrintStream.write(PrintStream.java:526)
at java.io.PrintStream.print(PrintStream.java:669)
at com.xcbeyond.test.RecursionTest.recursion(RecursionTest.java:36)从上述结果来看，使用循环算法比递归算法更耗时，但当循环、递归次数达到一定数据级时，递归算法就会出现栈溢出(StackOverflowError)问题了，这也就是文章开头说的现象了。
针对栈溢出问题，我们可以进一步来跟踪如下：
(上述代码略做修改，为了便于观察，number设置为5)
package com.xcbeyond.test;
/**
* 递归测试
* @Auther: xcbeyond
* @Date: 2019/9/12 11:26
*/
public class RecursionTest {
public static void main(String [] args) {
int number = 3;
long startTime = System.currentTimeMillis();
loop(number);
long endTime = System.currentTimeMillis();
System.out.println();
System.out.println("循环耗时：" + (endTime-startTime));
// long startTime2 = System.currentTimeMillis();
// recursion(number);
// long endTime2 = System.currentTimeMillis();
// System.out.println();
// System.out.println("递归耗时：" + (endTime2-startTime2));
}
/**
* 递归
* @param n
* @return
*/
public static void recursion(int n) {
Thread.currentThread().dumpStack();
if(n <= 0) {
return;
}else {
System.out.print(n + " ");
recursion(n - 1);
}
}
/**
* 循环
* @param n
* @return
*/
public static void loop(int n) {
for(int i = n; i> 0;i--) {
System.out.print(i + " ");
Thread.currentThread().dumpStack();
}
}
}循环的栈分配情况：
递归的栈分配情况：
通过分析栈的出栈入栈过程，循环只会堆栈一次，而递归却随着递归数次累积堆栈，即：随着递归次数增多，将会出现栈溢出的问题。
循环、递归区别
循环
优点：结构简单
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环，如果使用循环并不困难的话，最好使用循环。
递归
优点：代码简洁、清晰，并且容易验证正确性
缺点：它的运行需要较多次数的方法调用，如果调用层数比较深，需要增加额外的堆栈处理，比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。
一般递归调用可以处理的算法，也通过循环去解决常需要额外的低效处理 。现在的编译器在优化后，对于多次调用的方法处理会有非常好的效率优化，效率未必低于循环。
总结
每次的递归，就是方法的每次调用，即：进行多次压栈操作。所以，如果使用递归算法，则不能递归次数不能过大，复杂将会出现栈溢出。
栈，主要是用来存放栈帧的，每执行一个方法就会出现压栈操作，所以采用递归的时候产生的栈帧比较多，递归就会影响到内存，非常消耗内存。而使用循环就执行了一个方法，压入栈帧一次，只存在一个栈帧，所以比较节省内存。
总之，在循环、递归算法的选取上，可遵循如下原则：
- 循环次数不是特别大，处理逻辑及其复杂，如果用循环算法，可能难于理解时，可优先采用递归算法。
- 处理逻辑简单，则用循环。
记住一点，无论使用循环，还是递归，尽量避免出现循环次数特别大的场景处理，尽量去规避它吧。
腾讯云开发者
