首页 Java java教程 Java中的迭代和递归实例详解

Java中的迭代和递归实例详解

Jul 02, 2017 am 10:23 AM
java 实例 递归

这篇文章主要给大家介绍了关于Java中的迭代和递归文章显示分别介绍了Java中的迭代和递归,而后又介绍了迭代和递归的区别以及数形递归的相关内容,文中介绍的很详细,相信会对大家学习具有一定的参考借鉴价值,有需要的朋友们可以参考借鉴。

前言

最近在看书的时候看到这一内容,感觉还是蛮有收获的。迭代使用的是循环(for,while,do...wile)或者迭代器,当循环条件不满足时退出。而递归,一般是函数递归,可以是自身调用自身,也可以是非直接调用,即方法A调用方法B,而方法B反过来调用方法A,递归退出的条件为if,else语句,当条件符合基的时候退出。

上面是迭代和递归的语法特性,他们在Java中有什么不同呢?下面通过这篇文章来详细了解了解。

一、递归

提到迭代,不得不提一个数学表达式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;
}
登录后复制

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

以上是Java中的迭代和递归实例详解的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Java 中的平方根 Java 中的平方根 Aug 30, 2024 pm 04:26 PM

Java 中的平方根指南。下面我们分别通过例子和代码实现来讨论平方根在Java中的工作原理。

Java 中的完美数 Java 中的完美数 Aug 30, 2024 pm 04:28 PM

Java 完美数指南。这里我们讨论定义,如何在 Java 中检查完美数?,示例和代码实现。

Java 中的随机数生成器 Java 中的随机数生成器 Aug 30, 2024 pm 04:27 PM

Java 随机数生成器指南。在这里,我们通过示例讨论 Java 中的函数,并通过示例讨论两个不同的生成器。

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java 版 Weka 指南。这里我们通过示例讨论简介、如何使用weka java、平台类型和优点。

Java 中的阿姆斯特朗数 Java 中的阿姆斯特朗数 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯特朗数指南。这里我们讨论一下java中阿姆斯特朗数的介绍以及一些代码。

Java 中的史密斯数 Java 中的史密斯数 Aug 30, 2024 pm 04:28 PM

Java 史密斯数指南。这里我们讨论定义,如何在Java中检查史密斯号?带有代码实现的示例。

Java Spring 面试题 Java Spring 面试题 Aug 30, 2024 pm 04:29 PM

在本文中,我们保留了最常被问到的 Java Spring 面试问题及其详细答案。这样你就可以顺利通过面试。

突破或从Java 8流返回? 突破或从Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处

See all articles