什么是遞歸帝牡？
簡單的理解就是：遞歸就是方法自己調(diào)用自己,每次調(diào)用時(shí)傳入不同的變量.遞歸有助于編程者解決復(fù)雜問題,同時(shí)可以讓代碼變 得簡潔
遞歸能解決什么問題？
- 各種數(shù)學(xué)問題如∶8皇后問題抓歼，漢諾塔，階乘問題，迷宮問題掩浙，球和籃子的問題。
- 各種算法中也會(huì)使用到遞歸秸歧，比如快排厨姚，歸并排序，二分查找键菱，分治算法等谬墙。3. 將用棧解決的問題-->遞歸代碼比較簡潔
遞歸小案例 來理解遞歸調(diào)用機(jī)制
- 打印問題
- 階乘問題
static class T {
//打印
public void test(int n) {
if (n > 2) {
test(n - 1);
}
System.out.println("n=" + n);
}
//factorial 階乘
public int factorial(int n) {
if (n == 1) {
return 1;
} else {
return factorial(n - 1) * n;
}
}
}
public static void main(String[] args) {
// 打印問題
T t1 = new T();
t1.test(4);//輸出什么？ n=2 n=3 n=4
// 階乘問題
int res = t1.factorial(5);
System.out.println("5 的階乘 res =" + res);
}
打印問題的方法調(diào)用分析圖
階乘問題方法分析圖
遞歸的重要規(guī)則
- 執(zhí)行一個(gè)方法時(shí)经备，就創(chuàng)建一個(gè)新受保護(hù)的獨(dú)立空間（検锰В空間）
- 方法的局部變量是獨(dú)立的，不會(huì)相互影響侵蒙，比如n變量
- 如果方法中使用的是引用類型變量（比如數(shù)組造虎，對(duì)象），就會(huì)共享該引用類型的數(shù)據(jù)蘑志。
- 遞歸必須向退出遞歸的條件逼近累奈，否則就是無限遞歸贬派，出現(xiàn)StackOverflowError，死龜了
- 當(dāng)一個(gè)方法執(zhí)行完畢澎媒，或者遇到return搞乏，就會(huì)返回，遵守誰調(diào)用戒努，就
將結(jié)果返回給誰请敦，同時(shí)當(dāng)方法執(zhí)行完畢或者返回時(shí)，該方法也就執(zhí)行完畢储玫。
既然我們已經(jīng)知道遞歸的基本使用了侍筛，用遞歸解決下面問題看看
- 請(qǐng)使用遞歸的方式求出斐波那契數(shù)1，1撒穷，2匣椰，3，5端礼，8禽笑，13..給你一個(gè)整數(shù)n，
求出它的值是多
/**
* @description: 請(qǐng)使用遞歸的方式求出斐波那契數(shù)1蛤奥，1佳镜，2，3凡桥，5蟀伸，8，13..給你一個(gè)整數(shù)n,求出它的值是多
* 1. 傳入的數(shù)必須大于 0
* 2. n = 1 斐波那契數(shù) == 1
* 2. n = 2 斐波那契數(shù) == 1
* 2. n >= 3 斐波那契數(shù) 等于前兩數(shù)之和
* @param: n 表示獲取第幾位斐波拉契數(shù)
* @return: 斐波那契數(shù)
* @author Mr.luo
* @date: 2021/12/5 1:41 下午
*/
public static int fibonacci(int n){
if(n >= 1){
if(n == 1 || n == 2){
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
} else {
return -1;
}
}
- 猴子吃桃子問題∶有一堆桃子缅刽，猴子第一天吃了其中的一半啊掏，并再多吃了一個(gè)!以后每天猴子都吃其中的一半，然后再多吃一個(gè)拷恨。當(dāng)?shù)降?0天時(shí)脖律，想再吃時(shí)（即還沒吃）發(fā)現(xiàn)只有1個(gè)桃子了谢肾。問題∶最初共多少個(gè)桃子?
/**
* @description: 猴子吃桃子問題∶
* 有一堆桃子腕侄，猴子第一天吃了其中的一半，并再多吃了一個(gè)!以后每天猴子都吃其中的一半芦疏，然后再多吃一個(gè)冕杠。
* 當(dāng)?shù)降?0天時(shí)，想再吃時(shí)（即還沒吃）發(fā)現(xiàn)只有1個(gè)桃子了酸茴。問題∶最初共多少個(gè)桃子?
* 思路分析：已知條件 ： 每天吃一半 再多吃 一個(gè) 分预， 再第十天的時(shí)候只有一個(gè)桃子了
* 逆向推導(dǎo)：
* 第十天 day = 1 個(gè)
* 第九天 day = (第十天 + 1) * 2
* 第八天 day = (第九天 + 1) * 2
* 規(guī)律：當(dāng)天的桃子數(shù)量 = （前一天桃子數(shù)量 + 1） * 2
* @author Mr.luo
* @date: 2021/12/5 1:55 下午
*/
public static int monkeyEatingPeach(int day){
if (day == 10) {
return 1;
} else if(day > 0 && day <= 9) {
return (monkeyEatingPeach(day + 1) +1) * 2;
} else {
System.out.println("day 輸入錯(cuò)誤");
}
return -1;
}
我將在接下來的篇章里用遞歸思想解決 ：
8皇后問題，漢諾塔薪捍，階乘問題笼痹，迷宮問題
