To Iterate is Human,to Recures,Divine
人理解迭代，神理解递归
阶梯问题 递归方法空间复杂度：O(1)
时间复杂度：O(2^n)
分析：
- 空间复杂度：因为递归没有申请额外空间，所以为O(1)
- 时间复杂度：递归的次数以一个二叉树的形式增加，容易知道代码的时间复杂度和二叉树的节点个数有关，得到O(2^n)
空间复杂度：O(1)
时间复杂度：O(n)
分析：
- 空间复杂度：因为递归没有申请额外空间，所以为O(1)
- 时间复杂度：只有一个for循环即可得到结果，所以为O(n)
public class Ladder {
//递归方法
public static int Recursion(int n){
//终止条件
if(n==1||n==2){
return n;
}
//非终止条件：返回前一步和前两步的方法
return Recursion(n-1)+Recursion(n-2);
}
//递推方法
public static int Recurrence(int n){
if(n==1)return 1;
if(n==2)return 2;
int Part1 = 1;
int Part2 = 2;
int temp;//创建临时变量
int sum = 0;//创建接收结果变量为0
for (int i = 3; i <= n; i++) {//tip:从3开始
sum = Part1+Part2;//sum需要等于前两个
temp = Part2;
Part2 = sum;
Part1 = temp;
}
return sum;
}
public static void main(String[] args) {
System.out.println(Recurrence(4));//递推
System.out.println(Recursion(4));//递归
}
}
阶乘算法
递归方法
空间复杂度：O(1)
时间复杂度：O(n)
分析：
- 空间复杂度：因为递归没有申请额外空间，所以得O(1)
- 时间复杂度：递归的次数与n有关，时间与n成正比，所以得O(n)
空间复杂度：O(1)
时间复杂度：O(n)
分析：
-
空间复杂度：因为没有开辟多的空间，所以得O(1)
-
时间复杂度：递推很容易看出，代码执行的次数与n有关，可以得到O(n)
public class Factorial {
//递归方法
public static int Recursion(int n) {
//终止条件
if (n == 1) return 1;
//非终止条件 返回上一个数的乘阶*n
return Recursion(n - 1) * n;
}
//递推方法
public static int Recurrence(int n) {
int sum = 1;//设sum等于1
for (int i = 1; i <= n; i++) {
sum *= i;//每次乘以n
}
return sum;//最后返回sum
}
public static void main(String[] args) {
System.out.println(Recurrence(10));//递推
System.out.println(Recursion(10));//递归
}
}
斐波拉契数列
递归方法
空间复杂度：O(1)
时间复杂度：O(2^n)
分析：
- 空间复杂度：因为递归没有申请额外空间，所以为O(1)
- 时间复杂度：递归的次数以一个二叉树的形式增加，容易知道代码的时间复杂度和二叉树的节点个数有关，得到O(2^n)
空间复杂度：O(1)
时间复杂度：O(n)
分析：
- 空间复杂度：因为递推没有申请额外空间，所以为O(1)
- 时间复杂度：只有一个for循环即可得到结果，所以为O(n)
public class Fibonacci {
//递归方法
public static int Recursion(int n){
//终止条件
if(n==1||n==2){
return n;
}
//非终止条件：返回前一步和前两步的方法
return Recursion(n-1)+Recursion(n-2);
}
//递推方法
public static int Recurrence(int n){
if(n==1)return 1;
if(n==2)return 2;
int Part1 = 1;
int Part2 = 2;
int temp;//创建临时变量
int sum = 0;//创建接收结果变量为0
for (int i = 3; i <= n; i++) {//tip:从3开始
sum = Part1+Part2;//sum需要等于前两个
temp = Part2;
Part2 = sum;
Part1 = temp;
}
return sum;
}
public static void main(String[] args) {
System.out.println(Recurrence(4));//递推
System.out.println(Recursion(4));//递归
}
}
回文字符串
递归方法
空间复杂度：O(1)
时间复杂度：O(2^n)
分析：
- 空间复杂度：因为递归没有申请额外空间，所以为O(1)
- 时间复杂度：递归的次数以一个二叉树的形式增加，容易知道代码的时间复杂度和二叉树的节点个数有关，得到O(2^n)
空间复杂度：O(1)
时间复杂度：O(n)
分析：
- 空间复杂度：因为递推没有申请额外空间，所以为O(1)
- 时间复杂度：只有一个while循环即可得到时间T(n)=n/2，所以得O(n)
public class Palindrome {
//递推的方法
public static boolean IsPalindereme01(String s) {
//运用指针的方法
int begin = 0;//指向第一个下标
int end = s.length() - 1;//指向最后一个下标
while (begin < end) {
if (s.charAt(begin) != s.charAt(end))
return false;//若出现有不相等的情况返回false
begin++;//指针加一
end--;//指针减一
}
//循环结束表示正确，返回true
return true;
}
//递归的方法
public static boolean IsPalindereme02(String s,int left,int right) {
//终止条件
if (right-left <= 1)//当右指针指向左指针右边或者相等时结束，可以用right<=left+1代替
return true;
if (s.charAt(left) != s.charAt(right))//charAt(a)函数取字符串下标为a的字符
return false;//当出现不相等时返回false
//非终止条件
else
return IsPalindereme02(s,left+1,right-1);//继续循环
}
//测试结果
public static void main(String[] args) {
String s = "asdfghjklkjhgfdsa";
System.out.println(IsPalindereme01(s));
System.out.println(IsPalindereme02(s,0,s.length()-1));
s = "123";
System.out.println(IsPalindereme01(s));
System.out.println(IsPalindereme02(s,0,s.length()-1));
}
}
汉诺塔
递归方法
空间复杂度：O(1)
时间复杂度：O(2^n)
分析：
-
空间复杂度：因为递归没有申请额外空间，所以为O(1)
-
时间复杂度：
-
T(n)=2(n-1)*2T(1)+1*(1+2+22+……+2^(n-1))
=2n+2n-1
=2^(n+1)-1
-
求通项算得到递归的算法时间复杂度为O(2^n)
-
若使用递推直接使用公式：H(n) = 2^n - 1
案例代码：hannoiDemo.javaimport java.util.Scanner;
public class hannoiDemo {
static int times;
//递归函数
public static void hannoi(int n, char A, char B, char C) {
if (n == 1) {
move(n, A, C);
} else {
//移动上一关的步骤移动到B
hannoi(n - 1, A, C, B);
//把最大的盘子移动C塔
move(n, A, C);
//再把B上的上一关的盘子移动到C上就可以了
hannoi(n - 1, B, A, C);
}
}
//求通项算得到递归的算法时间复杂度为O(2^n);
//打印移动
public static void move(int disk, char M, char N) {
System.out.println("第" + (++times) + "次移动, 盘子" + disk + " " + M + "------->" + N);
}
public static void main(String[] args) {
char A = 'A';
char B = 'B';
char C = 'C';
System.out.println("汉诺塔游戏开始啦");
System.out.println("请输入盘子数：");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
//调用汉诺塔
hannoi(n, A, B, C);
s.close();
}
}
加法分解
递归方法
空间复杂度：O(1)
时间复杂度：O(2^n)
分析：
- 空间复杂度：因为递归没有申请额外空间，所以为O(1)
- 时间复杂度：递归的次数以一个二叉树的形式增加，容易知道代码的时间复杂度和二叉树的节点个数有关，得到O(2^n)
#includeusing namespace std; int sum = 0; void dfs1(int n, int count, int* p) { if (n == 0) { //递归基，到叶子结点时输出结果 cout << sum << "="; for (int i = 0; i < count; i++) if (i == count - 1) cout << p[i] << endl; else cout << p[i] << "+"; return; } for (int i = 1; i <= n; i++) { p[count] = i; dfs1(n - i, count + 1, p); } return; } void dfs2(int n, int count, int* p) { if (n == 0) { //递归基，到叶子结点时输出结果 cout << sum << "="; for (int i = 0; i < count; i++) if (i == count - 1) cout << p[i] << endl; else cout << p[i] << "+"; return; } int k = count > 0 ? p[count - 1] : 1; //数组中的数应该非递减的顺序 for (int i = k; i <= n; i++) { p[count] = i; dfs2(n - i, count + 1, p); } } int main() { int n, m; cin >> n >> m; sum = n; int* p = new int[n]; if (m == 1) dfs1(n, 0, p); else if (m == 2) dfs2(n, 0, p); return 0; }
