遞歸是一種通過(guò)調(diào)用自身的方式來(lái)解決問(wèn)題的算法。在遞歸算法中，問(wèn)題被分解為更小的相似子問(wèn)題，然后通過(guò)對(duì)這些子問(wèn)題的解進(jìn)行組合來(lái)解決原始問(wèn)題。遞歸算法通常包含兩個(gè)主要部分：
- 基本情況（Base Case）： 定義問(wèn)題的最小規(guī)模，直接解答而不再進(jìn)行遞歸。基本情況是遞歸算法的出口，防止算法陷入無(wú)限遞歸。
- 遞歸步驟： 在問(wèn)題規(guī)模較大時(shí)，將問(wèn)題劃分為相似但規(guī)模較小的子問(wèn)題，并通過(guò)遞歸調(diào)用解決這些子問(wèn)題。遞歸調(diào)用自身是遞歸算法的核心。
遞歸算法在解決許多問(wèn)題上非常強(qiáng)大，尤其是對(duì)于那些可以通過(guò)分解為子問(wèn)題并且存在重疊子問(wèn)題的情況。遞歸通常使算法更加簡(jiǎn)潔、清晰，但需要謹(jǐn)慎處理基本情況，以避免無(wú)限遞歸。
經(jīng)典的遞歸問(wèn)題包括漢諾塔問(wèn)題、階乘計(jì)算、斐波那契數(shù)列等。遞歸也在許多算法和數(shù)據(jù)結(jié)構(gòu)中發(fā)揮著重要的作用，例如樹(shù)的遍歷、圖的深度優(yōu)先搜索等。
如何理解遞歸？
1.遞歸展開(kāi)的細(xì)節(jié)圖
2.二叉樹(shù)中的題目
3.宏觀看待遞歸的過(guò)程
1.不要在意遞歸的細(xì)節(jié)展開(kāi)圖
2.把遞歸的函數(shù)當(dāng)成一個(gè)黑盒
3.相信這個(gè)黑盒一定能完成這個(gè)任務(wù)
如何寫好遞歸？
1.先找到相同的子問(wèn)題!!!->函數(shù)頭的設(shè)計(jì)
2.只關(guān)心某一個(gè)子問(wèn)題是如何解決的 ->函數(shù)體的書寫
3.注意一下遞歸函數(shù)的出口即可
01.漢諾塔問(wèn)題
題目鏈接：https://leetcode.cn/problems/hanota-lcci/
在經(jīng)典漢諾塔問(wèn)題中，有 3 根柱子及 N 個(gè)不同大小的穿孔圓盤，盤子可以滑入任意一根柱子。一開(kāi)始，所有盤子自上而下按升序依次套在第一根柱子上(即每一個(gè)盤子只能放在更大的盤子上面)。移動(dòng)圓盤時(shí)受到以下限制:
(1) 每次只能移動(dòng)一個(gè)盤子;
(2) 盤子只能從柱子頂端滑出移到下一根柱子;
(3) 盤子只能疊在比它大的盤子上。
請(qǐng)編寫程序，用棧將所有盤子從第一根柱子移到最后一根柱子。
你需要原地修改棧。
示例1:
輸入：A = [2, 1, 0], B = [], C = []
輸出：C = [2, 1, 0]
示例2:
輸入：A = [1, 0], B = [], C = []
輸出：C = [1, 0]
提示:
- A中盤子的數(shù)目不大于14個(gè)。
思路
對(duì)于這類問(wèn)題我們可以使用數(shù)學(xué)中的歸結(jié)思想，先畫圖分析由1到n的情況，我們可以總結(jié)出下面這三個(gè)步驟
代碼文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-831177.html
class Solution {
void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n)
{
if(n==1){
C.push_back(A.back());
A.pop_back();
return;
}
dfs(A,C,B,n-1);
C.push_back(A.back());
A.pop_back();
dfs(B,A,C,n-1);
}
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
dfs(A,B,C,A.size());
}
};
- 定義一個(gè)私有的遞歸函數(shù)
dfs，該函數(shù)將 A 柱上的 n 個(gè)盤子通過(guò) B 柱移動(dòng)到 C 柱。參數(shù)A、B和C分別表示三個(gè)柱子的盤子狀態(tài)，n表示要移動(dòng)的盤子數(shù)量。 - 在遞歸函數(shù)中，當(dāng)只有一個(gè)盤子時(shí)，直接將 A 柱的盤子移到 C 柱上，然后返回。
- 在遞歸函數(shù)中，先將 A 柱上的 n-1 個(gè)盤子通過(guò) C 柱移動(dòng)到 B 柱上，然后將 A 柱上的最后一個(gè)盤子移動(dòng)到 C 柱上，最后將 B 柱上的 n-1 個(gè)盤子通過(guò) A 柱移動(dòng)到 C 柱上。
- 在公有函數(shù)
hanota中，調(diào)用遞歸函數(shù)dfs，傳入 A、B、C 三個(gè)柱子的狀態(tài)和盤子數(shù)量。
02.合并兩個(gè)有序鏈表
題目鏈接：https://leetcode.cn/problems/merge-two-sorted-lists/
將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]
提示：
- 兩個(gè)鏈表的節(jié)點(diǎn)數(shù)目范圍是
[0, 50] -100 <= Node.val <= 100-
l1和l2均按 非遞減順序 排列
思路
這里我們?nèi)绻麆澐譃樽訂?wèn)題，每次就拿出最小的那個(gè)節(jié)點(diǎn)當(dāng)做頭節(jié)點(diǎn)，拼接剩下的當(dāng)前節(jié)點(diǎn)尾部的節(jié)點(diǎn)和另一個(gè)鏈表的頭節(jié)點(diǎn)相比較的更小的點(diǎn)，最后誰(shuí)被拼接完了，就直接拼接另一條鏈表剩下的，這樣不難看出，每次的步驟都是重復(fù)的，于是我們可以使用遞歸的思想來(lái)解決這道問(wèn)題。
代碼
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1) return list2;
if(!list2) return list1;
if(list1->val<=list2->val){
list1->next=mergeTwoLists(list1->next,list2);
return list1;
}else{
list2->next=mergeTwoLists(list2->next,list1);
return list2;
}
}
};
- 如果
list1為空，說(shuō)明第一個(gè)鏈表為空，直接返回list2。 - 如果
list2為空，說(shuō)明第二個(gè)鏈表為空，直接返回list1。 - 接下來(lái)比較
list1和list2的頭節(jié)點(diǎn)的值，選擇較小的節(jié)點(diǎn)作為新鏈表的頭節(jié)點(diǎn)。 - 如果
list1的頭節(jié)點(diǎn)值小于等于list2的頭節(jié)點(diǎn)值，將list1的下一個(gè)節(jié)點(diǎn)與list2合并，并返回list1作為新鏈表的頭節(jié)點(diǎn)。 - 如果
list2的頭節(jié)點(diǎn)值小于list1的頭節(jié)點(diǎn)值，將list2的下一個(gè)節(jié)點(diǎn)與list1合并，并返回list2作為新鏈表的頭節(jié)點(diǎn)。
03.反轉(zhuǎn)鏈表
題目鏈接：https://leetcode.cn/problems/reverse-linked-list/
給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2]
輸出：[2,1]
示例 3：
輸入：head = []
輸出：[]
提示：
- 鏈表中節(jié)點(diǎn)的數(shù)目范圍是
[0, 5000] -5000 <= Node.val <= 5000
**進(jìn)階：**鏈表可以選用迭代或遞歸方式完成反轉(zhuǎn)。你能否用兩種方法解決這道題？
思路
若我們直接遍歷到最后的節(jié)點(diǎn)再逐個(gè)向前改變指向，在每次接入前一個(gè)節(jié)點(diǎn)時(shí)，將它的next指向空，最終返回頭節(jié)點(diǎn)即可。
- 遞歸函數(shù)的含義：交給你?個(gè)鏈表的頭指針，你幫我逆序之后，返回逆序后的頭結(jié)點(diǎn)；
- 函數(shù)體：先把當(dāng)前結(jié)點(diǎn)之后的鏈表逆序，逆序完之后，把當(dāng)前結(jié)點(diǎn)添加到逆序后的鏈表后面即可；
- 遞歸出口：當(dāng)前結(jié)點(diǎn)為空或者當(dāng)前只有?個(gè)結(jié)點(diǎn)的時(shí)候，不用逆序，直接返回
代碼
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode* newhead = reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return newhead;
}
};
04.兩兩交換鏈表中的節(jié)點(diǎn)
題目鏈接：https://leetcode.cn/problems/swap-nodes-in-pairs/
給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。
示例 1：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
示例 2：
輸入：head = []
輸出：[]
示例 3：
輸入：head = [1]
輸出：[1]
提示：
- 鏈表中節(jié)點(diǎn)的數(shù)目在范圍
[0, 100]內(nèi) 0 <= Node.val <= 100
思路
我們將問(wèn)題劃分為子問(wèn)題，先交換當(dāng)前節(jié)點(diǎn)的下兩個(gè)節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向遞歸操作的結(jié)果，返回新的頭節(jié)點(diǎn)。
代碼
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 如果鏈表為空或者只有一個(gè)節(jié)點(diǎn)，無(wú)需交換，直接返回原鏈表頭指針
if (!head || !head->next)
return head;
// 遞歸調(diào)用，交換當(dāng)前節(jié)點(diǎn)的下兩個(gè)節(jié)點(diǎn)
ListNode* tmp = swapPairs(head->next->next);
// 將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)
ListNode* ret = head->next;
// 將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)，實(shí)現(xiàn)交換
head->next->next = head;
// 將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向遞歸操作的結(jié)果
head->next = tmp;
// 返回新的頭節(jié)點(diǎn)
return ret;
}
};
-
if (!head || !head->next)：檢查鏈表是否為空或者只有一個(gè)節(jié)點(diǎn)。如果是，直接返回原鏈表頭指針，因?yàn)椴恍枰M(jìn)行交換。 -
ListNode* tmp = swapPairs(head->next->next);：遞歸調(diào)用swapPairs函數(shù)，傳入當(dāng)前節(jié)點(diǎn)的下兩個(gè)節(jié)點(diǎn)。這樣就會(huì)從鏈表的末尾開(kāi)始，每次交換兩個(gè)相鄰的節(jié)點(diǎn)，然后返回新的頭節(jié)點(diǎn)。 -
ListNode* ret = head->next;：將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)，因?yàn)樵诮粨Q過(guò)程中，它會(huì)變成新的頭節(jié)點(diǎn)。 -
head->next->next = head;：將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)，實(shí)現(xiàn)交換操作。 -
head->next = tmp;：將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向遞歸操作的結(jié)果，即當(dāng)前節(jié)點(diǎn)的下兩個(gè)節(jié)點(diǎn)交換后的頭節(jié)點(diǎn)。 -
return ret;：返回新的頭節(jié)點(diǎn)，作為上層遞歸調(diào)用的結(jié)果。
05.Pow(x, n)
題目鏈接：https://leetcode.cn/problems/powx-n/
實(shí)現(xiàn) pow(x, n) ，即計(jì)算 x 的整數(shù) n 次冪函數(shù)（即，xn ）。
示例 1：
輸入：x = 2.00000, n = 10
輸出：1024.00000
示例 2：
輸入：x = 2.10000, n = 3
輸出：9.26100
示例 3：
輸入：x = 2.00000, n = -2
輸出：0.25000
解釋：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1-
n是一個(gè)整數(shù) - 要么
x不為零，要么n > 0。 -104 <= xn <= 104
思路
這里我們可以使用二分的思想，可以快速提高效率，例如將3的32次方分為兩個(gè)3的16次方相乘，不斷向下遞歸，最終返回相乘結(jié)果，只不過(guò)這里需要注意負(fù)數(shù)和奇偶次方問(wèn)題需要單獨(dú)判斷。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-831177.html
代碼
class Solution {
public:
double myPow(double x, int n) {
// 如果指數(shù)n為負(fù)數(shù)，將問(wèn)題轉(zhuǎn)化為計(jì)算 x^(-n)，即取倒數(shù)
return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);
}
double Pow(double x, long long n) {
// 遞歸終止條件：n為0時(shí)，任何數(shù)的0次方都為1
if (n == 0)
return 1.0;
// 遞歸調(diào)用，計(jì)算 x^(n/2)
double tmp = Pow(x, n / 2);
// 如果n為奇數(shù)，返回 tmp * tmp * x
if (n % 2)
return tmp * tmp * x;
else // 如果n為偶數(shù)，返回 tmp * tmp
return tmp * tmp;
}
};
-
return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);：根據(jù)指數(shù)n的正負(fù)情況，決定調(diào)用正指數(shù)或者取倒數(shù)的遞歸函數(shù)。當(dāng)n為負(fù)數(shù)時(shí)，將其轉(zhuǎn)化為正數(shù)計(jì)算，并返回結(jié)果的倒數(shù)。 -
double Pow(double x, long long n)：遞歸函數(shù)，用于計(jì)算 x^n。 -
if (n == 0) return 1.0;：遞歸終止條件。當(dāng)指數(shù)n為0時(shí)，任何數(shù)的0次方都為1。 -
double tmp = Pow(x, n / 2);：遞歸調(diào)用，計(jì)算 x^(n/2)。這里利用了指數(shù)冪的性質(zhì)，將問(wèn)題規(guī)模減半，減少了計(jì)算量。 -
if (n % 2)：判斷n是否為奇數(shù)。 -
return tmp * tmp * x;：如果n為奇數(shù)，返回 tmp * tmp * x，這是因?yàn)?x^n = (x(n/2))2 * x。
n) : Pow(x, n);`：根據(jù)指數(shù)n的正負(fù)情況，決定調(diào)用正指數(shù)或者取倒數(shù)的遞歸函數(shù)。當(dāng)n為負(fù)數(shù)時(shí)，將其轉(zhuǎn)化為正數(shù)計(jì)算，并返回結(jié)果的倒數(shù)。 -
double Pow(double x, long long n)：遞歸函數(shù)，用于計(jì)算 x^n。 -
if (n == 0) return 1.0;：遞歸終止條件。當(dāng)指數(shù)n為0時(shí)，任何數(shù)的0次方都為1。 -
double tmp = Pow(x, n / 2);：遞歸調(diào)用，計(jì)算 x^(n/2)。這里利用了指數(shù)冪的性質(zhì)，將問(wèn)題規(guī)模減半，減少了計(jì)算量。 -
if (n % 2)：判斷n是否為奇數(shù)。 -
return tmp * tmp * x;：如果n為奇數(shù)，返回 tmp * tmp * x，這是因?yàn)?x^n = (x(n/2))2 * x。 -
return tmp * tmp;：如果n為偶數(shù)，返回 tmp * tmp，這是因?yàn)?x^n = (x(n/2))2。
到了這里，關(guān)于算法沉淀——遞歸（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[職場(chǎng)] 會(huì)計(jì)學(xué)專業(yè)學(xué)什么 #其他#知識(shí)分享#職場(chǎng)發(fā)展](https://imgs.yssmx.com/Uploads/2024/02/830441-1.jpeg)
