文档章节

深入理解Java中的迭代与递归

郑加威
 郑加威
发布于 2017/03/17 09:49
字数 1361
阅读 21
收藏 0

递归

提到迭代,不得不提一个数学表达式: n!=n*(n-1)*(n-2)*...*1

有很多方法来计算阶乘。有一定数学基础的人都知道n!=n*(n-1)!因此,代码的实现可以直接写成:

代码一

int factorial (int n) {
    if (n == 1) {
        return 1;
    } else {
        return n*factorial(n-1);
    }
}   

在执行以上代码的时候,其实机器是要执行一系列乘法的: factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1)。所以,需要不断的跟踪(跟踪上次计算的结果)并调用乘法进行计算(构建一个乘法链)。这类不断调用自身的运算形式称之为递归。递归可以进一步的分为线性递归和数形递归。信息量随着算法的输入呈线性增长的递归称之为线性递归。计算n!(阶乘)就是线性递归。因为随着N的增大,计算所需的时间呈线性增长。另外一种信息量随着输入的增长而进行指数增长的称之为树形递归。

迭代

另外一种计算n!的方式是:先计算1乘以2,然后用其结果乘以3,再用的到的结果乘以4….一直乘到N。在程序实现时,可以定义一个计数器,每进行一次乘法,计数器都自增一次,直到计数器的值等于N截至。代码如下:

代码二

int factorial (int n) {
    int product = 1;
    for(int i=2; i<n; i++) {
        product *= i;
    }
    return product;
}

和代码一相比,代码二没有构建一个乘法链。在进行每一步计算时,只需要知道当前结果(product)和i的值就可以了。这种计算形式称之为迭代。迭代有这样几个条件:1、有一个有初始值的变量。2、一个说明变量值如何更新的规则。3、一个结束条件。(循环三要素:循环变量、循环体和循环终止条件)。和递归一样。时间要求随着输入的增长呈线性的可以叫做线性迭代。

迭代 VS 递归

比较了两个程序,我们可以发现,他们看起来几乎相同,特别是其数学函数方面。在计算n!的时候,他们的计算步数都是和n的值成正比的。但是,如果我们站在程序的角度,考虑他们是如何运行的话,那么这两个算法就有很大不同了。

(注:原文中关于其区别写的有点扯,这里就不翻译了,下面是笔者自己总结内容。)

首先分析递归,其实递归最大的有点就是把一个复杂的算法分解成若干相同的可重复的步骤。所以,使用递归实现一个计算逻辑往往只需要很短的代码就能解决,并且这样的代码也比较容易理解。但是,递归就意味着大量的函数调用。函数调用的局部状态之所以用栈来记录的。所以,这样就可能浪费大量的空间,如果递归太深的话还有可能导致堆栈溢出。

接下来分析迭代。其实,递归都可以用迭代来代替。但是相对于递归的简单易懂,迭代就比较生硬难懂了。尤其是遇到一个比较复杂的场景的时候。但是,代码的难以理解带来的有点也比较明显。迭代的效率比递归要高,并且在空间消耗上也比较小。

递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。

能用迭代的不要用递归,递归调用函数不仅浪费空间,如果递归太深的话还容易造成堆栈的溢出。

数形递归

前面介绍过,树递归随输入的增长的信息量呈指数级增长。比较典型的就是斐波那契数列:

用文字描述就是斐波那契数列中前两个数字的和等于第三个数字:0,1,1,2,3,5,8,13,21……

递归实现代码如下:

int fib (int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

计算过程中,为了计算fib(5),程序要先计算fib(4)fib(3),要想计算fib(4) ,程序同样需要先计算 fib(3)fib(2)。在这个过程中计算了两次fib(3)

从上面分析的计算过程可以得出一个结论:使用递归实现斐波那契数列存在冗余计算。

就像上面提到的,可以用递归的算法一般都能用迭代实现,斐波那契数列的计算也一样。

int fib (int n) {
    int fib = 0;
    int a = 1;
    for(int i=0; i<n; i++) {
       int temp = fib;
        fib = fib + a;
        a = temp;
    }
    return fib;
}

虽然使用递归的方式会有冗余计算,可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。

© 著作权归作者所有

郑加威
粉丝 175
博文 183
码字总数 387300
作品 0
杭州
架构师
私信 提问
JVM 深入笔记(2)内存溢出场景模拟

JVM 深入笔记(2)各内存区溢出场景模拟 作者:柳大 · Poechant 电邮:zhongchao.ustc#gmail.com (#->@) 博客:blog.csdn.net/poechant 日期:Feb. 23st 2012 《JVM 深入笔记(1)内存区域是...

晨曦之光
2012/04/24
153
0
【JVM】浅谈双亲委派和破坏双亲委派

一、前言 笔者曾经阅读过周志明的《深入理解Java虚拟机》这本书,阅读完后自以为对jvm有了一定的了解,然而当真正碰到问题的时候,才发现自己读的有多粗糙,也体会到只有实践才能加深理解,正...

joemsu
2018/07/14
0
0
面试中关于Java虚拟机(jvm)的问题看这篇就够了

最近看书的过程中整理了一些面试题,面试题以及答案都在我的文章中有所提到,希望你能在以问题为导向的过程中掌握虚拟机的核心知识。面试毕竟是面试,核心知识我们还是要掌握的,加油~~~ 下面...

snailclimb
2018/05/12
0
0
JScript.net的运行效率测试(兼多种语言效率对比)

昨天的文章《用JScript.net写.net应用程序》一文写了之后,对于其运行效率问题有了一点疑问,所以需要进行以下测试,前人当然做过很多种测试,不过bigtall的测试方法有些不同。这里我采用了斐...

长平狐
2012/10/23
473
0
如何理解并掌握 Java 数据结构

一说起“数据结构”可能很多同学都又交给老师了。但是实际工作中如果做得深入一些,特别是越往上发展,越大公司越离不开数据结构。本场 Chat 作者将带领大家重温《Java 数据结构》,讲解的内...

valada
2018/04/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql-connector-java升级到8.0后保存时间到数据库出现了时差

在一个新项目中用到了新版的mysql jdbc 驱动 <dependency>     <groupId>mysql</groupId>     <artifactId>mysql-connector-java</artifactId>     <version>8.0.18</version> ......

ValSong
今天
5
0
Spring Boot 如何部署到 Linux 中的服务

打包完成后的 Spring Boot 程序如何部署到 Linux 上的服务? 你可以参考官方的有关部署 Spring Boot 为 Linux 服务的文档。 文档链接如下: https://docs.ossez.com/spring-boot-docs/docs/r...

honeymoose
今天
6
0
Spring Boot 2 实战:使用 Spring Boot Admin 监控你的应用

1. 前言 生产上对 Web 应用 的监控是十分必要的。我们可以近乎实时来对应用的健康、性能等其他指标进行监控来及时应对一些突发情况。避免一些故障的发生。对于 Spring Boot 应用来说我们可以...

码农小胖哥
今天
6
0
ZetCode 教程翻译计划正式启动 | ApacheCN

原文:ZetCode 协议:CC BY-NC-SA 4.0 欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 学习资源 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 ...

ApacheCN_飞龙
今天
4
0
CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部