• 欢迎访问天天编码网站,Java技术、技术书单、开发工具,欢迎加入天天编码
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏天天编码吧
  • 我们的淘宝店铺已经开张了哦,传送门:https://shop145764801.taobao.com/

Java中的迭代与递归

Java基础 tiantian 2288次浏览 3个评论 扫描二维码

我们知道,任何简单或者复杂的程序流程都可以拆分为 顺序结构、选择结构和循环结构。其中顺序结构和条件结构相对比较简单,循环结构相对复杂,递归和迭代都是循环结构的实现方式。简单地说,递归是函数重复调用自身来实现循环;迭代是函数内某段代码实现循环。

递归

假设我们需要实现阶乘函数: 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);
}
}

在执行这个代码片段的过程中,JVM需要建立一条乘法操作的链条:factorial(n) -> factorial(n-1) -> factorial(n-2) -> … -> factorial(1)。应此,JVM中需要有相应的机制去保持这么多的链条元素,其中的每次调用都对应到JVM的栈空间的一个栈帧。这种实现方式,具有一条操作链条,就是标准的递归实现方式。按照递归的流程,递归可以进一步被分类为线性递归和树形递归。当递归过程中需要保持的信息是以线性方式增长的时候,这种递归情况就成为线性递归。我们此处求阶乘所实现的示例代码就是属于线性递归,因为递归过程中时间消耗的增长是线性的。另一个递归方式,树形递归,在递归的过程中需要保持的中间状态是分支形式增长的,本文将不会深入探讨这两种递归方式的异同,今后可能会有专文来讲解它们,欢迎收藏本站。

迭代

对于同样的计算N的阶乘问题,我们可以从一种全新的视觉来看分析。首先:1 * 2,然后:前一步的结果 * 3,再然后: 前一步的结果 * 4, … , 最后:前一步的结果 * n。这个过程翻译成为Java代码的话,可以使用一个计数器从1开始,每次增长1,直到到n为止,同时,累积每次的计算结果,知道超过n。翻译出来的示例代码如下所示:

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

我们把此示例代码与上面一个实例代码进行比较,可以发现此代码不需要建立一条乘法操作的链条。在每一步中,JVM只需要保持product和i的瞬时值,这种类型的实现方式就是迭代方式。这种方式的中间状态可以被固定数量的变量保持住,此处只使用了product和i两个变量。注意:无论是迭代方式还是递归方式,都需要特别注意循环的结束条件,或者造成死循环就悲剧了。此外,我们此处的迭代代码的时间消耗会随着输入值的增长而线性增长,也就称为线性迭代方式。

递归 VS 迭代

仔细比较上述的两个示例代码,可以发现它们具有非常多类似的地方,特别是其中的核心求值部分。为了求出最终的结果,它们都需要经历n个小步骤。另一方面,当我们仔细考虑两者的实际运行过程时,会发现它们之间的巨大差异。

对于迭代方式,使用代码中的少些变量就完全保持了循环过程中的状态。如果在迭代的过程中,中断迭代的运行后,再恢复此次迭代过程只需要提供正确的变量初始值即可。然后,如果在递归的过程中,一旦中断了递归的运行,基本就不可能恢复此次递归过程了。因为递归过程的很多中间状态变量被保存在此次递归的执行上下中,而不是代码本身,无法恢复。

树形递归

作为递归分类中比较复杂的情形,树形递归过程中需要保持的中间变量随着输入值的增长呈现树形增长。我们举个简单的例子来说明,数学中常见的 Fibonacci 公式:

Java中的迭代与递归

通过该公式定义,我们发现Fibonacci序列的规律是:每个序列值都是前两个值的和。Fibonacci序列的前几项数值如下:0,1,1,2,3,5,8,13,21,…

对照着Fabonacci公式的定义,我们可以翻译出对应的代码为:

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(3)和fib(4)的值,为了计算fib(4)的值,又必须先计算出fib(2)和fib(3)的值。仔细观察可以发现,在方法体中的最后一行,这个fib(int)函数会调用自身两次。此外,我们还发现了如下两个现象:

  1. Fibonacci序列的第i个值等于 phi(i)/rootsquare(5) 向下取值的整型值,这意味着Fibonacci值不是线程增长的。
  2. 这种计算Fibonacci序列的方式是低效的,因为此过程中有大量的重复计算。如果我们需要计算的Fibonacci值是序列中比较靠后的值,这个代码片段的耗时会非常长。我们可以在任何一本好的算法书中发现此示例代码的时间复杂度为O(phi(n))。

两个现象都表明,随着输入值的增长,这个示例代码的耗时增长是树形的。

当然,我们可以使用迭代的方式来重写上面求Fibonacci序列的示例代码。下面,我们给出一种线性迭代方式的示例代码。此代码与递归实现的代码片段在时间消耗上面的差异是非常巨大的,对于输入值不大的计算过程同样如何。

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

当然,你不能只因为本文给出的几个代码示例,就得出树形迭代无用的结论。当我们考虑在层级的数据结构上编写代码时,树形迭代就成为一个自然和强有力的工具。大家可以回想一下我们对 Tree 的各种先序、中序、后序遍历方式,多么清晰和自然,如果改成使用迭代方式,复杂度的提升是巨大的。通过比较Fibonacci实现方式中的递归代码和迭代代码,我们可以说,递归方式更符合人的直接思维,但却缺乏效率。所以,我们通常使用迭代的方式来求Fibonacci序列。


天天编码 , 版权所有丨本文标题:Java中的迭代与递归
转载请保留页面地址:http://www.tiantianbianma.com/java-iteration-recursion.html/
喜欢 (8)
支付宝[多谢打赏]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(3)个小伙伴在吐槽
  1. int fib(int n) { int fib = 0; int a = 1; for (int i = 0; i < n; i++) { fib = fib + a; a = fib; } }这个迭代有问题
    匿名2017-10-11 18:13 回复 Windows 7 | Chrome 61.0.3141.7
    • public static int fib(int n) { int fib = 0; int a = 1; int c = 0; for (int i = 0; i < n; i++) { c=fib; fib = fib + a; a = c; } return fib; }要加一个中间量c才可以
      匿名2017-10-11 18:17 回复 Windows 7 | Chrome 61.0.3141.7
  2. fib的迭代有问题
    匿名2017-10-14 22:43 回复 Windows 7 | Chrome 53.0.2785.104