沐鳴平台_你真的懂遞歸嗎?
因為很多算法思想都基於遞歸,無論是DFS、樹的遍歷、分治算法、動態規劃等都是遞歸思想的應用。學會了用遞歸來解決問題的這種思維方式,再去學習其他的算法思想,無疑是事半功倍的。
遞歸的本質
無可奈何花落去,似曾相識燕歸來。
遞歸,去的過程叫“遞” ,回來的過程叫“歸”。
探究遞歸的本質要從計算機語言的本質說起。
計算機語言的本質是彙編語言,彙編語言的特點就是沒有循環嵌套。
我們平時使用高級語言來寫的 if..else.. 也好, for/while 也好,在實際的機器指令層面來看,就是一個簡單的地址跳轉,跳轉到特定的指令位置,類似於 goto 語句。
機器嘛,總是沒有溫度的。我們再來看一個生活中的例子,大家小的時候一定用新華字典查過字。如果要查的字的解釋中,也有不認識的字。那就要接着查第二個字,不幸第二個字的解釋中,也有不認識的字,就要接着查第三個字。直到有一個字的解釋我們完全可以看懂,那麼遞歸就到了盡頭。接下來我們開始後退,逐個清楚了之前查過的每一個字,最終,我們明白了我們要查的第一個字。
我們再從一段代碼中,體會一下遞歸。
const factorial = function(n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
factorial 是一個實現階乘的函數。我們以階乘 f(6) 來看下它的遞歸。
f(6) = n * f(5),所以 f(6) 需要拆解成 f(5) 子問題進行求解,以此類推 f(5) = n * f(4) ,也需要進一步拆分 … 直到 f(1),這是遞的過程。 f(1) 解決后,依次可以解決f(2)…. f(n)最後也被解決,這是歸的過程。
從上面兩個例子可以看出,遞歸無非就是把問題拆解成具有相同解決思路的子問題,直到最後被拆解的子問題不能夠拆分,這個過程是“遞”。當解決了最小粒度可求解的子問題后,在“歸”的過程中順其自然的解決了最開始的問題。
搞清楚了遞歸的本質,在利用遞歸思想解題之前,我們還要記住滿足遞歸的三個條件:
1.問題可以被分解成幾個子問題
2.問題和子問題的求解方法完全相同
3.遞歸終止條件
敲黑板,記筆記!
LeetCode 真題
我們拿一道 LeetCode 真題練練手。
求解斐波那契數列,該數列由 0 和 1 開始,後面的每一項数字都是前面兩項数字的和,也就是:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
給定 N,計算 F(N)。
遞歸樹如上圖所示,要計算 f(5),就要先計算子問題 f(4) 和 f(3),要計算 f(4),就要先計算齣子問題 f(3)和 f(2)…
以此類推,當最後計算到 f(0) 或者 f(1) 的時候,結果已知,然後層層返回結果。
經過如上分析可知,滿足遞歸的三個條件,開始擼代碼。
遞歸解法
const fib = function(n) {
if (n == 0 || n == 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
或者可以這樣炫技:
const fib = n => n <= 0 ? 0 : n == 1 ? 1: fib(n - 2) + fib(n - 1);
還沒完事,記住要養成習慣,一定要對自己寫出的算法進行複雜度分析。這部分在專欄JavaScript算法時間、空間複雜度分析已經講解過,沒看過的同學請點擊鏈接移步。
複雜度分析
- 空間複雜度為 O(n)
- 時間複雜度 O(2^n)
總時間 = 子問題個數 * 解決一個子問題需要的時間
- 子問題個數即遞歸樹中的節點總數 2^n
- 解決一個子問題需要的時間,因為只有一個加法操作 fib(n-1) + fib(n-2) ,所以解決一個子問題的時間為 O(1)
二者相乘,得出算法的時間複雜度為 O(2^n),指數級別,裂開了呀。
面試的時候如果只寫這樣一種解法就 GG 了。
其實這道題我們可以利用動態規劃或是黃金分割比通項公式來求解,動態規劃想要講清楚的話篇幅較長,後續開個專欄會詳細介紹,這裏看不懂的同學們不要着急。
(選擇這道題的初衷是為了讓大家理解遞歸。)
動態規劃解法
遞歸是自頂向下(看上文遞歸樹),動態規劃是自底向上,將遞歸改成迭代。為了減少空間消耗,只存儲兩個值,這種解法是動態規劃的最優解。
- 時間複雜度 O(n)
- 空間複雜度 O(1)
const fib = function(n) {
if (n == 0) {
return 0;
}
let a1 = 0;
let a2 = 1;
for (let i = 1; i < n; i++) {
[a1, a2] = [a2, a1 + a2];
}
return a2;
}
黃金分割比通項公式解法
- 時間複雜度 O(logn)
- 空間複雜度 O(1)
const fib = function(n) {
return (Math.pow((1 + Math.sqrt(5))/2, n) - Math.pow((1 - Math.sqrt(5))/2, n)) / Math.sqrt(5);
}
除此之外,還可以利用矩陣方程來解題,這裏不再展開。
回到遞歸,在學習遞歸的過程中,最大的陷阱就是人肉遞歸。人腦是很難把整個“遞”“歸”過程毫無差錯的想清楚的。但是計算機恰好擅長做重複的事情,那我們便無須跳入細節,利用數學歸納法的思想,將其抽象成一個遞推公式。相信它可以完成這個任務,其他的交給計算機就好了。
如果你非要探究裏面的細節,挑戰人腦壓棧,那麼你只可能會陷入其中,甚至懷疑人生。南牆不好撞,該回頭就回頭。
你凝望深淵的時候,深淵也在凝望你。
原文:https://segmentfault.com/a/1190000022677431
站長推薦
1.雲服務推薦: 國內主流雲服務商,各類雲產品的最新活動,優惠券領取。地址:阿里雲騰訊雲華為雲
2.廣告聯盟: 整理了目前主流的廣告聯盟平台,如果你有流量,可以作為參考選擇適合你的平台點擊進入
鏈接: http://www.fly63.com/article/detial/9061