java中的迭代和递归详解的关系,java迭代和递归的区别,Java中的迭代和递归详解

java中的迭代和递归详解的关系,java迭代和递归的区别,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) {

返回1;

}否则{

返回n *阶乘(n-1);

}

}

在执行上述代码时,机器实际上要执行一系列乘法:阶乘(n) 阶乘(n-1) 阶乘(n-2) …阶乘(1)。所以要保持跟踪(跟踪上一次计算的结果),调用乘法来计算(构建乘法链)。这个类不断调用自己的运算形式,这叫做递归。递归可以进一步分为线性递归和数值递归。随着信息算法的输入而线性增加的递归称为线性递归。算n!阶乘是线性递归。随着n的增加,计算所需的时间线性增加。另一种随着输入的增加而呈指数增长的信息叫做树递归。

二、迭代

另一种计算n的方法!方式是:先算1乘以2,再把结果乘以3,再把得到的结果乘以4.一直到n .程序执行的时候,可以定义一个计数器。每次执行乘法运算时,计数器都会自行递增,直到计数器的值等于n。代码如下:

代码二

int factorial (int n) {

int product=1;

for(int I=2;在;i ) {

乘积*=I;

}

退回产品;

}

与码一相比,码二没有建立乘法链。在每一步计算中,你只需要知道当前的结果(乘积)和I的值,这种形式的计算叫做迭代。迭代有几个条件:1。有一个有初始值的变量。2.解释变量值如何更新的规则。3.结束条件。(流通三要素:流通变量、流通主体、流通终止条件)。与递归相同。随着输入的增加而呈线性所需的时间可称为线性迭代。

三、迭代 VS 递归

对比这两个程序,可以发现它们看起来几乎一样,尤其是在数学函数方面。数n!它们的计算步骤与n的值成正比,然而,如果我们从程序的角度考虑它们是如何工作的,那么这两种算法就大不相同了。

(注:原文的差别有点可笑,这里就不翻译了。下面是作者自己的总结。)

首先分析递归。其实递归最大的一点就是把一个复杂的算法分解成几个相同的可重复的步骤。因此,使用递归来实现一个计算逻辑通常只需要很短的代码,这样的代码很容易理解。然而,递归意味着大量的函数调用。函数调用的本地状态由堆栈记录。因此,这可能会浪费大量空间,如果递归太深,可能会导致堆栈溢出。

接下来,分析迭代。实际上,递归可以用迭代来代替。然而,与递归的简单性和可理解性相比,迭代显得相当生硬和难以理解。尤其是遇到复杂场景的时候。但是,代码很难理解,这带来了一些明显的问题。迭代的效率比递归高,空间消耗更小。

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

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

四、数形递归

如前所述,树递归随着输入的增加呈指数增长。典型的是斐波那契数列:

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

递归实现代码如下:

int fib (int n) {

if (n==0) {

返回0;

} else if (n==1) {

返回1;

}否则{

返回光纤(n-1)光纤(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 ) {

int temp=fib

fib=fib a;

a=温度;

}

返回光纤;

}

虽然递归会有多余的计算,但是可以用迭代来代替。但这并不意味着递归可以被完全取代。因为递归可读性更强。

总结

这就是本文的全部内容。希望这篇文章的内容对你学习或者使用Java有所帮助。有问题可以留言交流。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: