关于递归和迭代[通俗易懂]
2023-06-13 09:12:00 时间
大家好，又见面了，我是你们的朋友全栈君。
首先明确递归和迭代的概念。
递归：程序调用自身的编程技巧（将大问题化解为相同结构的小问题，从待解问题一直分解到已知答案的最小问题，在逐级返回得 到原解）
使用递归的两个阶段：
1)递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;
2)回归:当获得最简单的情况后,逐步返回,依次得到复杂的解.
迭代：从已知式出发，通过递推式，不断更新变量到解决问题。
从思想上来说，迭代是人，递归是神！迭代是人，递归是神
从实现上来说，能用迭代就不用递归（递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出）
下面以剑指offer题为例，给出几个个人感觉实现比较好的迭代。
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：（递归方式分析得思路 —>迭代方式写代码）
public class Solution {
public int JumpFloorII(int target) {
//递归的思想快速分析问题得到思路
if (target <= 0) {
return -1;
} else if (target == 1) {
return 1;
} else {
return 2 * JumpFloorII(target - 1);
}
}
}f(N) = f(N-1)+ f(N-2)+ f(N-3)+……. +f(1)+1 （1）
= 2^(n-1) （2）
代码1：
public class Solution {
public int JumpFloorII(int target) {
if(target == 0) {
return 0;
}
//该方法通过数组的形式完成1式的累加，并将每一项都保存起来。
int[] dp = new int[target + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i <= target;i++) {
dp[i] = 0;
for(int j = 0;j < i;j++) {
dp[i] += dp[j];
}
}
return dp[target];
}
}代码2 ：
public class Solution {
public int JumpFloorII(int target) {
//该方法实现2式的累乘
int t =1;
if(target == 0){
return 0;
}else if(target ==1){
return 1;
}else {
for(;target-1>0;target--)
t = 2*t;
}
return t;
}
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/134927.html原文链接：https://javaforall.cn