前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >循环?还是递归?

循环?还是递归?

作者头像
xcbeyond
发布2020-03-25 14:16:46
1.2K0
发布2020-03-25 14:16:46
举报
文章被收录于专栏:技术那些事

前言

前几天群里有几个小伙伴,展开了如下讨论:

--------------------------------------------------------------------------

【西安-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输出为例。

代码语言:javascript
复制
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

代码语言:javascript
复制
循环耗时:34
递归耗时:18

情况2:5000

代码语言:javascript
复制
循环耗时:48
递归耗时:11

情况3:10000

代码语言:javascript
复制
循环耗时: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)

代码语言:javascript
复制
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();
        }
    }
}

循环的栈分配情况:

递归的栈分配情况:

通过分析栈的出栈入栈过程,循环只会堆栈一次,而递归却随着递归数次累积堆栈,即:随着递归次数增多,将会出现栈溢出的问题。

循环、递归区别

循环

优点:结构简单

缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环,如果使用循环并不困难的话,最好使用循环。

递归

优点:代码简洁、清晰,并且容易验证正确性

缺点:它的运行需要较多次数的方法调用,如果调用层数比较深,需要增加额外的堆栈处理,比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。

一般递归调用可以处理的算法,也通过循环去解决常需要额外的低效处理 。现在的编译器在优化后,对于多次调用的方法处理会有非常好的效率优化,效率未必低于循环。

总结

每次的递归,就是方法的每次调用,即:进行多次压栈操作。所以,如果使用递归算法,则不能递归次数不能过大,复杂将会出现栈溢出。

栈,主要是用来存放栈帧的,每执行一个方法就会出现压栈操作,所以采用递归的时候产生的栈帧比较多,递归就会影响到内存,非常消耗内存。而使用循环就执行了一个方法,压入栈帧一次,只存在一个栈帧,所以比较节省内存。

总之,在循环、递归算法的选取上,可遵循如下原则:

  • 循环次数不是特别大,处理逻辑及其复杂,如果用循环算法,可能难于理解时,可优先采用递归算法。
  • 处理逻辑简单,则用循环。

记住一点,无论使用循环,还是递归,尽量避免出现循环次数特别大的场景处理,尽量去规避它吧。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-09-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序猿技术大咖 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档