JavaScript 數據結構與算法之美 - 遞歸

Rocko 發布于2019-08-23 18:29 / 1048人閱讀

摘要：遞歸常見問題及解決方案警惕堆棧溢出可以聲明一個全局變量來控制遞歸的深度，從而避免堆棧溢出。文章輸出計劃數據結構與算法之美的系列文章，堅持天左右更新一篇，暫定計劃如下表。

前言

算法為王。

排序算法博大精深，前輩們用了數年甚至一輩子的心血研究出來的算法，更值得我們學習與推敲。

因為之后要講有內容和算法，其代碼的實現都要用到遞歸，所以，搞懂遞歸非常重要。

1. 定義

方法或函數調用自身的方式稱為遞歸調用，調用稱為遞，返回稱為歸。

簡單來說就是：自己調用自己。

現實例子：周末你帶著女朋友去電影院看電影，女朋友問你，咱們現在坐在第幾排啊？電影院里面太黑了，看不清，沒法數，現在你怎么辦？

于是你就問前面一排的人他是第幾排，你想只要在他的數字上加一，就知道自己在哪一排了。
但是，前面的人也看不清啊，所以他也問他前面的人。
就這樣一排一排往前問，直到問到第一排的人，說我在第一排，然后再這樣一排一排再把數字傳回來。
直到你前面的人告訴你他在哪一排，于是你就知道答案了。

基本上，所有的遞歸問題都可以用遞推公式來表示，比如:

f(n) = f(n-1) + 1; 
// 其中，f(1) = 1

f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排數，f(1) = 1 表示第一排的人知道自己在第一排。

有了這個遞推公式，我們就可以很輕松地將它改為遞歸代碼，如下：

function f(n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

2. 為什么使用遞歸？遞歸的優缺點？

優點：代碼的表達力很強，寫起來簡潔。

缺點：空間復雜度高、有堆棧溢出風險、存在重復計算、過多的函數調用會耗時較多等問題。

3. 什么樣的問題可以用遞歸解決呢？

一個問題只要同時滿足以下 3 個條件，就可以用遞歸來解決。

問題的解可以分解為幾個子問題的解。何為子問題？就是數據規模更小的問題。

比如，前面講的電影院的例子，你要知道，自己在哪一排的問題，可以分解為前一排的人在哪一排這樣一個子問題。

問題與子問題，除了數據規模不同，求解思路完全一樣

比如電影院那個例子，你求解自己在哪一排的思路，和前面一排人求解自己在哪一排的思路，是一模一樣的。

存在遞歸終止條件

比如電影院的例子，第一排的人不需要再繼續詢問任何人，就知道自己在哪一排，也就是 f(1) = 1，這就是遞歸的終止條件。

4. 遞歸常見問題及解決方案

警惕堆棧溢出：可以聲明一個全局變量來控制遞歸的深度，從而避免堆棧溢出。

警惕重復計算：通過某種數據結構來保存已經求解過的值，從而避免重復計算。

5. 如何實現遞歸？

1. 遞歸代碼編寫

寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。

2. 遞歸代碼理解

對于遞歸代碼，若試圖想清楚整個遞和歸的過程，實際上是進入了一個思維誤區。

那該如何理解遞歸代碼呢？

如果一個問題 A 可以分解為若干個子問題 B、C、D，你可以假設子問題 B、C、D 已經解決。

而且，你只需要思考問題 A 與子問題 B、C、D 兩層之間的關系即可，不需要一層層往下思考子問題與子子問題，子子問題與子子子問題之間的關系。

屏蔽掉遞歸細節，這樣子理解起來就簡單多了。

因此，理解遞歸代碼，就把它抽象成一個遞推公式，不用想一層層的調用關系，不要試圖用人腦去分解遞歸的每個步驟。

6. 例子 1. 一個階乘的例子：

function fact(num) {
  if (num <= 1) {
    return 1;
  } else {
    return num * fact(num - 1);
    }
}
fact(3) // 結果為 6

以下代碼可導致出錯：

var anotherFact = fact; 
fact = null; 
alert(antherFact(4)); //出錯

由于 fact 已經不是函數了，所以出錯。

使用 arguments.callee

arguments.callee 是一個指向正在執行的函數的指針，arguments.callee 返回正在被執行的對現象。
新的函數為：

function fact(num){ 
    if (num <= 1){ 
        return 1; 
    }else{ 
        return num * arguments.callee(num - 1); //此處更改了。 
    } 
} 
var anotherFact = fact; 
fact = null; 
alert(antherFact(4)); // 結果為 24

2. 再看一個多叉樹的例子

先看圖

葉子結點：就是深度為 0 的結點，也就是沒有孩子結點的結點，簡單的說就是一個二叉樹任意一個分支上的終端節點。

數據結構格式，參考如下代碼：

const json = {
  name: "A",
  children: [
    {
      name: "B",
      children: [
        {
          name: "E",
        },
        {
          name: "F",
        },
        {
          name: "G",
        }
      ]
    },
    {
      name: "C",
      children: [
        {
          name: "H"
        }
      ]
    },
    {
      name: "D",
      children: [
        {
          name: "I",
        },
        {
          name: "J",
        }
      ]
    }
  ]
}

我們如何獲取根節點的所有葉子節點個數呢？

遞歸代碼如下：

/**
 * 獲取根節點的所有 葉子節點 個數
 * @param {Object} json Object 對象
 */
function getLeafCountTree(json) {
  if(!json.children){
      return 1;
  } else {
      let leafCount = 0;
      for(let i = 0 ; i < json.children.length ; i++){
          // leafCount = leafCount + getLeafCountTree(json.children[i]);
          leafCount = leafCount + arguments.callee(json.children[i]);
      }
      return leafCount;
  }
}

遞歸遍歷是比較常用的方法，比如：省市區遍歷成樹、多叉樹、階乘等。

7. 文章輸出計劃

JavaScript 數據結構與算法之美 的系列文章，堅持 3 - 7 天左右更新一篇，暫定計劃如下表。

如果有錯誤或者不嚴謹的地方，請務必給予指正，十分感謝。

8. 最后

文章可以轉載，但須注明作者及出處，需要轉載到公眾號的，喊我加下白名單就行了。

參考文章：

遞歸：如何用三行代碼找到“最終推薦人”？

GPU云服務器云服務器最大值算法遞歸 java遞歸算法樹 java 樹遞歸算法背包算法 c語言遞歸

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/105312.html

優秀程序員都應該學習的 GitHub 上開源的數據結構與算法項目

摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

cheukyin 2019-08-26 10:17 評論0 收藏0
JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0
JavaScript 數據結構與算法之美 - 非線性表中的樹、堆是干嘛用的？其數據結構是怎樣的？

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。非線性表中的樹堆是干嘛用的其數據結構是怎樣的希望大家帶著這兩個問題閱讀下文。其中，前中后序，表示的是節點與它的左右子樹節點遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想學好前端，先練好內功，內功不行，...

singerye 2019-08-26 10:09 評論0 收藏0
JavaScript 數據結構與算法之美 - 棧內存與堆內存、淺拷貝與深拷貝

摘要：棧內存與堆內存淺拷貝與深拷貝，可以說是前端程序員的內功，要知其然，知其所以然。棧內存與堆內存中的變量分為基本類型和引用類型。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言想寫好前端，先練好內功。棧內存與堆內存、淺拷貝與深拷貝，可以說是前端程序員的內功，要知其然，知其所以然。筆者寫的 JavaScrip...

dailybird 2019-08-23 18:26 評論0 收藏0
JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0