递归:是一种直接货和间接调用自身或者方法的算法.
递归:不要递归太多次,一定要有退出条件.
递归算法解决问题的特点:
1.最小代码解决复杂问题
2.递归方法就是调用自身
3.必须有一个递归结束条件,称为归出口
public class test4 {
public static void main(String[] args) {
System.out.println(test4.fact(5));
System.out.println(test4.sum(100));
System.out.println(test4.temp(11));
}
//递归,不要递归太多次,一定要有退出条件
案例1:求乘积
static int fact(int n){
if(n == 1){
return 1;
}
return n*fact(n-1);
}
案例2:求和
static int sum(int i){
if(i == 1){
return 1;
}
return i+sum(i-1);
}
案例3:台阶问题
static int temp(int n){
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return temp(n-1)+temp(n-2);
}
}
一、 输入两个整数 n 和 m，从数列1，2，3...n 中随意取几个数，使其和等于m ,要求将其中所有的可能组合列出来
解题思路： 将m分解成n以内的解为：f(n,m)，分解成两个子问题：f(n-1,m-n)和f(n-1,m)
import java.util.ArrayList;
// 动态规划 0-1背包 第一题
public class HomeWork {
public static void main(String[] args) {
int m = 13;int n = 9;
HomeWork homeWork = new HomeWork();
homeWork.func(m, n, new ArrayList());
}
void func(int m, int n, ArrayListlist) {
if (m == 0) { // 改输出了
System.out.println(list);
return;
}
if (m <= 0 || n < 0) {
return;
}
// 不包含n的情况
this.func(m, n - 1, new ArrayList<>(list));
// 包含n的情况
list.add(n);
this.func(m - n, n - 1, new ArrayList<>(list));
}
}
二、 兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么若干月以后可以繁殖多少对兔子？
解题思路： 将第n天设置为fn 第n-1天为 f(n-1) 第n-2天为 f(n-2) 有上述规律可的
f(n)=f(n-1)+f(n-2)
public class HomeWork3 {
//f(n)=f(n-1)+f(n-2)
public static void main(String[] args) {
int day = 7;
HomeWork3 h = new HomeWork3();
System.out.println(h.fun(day));
}
int fun(int day) {
if (day <= 2) {
return 1;
}
return fun(day -1 ) + fun(day -2);
}
// 第一月 第二月 第三月 第四月 第五月 第六月 第七月
// 1对 1对 2对 3对 5对 8对 13对
// f(n) = f(n - 1) + f(n - 2) (斐波那契数值)
}
