递归(recurse)与迭代(iteration) | 您所在的位置:网站首页 › 递归与迭代的区别图解 › 递归(recurse)与迭代(iteration) |
1.概念
递归概念
递归,在数学与计算机科学中,是指在方法的定义中使用方法自身。也就是说,递归算法是一种直接或者间接调用自身方法的算法。简言之:在定义自身的同时又出现自身的直接或间接调用。 注意:递归必须要有一个退出的条件! 递归算法解决问题的特点: 1)递归就是方法里调用自身。 2)在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。 3)递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等,所以一般不提倡用递归算法设计程序。 在做递归算法的时候,一定要把握住出口,也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的,就是一个条件,当满足了这个条件的时候我们就不再递归了。 迭代概念迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。 迭代和递归的关系和区别从概念上讲,递归就是指程序调用自身的编程思想,即一个函数调用本身;迭代是利用已知的变量值,根据递推公式不断演进得到变量新值得编程思想。简单地说,递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环。 在循环的次数较大的时候,迭代的效率明显高于递归。 2.实际问题 求n的阶乘图解理解 public class Demo6 { public static void main(String[] args) { System.out.println(fact(5)); } /** * 求n的阶乘f1(n) 求n的阶乘--->fact(n-1)求n-1的阶乘 * 1.找重复(规模更小);n*(n-1)的阶乘,求n-1的阶乘是原问题的重复(规模更小)——子问题 * 2.找变化;变化的量应作为参数 * 3.找边界;出口 */ public static int fact(int n) { if(n == 1) { return n = 1; }else { return n*fact(n-1); } } } 斐波那契数列 递归实现 int fib(int n){ if(n>1) return fib(n-1) + fib(n-2); else return n; // n = 0, 1时给出recursion终止条件 } 迭代实现 int fib(int n){ int i, temp0, temp1, temp2; if(n public static void main(String[] args) { double digui = digui(5, 1, 1, 1); // double digui = digui1(5, 1, 1, 1); System.out.println(digui); } public static double digui(int level,double r1,double r2, double r3){ if (level == 1){ return r1 + r2 + r3; } else { double sum = r1 + r2 + (r3 * digui(level-1,r1,r2,r3)) / (r3 + digui(level-1,r1,r2,r3)); return sum; } }; public static double digui1(int level,double r1,double r2, double r3){ if (level == 1){ return r1 + r2 + r3; } else { return r1 + r2 + (r3 * digui1(--level,r1,r2,r3)) / (r3 + digui1(--level,r1,r2,r3)); } }; }当运行digui1方法的时候就会报出StackOverflowError错误。而修改后的digui方法就可以正常运行。在运行digui1方法的debugger的过程中发现,level1的时候递归并没有停止,而是继续往下走了,下一个就是level0。 4.解决方法当把–level改为level-1的时候就能够运行成功,在分析一波了。找到了原因所在。 用–level永远的修改了level的值,所以它会走到1还停不下来 |
CopyRight 2018-2019 实验室设备网 版权所有 |