1真椿、遞歸原理
函數(shù)調(diào)用自身。實質(zhì)是函數(shù)每次調(diào)用自身時干厚，都把一個問題分解為子問題李滴。然后我們通過子問題的解螃宙，向上去構(gòu)造大問題的解。
為了確保遞歸函數(shù)不會導致無限循環(huán)所坯，它應具有以下屬性：
一個簡單的基本案例（basic case） —— 能夠不使用遞歸來產(chǎn)生答案的終止方案谆扎。
一組規(guī)則，也稱作遞推關(guān)系（recurrence relation）芹助，可將所有其他情況拆分到基本案例堂湖。
2、遞歸函數(shù)
每當遞歸函數(shù)調(diào)用自身時状土，它都會將給定的問題拆解為子問題无蜂。遞歸調(diào)用繼續(xù)進行，直到到子問題無需進一步遞歸就可以解決的地步蒙谓。
遞歸分為三個步驟：
1斥季、結(jié)束條件（Base case）
也就是遞歸的終點，可以直接得到結(jié)果累驮，不需要進一步的遞歸調(diào)用就可以直接計算答案的情況酣倾。沒有結(jié)束條件，遞歸就會形成死循環(huán)谤专。有時躁锡，基本案例也被稱為 bottom cases。
2置侍、拆解
將問題拆解為小問題稚铣。
3、組合
通過遞推關(guān)系式墅垮，將小問題構(gòu)造為大問題惕医。
例題：反轉(zhuǎn)鏈表
迭代法：
三個指針：pre,cur,next
- next先保存cur的下一個節(jié)點
- cur->next再指向pre
- pre=cur
- cur=next;
時間復雜度：O(n)，空間復雜度：O(1)
遞歸法：
假設(shè)除了頭結(jié)點算色，其他節(jié)點都已經(jīng)被反轉(zhuǎn)抬伺。如何反轉(zhuǎn)頭結(jié)點與后面的鏈表？
- 首先我們從后往前進行反轉(zhuǎn)
- 后面的節(jié)點指向前一個節(jié)點：head->next->next=head;
- 前一個節(jié)點不能指向后一個節(jié)點：head->next=nullptr;
時間復雜度：O(n)灾梦，空間復雜度：O(n)
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head||!head->next)
return head;
ListNode* cur=reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return cur;
}
};
3峡钓、記憶化
遞歸算法中存在重復計算問題。每一次遞歸都要從頭開始若河∧苎遥可以借助外部存儲，將已經(jīng)便利過的節(jié)點值存下來萧福，在遞歸中先判斷該點是否存儲過拉鹃。最后，將計算得到的值再進行存儲。
例題：斐波那契數(shù)列\(zhòng)爬樓梯
（1）遞歸膏燕。時間復雜度：O(2^n)钥屈。樹形遞歸的大小為 2^n “颖瑁空間復雜度：O(n)篷就。遞歸樹的深度可以達到 n 。
（2）記憶化遞歸近忙。時間復雜度：O(n)竭业。空間復雜度：O(n)及舍。
（3）動態(tài)規(guī)劃未辆。時間復雜度：O(n)』魑常空間復雜度：O(1)。
4钾麸、時間復雜度和空間復雜度
我自己的理解是：時間復雜度是語句最多執(zhí)行的次數(shù)更振。空間復雜度是存儲變量所需要的最大空間饭尝。
例如肯腕，把結(jié)構(gòu)中的每個變量遍歷一遍，時間復雜度是O(n)钥平。把它們?nèi)４娴綌?shù)組实撒，空間復雜度是O(n)。
時間復雜度：隨著自變量的增長涉瘾，算法所需時間的增長情況知态。 空間復雜度是指：
算法運行期間所需占用的所有內(nèi)存空間
5、尾遞歸
尾遞歸函數(shù)是遞歸函數(shù)的一種立叛，其中遞歸調(diào)用是遞歸函數(shù)中的最后一條指令负敏。并且在函數(shù)中應該只有一次遞歸調(diào)用。
尾遞歸的特點就是我們可以很容易的把它轉(zhuǎn)成 迭代（iterative ）的寫法秘蛇，當然有些智能的編譯器會自動幫我們做了（不是說顯性的轉(zhuǎn)化其做，而是在運行時按照 iterative 的方式去運行，實際消耗的空間是 O(1)）
尾遞歸的好處是赁还，它可以避免遞歸調(diào)用期間椦梗空間開銷的累積，因為系統(tǒng)可以為每個遞歸調(diào)用重用棧中的固定空間艘策。
為什么呢蹈胡？是因為在尾遞歸的情況下，一旦從遞歸調(diào)用返回，我們也會立即返回审残，因此我們可以跳過整個遞歸調(diào)用返回鏈梭域，直接返回到原始調(diào)用方。這意味著我們根本不需要所有遞歸調(diào)用的調(diào)用棧搅轿，這為我們節(jié)省了空間病涨。
》 參考文獻：這才是面試官想聽的：詳解「遞歸」正確的打開方式
