递归

递归:是一种直接货和间接调用自身或者方法的算法.

递归:不要递归太多次,一定要有退出条件.

递归算法解决问题的特点:

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)    (斐波那契数值)

}