沐鳴平台_你真的懂遞歸嗎?

因為很多算法思想都基於遞歸,無論是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