Recursion&IterationRecursion（递归）递归常用来描述事物以自相似的方式重复的过程。在数学和计算机科学中，它指的是在函数定义中使用函数。自己的方法。（A调用A）迭代（iteration）重复反馈过程的活动，每次迭代的结果将作为下一次迭代的初始值。（A重复调用B）如果题中有n步，那么一次只能走1或2步。一共有多少种方式？递归思路n=1->一步->f(1)=1n=2->(1)一步一步(2)直接走2步->f(2)=2n=3->(1)到达先第一步(f(1))，然后直接走两步(2)到达第二步(f(2))->f(3)=f(1)+f(2)n=4->(1)先到f(2)，然后直接走两步(2)先走到第二步f(3)，再直接走一步->f(4)=f(2)+f(3)···n=x(1)先到达f(x-2)，然后直接走两步(2)先到达第二步f(x-1)，然后直接走一步->f(x)=f(x-2)+f(x-1)循环迭代思路n=1->一步->f(1)=1n=2->(1)一步一步(2)直接走2步->f(2)=2n=3->(1)先到达第一步(f(1))，然后直接走两步(2)先到达第二步(f(2))->f(3)=f(1)+f(2)n=4->(1)先到达f(2)，然后直接跨过两步(2)先到达第二步f(3)，然后直接跨过一步->f(4)=f(2)+f(3)···n=x(1)先到达f(x-2)，然后直接走两步(2)到达第二步f(x-1),然后直接走一步->f(x)=f(x-2)+f(x-1)从上面可以看出，无论有多少步，都必须走到最后n-1或n-2步这两种情况，所以我们可以用两个临时变量one=(f(n)-1),two=(f(n)-2)来保存这两种情况！本题考点为递归循环迭代题解递归方法publicclassRecursion{publicstaticvoidmain(String[]args){longstart=System.currentTimeMillis();System.out.println(f(42));长端=System.currentTimeMillis();System.out.printf("耗时毫秒数：%d",end-start);}/***有n步，每次只有1或2步，一共多少次递归代码实现该方法*性能损耗比较严重，尤其是数据量大的时候，可能会造成栈overflow**@paramn要计算的值*@return计算结果*/publicstaticintf(intn){if(n==1||n==2){returnn;}返回f(n-2)+f(n-1);}}循环迭代publicclassLoopIteration{publicstaticvoidmain(String[]args){longstart=System.currentTimeMillis();System.out.println(loopIteration(42));长端=System.currentTimeMillis();System.out.printf("花费的时间以毫秒为单位:%d",end-start);}/***循环迭代求解有n步的问题，一次只能走1步或者2步。一共有多少种方式？**@paramn要计算的值（步数）*@return结果（走多少路）*/publicstaticintloopIteration(intn){if(n<1){thrownewIllegalArgumentException(n+"不能小于1");}如果(n==1||n==2){返回n;}//当n=3时，one=f(3-1)=f(2)=2,two=f(3-2)=f(1)=1intone=2;//初始化到达终点的方式inttwo=1;//初始化去最后需要走两步//总步数intsum=0;for(inti=3;i<=n;i++){总和=一+二;//当i=4时，此时二=f(4-2)=f(2)=2，所以是最后一个二=一；//当i=4时，one=f(4-1)=f(3)=3，所以是最后一个sumone=sum;}返回总和；}}总结比较上面两种方法的执行时间，可以看出递归是比较耗时的，所以能用迭代的地方不要用递归。就是把大问题简化成小问题，从小问题一步步推导出最后的结果。理论上，所有递归和迭代都可以相互转换。待研究）方法调用本身称为递归，利用变量的原值引入新值称为迭代递归。优点：把大问题变成小问题，可以减少代码量，同时代码精简，可读性强。缺点：递归调用浪费空间，递归太深容易造成栈溢出迭代优点：代码运行效率高，因为时间只是因为循环次数的增加而增加，没有额外的空间开销缺点:代码没有递归那么简洁，可读性不是很好（难懂）
