JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（八）遞歸

arashicage 發(fā)布于2019-08-26 14:04 / 2960人閱讀

摘要：在之前的文章中我們學(xué)習(xí)了幾種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，接下來(lái)我們先了解一下遞歸思想，為我們后面學(xué)習(xí)樹(shù)和圖奠定一定的基礎(chǔ)。而如果一直調(diào)用自己的話，最終會(huì)導(dǎo)致棧溢出從而導(dǎo)致程序崩潰，這是程序員不想發(fā)生的問(wèn)題之一。

在之前的文章中我們學(xué)習(xí)了幾種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，接下來(lái)我們先了解一下遞歸思想，為我們后面學(xué)習(xí)樹(shù)和圖奠定一定的基礎(chǔ)。

遞歸 理解遞歸

遞歸是一種解決問(wèn)題的方法。通俗點(diǎn)來(lái)講，其核心思想就是函數(shù)自己調(diào)用自己，或者間接調(diào)用自身。而如果一直調(diào)用自己的話，最終會(huì)導(dǎo)致棧溢出從而導(dǎo)致程序崩潰，這是程序員不想發(fā)生的問(wèn)題之一。那么要使用遞歸，就必須遵循的他的一些注意點(diǎn)。首先要注意的是，每個(gè)遞歸函數(shù)都有基線條件，也就是不再發(fā)生遞歸的停止點(diǎn)。還有，既然傳遞值或者函數(shù)到棧空間，那么我們就有好習(xí)慣，將不用的或者需要的空間進(jìn)行返回。也可以這樣理解，遞歸其實(shí)就是傳遞和歸還。下面一段簡(jiǎn)單的代碼進(jìn)行展示。

function understandRecursion(doIunderstandRecursion) {
  const recursionAnswer = confirm("Do you understand recursion?"); // function logic
  if (recursionAnswer === true) { // base case or stop point
    return true;
  }
  understandRecursion(recursionAnswer); // recursive call
}

understandRecursion(false);//continue
understandRecursion(false);//continue
understandRecursion(true);//stop

一些經(jīng)典遞歸算法 階乘

普通迭代實(shí)現(xiàn)

function factorialIterative(number) {
  if (number < 0) {
    return undefined;
  }
  let total = 1;
  for (let n = number; n > 1; n--) {
    total  = total * n;
  }
  return total;
}

遞歸實(shí)現(xiàn)

function factorial(n) {
    // console.trace();
    if (n === 1 || n === 0) {
      return 1;
    }
  return n * factorial(n - 1);
}

值得注意的是，由于操作系統(tǒng)和瀏覽器的不同，提供的棧空間不同，也就是棧溢出發(fā)生時(shí)函數(shù)的執(zhí)行次數(shù)不同，并且在ES6中提供的是尾調(diào)用優(yōu)化，函數(shù)內(nèi)最后一個(gè)操作是調(diào)用函數(shù)時(shí)，會(huì)通過(guò)跳轉(zhuǎn)指令jump而不是子程序調(diào)用，導(dǎo)致程序可以一直進(jìn)行。所以在這里，基線條件是萬(wàn)萬(wàn)不能忘了添加的。

斐波那契數(shù)列

迭代實(shí)現(xiàn)

function fibonacciIterative(n){
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) { // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

遞歸實(shí)現(xiàn)

function fibonacciIterative(n){
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) { // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

記憶化斐波那契數(shù)列

function fibonacciMemoization(n) {
  const memo = [0, 1];
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n];
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  };
  return fibonacci(n);
}

總結(jié)

迭代版本比遞歸版本快很多，但是遞歸版本更容易理解，需要的代碼通常更少。使用遞歸有些算法不用，因?yàn)槲舱{(diào)用優(yōu)化會(huì)造成多余的內(nèi)存消耗，甚至可能會(huì)被清除。