在計(jì)算機(jī)領(lǐng)域里面，很多問題都可以要采用遞歸算法來解決。遞歸中，最長用到的方法就是回溯法。我們具體分析問題的時候，可以發(fā)現(xiàn)這類問題本質(zhì)是一個樹的形狀。
一、遞歸算法
遞歸算法的本質(zhì)還是將原來的問題轉(zhuǎn)化為了更小的同一問題，進(jìn)行解決。一般注意兩點(diǎn)：
1、遞歸終止的條件。對應(yīng)到了遞歸算法中最基本的問題，也是最最簡單的問題。
2、遞歸過程。遞歸過程需要將原問題一步一步的推到更小的同一問題，更小的意思就是子問題解決起來就更加的簡單。有寫情況是能夠找到一個遞推的公式的。這個過程中就需要透徹的去理解遞歸函數(shù)的意義。明確這個函數(shù)的輸入和輸出是什么，這樣來寫的話，就清晰多了。
- 例子1、我們常見的斐波那契數(shù)列，這個例子算法用爛了
因?yàn)橛辛诉@樣的遞歸公式，那么我們就很容易的能看出來遞歸的終止條件就是我們知道的f(0)和f(1)了。有了f(0)和f(1)之后，我們就能夠繼續(xù)的遞推出f(3)一直到f(n)了。
def fib(n):
#遞歸的終止條件
if n==0:
return 1
elif n==1:
return 1
#遞歸的過程，已經(jīng)有了現(xiàn)成的公式了，所以好寫出來
else:
return f(n-1)+f(n-2)
- 例子2、對一個數(shù)組進(jìn)行一個求和的操作
通常我們是用一個for循環(huán)就能夠求出來一個數(shù)組的和是多少。也就是下面的簡單的代碼：
def Sum(nums):
total=0
for i in nums:
total +=1
return total
但是我們現(xiàn)在才用一個遞歸算法的思想來解決這個問題:
# 函數(shù)定義為計(jì)算[left, ..., n)區(qū)間里面的所有元素的和
def Sum(nums, left):
#遞歸的終止條件：left和nums數(shù)組長度時候，那么就沒有求和的元素，所以我們就返回了0.
if left==len(nums):
return 0
#遞歸的邏輯部分，就是按照我們上面的遞歸公式了。
else:
return Sum(nums, left+1)+nums[left]
if __name__ =="__main__":
test_arr = [1,2,3,4,5,6,7,8]
print(Sum(test_arr), 0)
# 得到的結(jié)果就是36了
像我們常見的數(shù)據(jù)結(jié)構(gòu)如鏈表、樹、圖等都是有著天然的遞歸結(jié)構(gòu)的，鏈表由于是一個線性的結(jié)構(gòu)，那么通常我們也是能夠直接循環(huán)遍歷就能解決問題的，但是這里我們用遞歸法來解決一下LeetCode上面的問題
LeetCode 203 移除鏈表元素
分析：鏈表的結(jié)構(gòu)可以理解成一個節(jié)點(diǎn)連接這一個更短的鏈表，這樣依次一直看下去，直到最后一個節(jié)點(diǎn)None，那么我們這個時候的遞歸終止條件就是head指向None了，返回的就是None
class Solution:
# 我們的返回就是一個節(jié)點(diǎn)的指針
def removeElements(self, head: ListNode, val: int) -> ListNode:
# 遞歸的終止條件就是head指向None的時候，返回None
if head==None:
return None
# 遞歸的過程，要是head的val屬性和要刪除的元素的相等，那么就是返回了head的下一個節(jié)點(diǎn)，不相等的話，那么就留住它。
head.next = self.removeElements(head.next, val)
return head.next if head.val==val else head
二、回溯法
深入的理解遞歸算法之后，我們就開始進(jìn)行回溯法的學(xué)習(xí)。通過LeetCode上面的幾道題，我們來深入的探討一下遞歸與回溯法的應(yīng)用。
持續(xù)更新中...
數(shù)據(jù)結(jié)構(gòu)與算法系列博客：
一、數(shù)據(jù)結(jié)構(gòu)與算法概述
二、數(shù)組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊(duì)列（Stack and Queue
五、樹（Trees）
六、遞歸與回溯算法
七、動態(tài)規(guī)劃
八、排序與搜索
九、哈希表
參考資料
1、
2、
3、
