遞歸:是一種直接貨和間接調(diào)用自身或者方法的算法.
遞歸:不要遞歸太多次,一定要有退出條件.
遞歸算法解決問(wèn)題的特點(diǎn):
1.最小代碼解決復(fù)雜問(wèn)題
2.遞歸方法就是調(diào)用自身
3.必須有一個(gè)遞歸結(jié)束條件,稱(chēng)為歸出口
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:臺(tái)階問(wèn)題
static int temp(int n){
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return temp(n-1)+temp(n-2);
}
}
一耕餐、 輸入兩個(gè)整數(shù) n 和 m劫谅，從數(shù)列1，2远剩，3...n 中隨意取幾個(gè)數(shù)贫奠，使其和等于m ,要求將其中所有的可能組合列出來(lái)
解題思路： 將m分解成n以內(nèi)的解為：f(n,m)痴腌，分解成兩個(gè)子問(wèn)題：f(n-1,m-n)和f(n-1,m)
import java.util.ArrayList;
// 動(dòng)態(tài)規(guī)劃? 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));
}
}
二焰坪、 兔子在出生兩個(gè)月后，就有繁殖能力阁猜，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來(lái)丸逸。如果所有兔子都不死，那么若干月以后可以繁殖多少對(duì)兔子剃袍？
解題思路： 將第n天設(shè)置為fn? 第n-1天為 f(n-1)? 第n-2天為 f(n-2)? ? 有上述規(guī)律可的
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對(duì)? ? 1對(duì)? ? ? 2對(duì)? ? ? 3對(duì)? ? 5對(duì)? ? ? 8對(duì)? ? ? ? 13對(duì)
// f(n) = f(n - 1) + f(n - 2)? ? (斐波那契數(shù)值)
}
