新余企业网站建设,济南城乡住房建设厅网站,有域名了网站怎么建设,网站开发与spark递归
提到迭代#xff0c;不得不提一个数学表达式#xff1a; n!n*(n-1)*(n-2)*...*1
有很多方法来计算阶乘。有一定数学基础的人都知道n!n*(n-1)!因此#xff0c;代码的实现可以直接写成#xff1a;
代码一
int factorial (int n) {
if (n 1) {
return 1;
} else …递归
提到迭代不得不提一个数学表达式 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 i2; in; 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 i0; in; i) {
int temp fib;
fib fib a;
a temp;
}
return fib;
}
虽然使用递归的方式会有冗余计算可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。 为了让学习变得轻松、高效今天给大家免费分享一套Java教学资源。帮助大家在成为Java架构师的道路上披荆斩棘。需要资料的欢迎加入学习交流群928505736
