递归 & 迭代
递归(recursion)
递归常被用来形容以自类似办法反复事物的过程,在数学和计算机科学中,指的是在函数定义中应用函数本身的办法。(A 调用 A)
迭代(iteration)
反复反馈过程的流动,每一次迭代的后果会作为下一次迭代的初始值。(A 反复调用 B)
如题
有 n 步台阶,一次只能上 1 步或 2 步,共有多少种走法?
递归思路
- n=1 -> 一步 ->f(1)=1
- n=2 ->(1)一步一步走(2)间接走 2 步 ->f(2)=2
-
n=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)=1
- n=2 ->(1)一步一步走(2)间接走 2 步 ->f(2)=2
-
n=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)保留这两个状况!
本题考点
- 递归
-
循环迭代
题解
递归形式
public class Recursion {public static void main(String[] args) {long start = System.currentTimeMillis(); System.out.println(f(42)); long end = System.currentTimeMillis(); System.out.printf("耗时毫秒为:%d", end - start); } /** * 有 n 步台阶,一次只能上 1 步或 2 步,共有多少种走法的递归代码实现 * 性能损耗比较严重,特地是数据量大的时候,还会有可能造成栈溢出 * * @param n 待计算的值 * @return 计算结果 */ public static int f(int n) {if (n == 1 || n == 2) {return n;} return f(n - 2) + f(n - 1); } }
循环迭代
public class LoopIteration {public static void main(String[] args) {long start = System.currentTimeMillis();
System.out.println(loopIteration(42));
long end = System.currentTimeMillis();
System.out.printf("耗时毫秒为:%d", end - start);
}
/**
* 循环迭代解决 有 n 步台阶,一次只能上 1 步或 2 步,共有多少种走法问题
*
* @param n 待计算的值(台阶数)* @return 后果(多少种走法)*/
public static int loopIteration(int n) {if (n < 1) {throw new IllegalArgumentException(n + "不能小于 1");
}
if (n == 1 || n == 2) {return n;}
// 当 n =3,one=f(3-1)=f(2)=2,two=f(3-2)=f(1)=1
int one = 2; // 初始化走到最初须要走一步的走法
int two = 1; // 初始化走到最初须要走两步的走法
// 总步数
int sum = 0;
for (int i = 3; i <= n; i++) {
sum = one + two;
// 当 i = 4 时,此时 two=f(4-2)=f(2)=2,所以就是上一次的 one
two = one;
// 当 i = 4 时,one=f(4-1)=f(3)=3,所以就是上一次的 sum
one = sum;
}
return sum;
}
}
小结
- 比照以上两种形式的执行工夫,能看出递归多耗时间了吧,所以能用迭代的中央千万不要应用递归
- 两种形式都是把大问题简化为小问题,从小问题一步一步推导出最终后果
- 实践上所有的递归和迭代能够互相转换,但理论从算法构造来说,递归申明的构造并不总能转换为迭代构造(起因有待钻研)
- 办法调用本身称为递归,利用变量的原值推出新值称为迭代
-
递归
- 长处:大问题转化为小问题,能够缩小代码量,同时代码精简,可读性好
- 毛病:递归调用节约了空间,而且递归太深容易造成堆栈溢出
-
迭代
- 长处:代码运行效率好,因为工夫只因循环次数减少而减少,而且没有额定的空间开销
- 毛病:代码不如递归简洁,可读性不太好(不易了解)