摘要:專題系列第十八篇,講解遞歸和尾遞歸定義程序調用自身的編程技巧稱為遞歸。然而非尾調用函數,就會創建多個執行上下文壓入執行上下文棧。所以我們只用把階乘函數改造成一個尾遞歸形式,就可以避免創建那么多的執行上下文。
定義JavaScript 專題系列第十八篇,講解遞歸和尾遞歸
程序調用自身的編程技巧稱為遞歸(recursion)。
階乘以階乘為例:
function factorial(n) { if (n == 1) return n; return n * factorial(n - 1) } console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120
示意圖(圖片來自 wwww.penjee.com):
斐波那契數列在《JavaScript專題之函數記憶》中講到過的斐波那契數列也使用了遞歸:
function fibonacci(n){ return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2); } console.log(fibonacci(5)) // 1 1 2 3 5遞歸條件
從這兩個例子中,我們可以看出:
構成遞歸需具備邊界條件、遞歸前進段和遞歸返回段,當邊界條件不滿足時,遞歸前進,當邊界條件滿足時,遞歸返回。階乘中的 n == 1 和 斐波那契數列中的 n < 2 都是邊界條件。
總結一下遞歸的特點:
子問題須與原始問題為同樣的事,且更為簡單;
不能無限制地調用本身,須有個出口,化簡為非遞歸狀況處理。
了解這些特點可以幫助我們更好的編寫遞歸函數。
執行上下文棧在《JavaScript深入之執行上下文棧》中,我們知道:
當執行一個函數的時候,就會創建一個執行上下文,并且壓入執行上下文棧,當函數執行完畢的時候,就會將函數的執行上下文從棧中彈出。
試著對階乘函數分析執行的過程,我們會發現,JavaScript 會不停的創建執行上下文壓入執行上下文棧,對于內存而言,維護這么多的執行上下文也是一筆不小的開銷吶!那么,我們該如何優化呢?
答案就是尾調用。
尾調用尾調用,是指函數內部的最后一個動作是函數調用。該調用的返回值,直接返回給函數。
舉個例子:
// 尾調用 function f(x){ return g(x); }
然而
// 非尾調用 function f(x){ return g(x) + 1; }
并不是尾調用,因為 g(x) 的返回值還需要跟 1 進行計算后,f(x)才會返回值。
兩者又有什么區別呢?答案就是執行上下文棧的變化不一樣。
為了模擬執行上下文棧的行為,讓我們定義執行上下文棧是一個數組:
ECStack = [];
我們模擬下第一個尾調用函數執行時的執行上下文棧變化:
// 偽代碼 ECStack.push(functionContext); ECStack.pop(); ECStack.push( functionContext); ECStack.pop();
我們再來模擬一下第二個非尾調用函數執行時的執行上下文棧變化:
ECStack.push(functionContext); ECStack.push( functionContext); ECStack.pop(); ECStack.pop();
也就說尾調用函數執行時,雖然也調用了一個函數,但是因為原來的的函數執行完畢,執行上下文會被彈出,執行上下文棧中相當于只多壓入了一個執行上下文。然而非尾調用函數,就會創建多個執行上下文壓入執行上下文棧。
函數調用自身,稱為遞歸。如果尾調用自身,就稱為尾遞歸。
所以我們只用把階乘函數改造成一個尾遞歸形式,就可以避免創建那么多的執行上下文。但是我們該怎么做呢?
階乘函數優化我們需要做的就是把所有用到的內部變量改寫成函數的參數,以階乘函數為例:
function factorial(n, res) { if (n == 1) return res; return factorial2(n - 1, n * res) } console.log(factorial(4, 1)) // 24
然而這個很奇怪吶……我們計算 4 的階乘,結果函數要傳入 4 和 1,我就不能只傳入一個 4 嗎?
這個時候就要用到我們在《JavaScript專題之柯里化》中編寫的 curry 函數了:
var newFactorial = curry(factorial, _, 1) newFactorial(5) // 24應用
如果你看過 JavaScript 專題系列的文章,你會發現遞歸有著很多的應用。
作為專題系列的第十八篇,我們來盤點下之前的文章中都有哪些涉及到了遞歸:
1.《JavaScript 專題之數組扁平化》:
function flatten(arr) { return arr.reduce(function(prev, next){ return prev.concat(Array.isArray(next) ? flatten(next) : next) }, []) }
2.《JavaScript 專題之深淺拷貝》:
var deepCopy = function(obj) { if (typeof obj !== "object") return; var newObj = obj instanceof Array ? [] : {}; for (var key in obj) { if (obj.hasOwnProperty(key)) { newObj[key] = typeof obj[key] === "object" ? deepCopy(obj[key]) : obj[key]; } } return newObj; }
3.JavaScript 專題之從零實現 jQuery 的 extend:
// 非完整版本,完整版本請點擊查看具體的文章 function extend() { ... // 循環遍歷要復制的對象們 for (; i < length; i++) { // 獲取當前對象 options = arguments[i]; // 要求不能為空 避免extend(a,,b)這種情況 if (options != null) { for (name in options) { // 目標屬性值 src = target[name]; // 要復制的對象的屬性值 copy = options[name]; if (deep && copy && typeof copy == "object") { // 遞歸調用 target[name] = extend(deep, src, copy); } else if (copy !== undefined){ target[name] = copy; } } } } ... };
4.《JavaScript 專題之如何判斷兩個對象相等》:
// 非完整版本,完整版本請點擊查看具體的文章 // 屬于間接調用 function eq(a, b, aStack, bStack) { ... // 更復雜的對象使用 deepEq 函數進行深度比較 return deepEq(a, b, aStack, bStack); }; function deepEq(a, b, aStack, bStack) { ... // 數組判斷 if (areArrays) { length = a.length; if (length !== b.length) return false; while (length--) { if (!eq(a[length], b[length], aStack, bStack)) return false; } } // 對象判斷 else { var keys = Object.keys(a), key; length = keys.length; if (Object.keys(b).length !== length) return false; while (length--) { key = keys[length]; if (!(b.hasOwnProperty(key) && eq(a[key], b[key], aStack, bStack))) return false; } } }
5.《JavaScript 專題之函數柯里化》:
// 非完整版本,完整版本請點擊查看具體的文章 function curry(fn, args) { length = fn.length; args = args || []; return function() { var _args = args.slice(0), arg, i; for (i = 0; i < arguments.length; i++) { arg = arguments[i]; _args.push(arg); } if (_args.length < length) { return curry.call(this, fn, _args); } else { return fn.apply(this, _args); } } }寫在最后
遞歸的內容遠不止這些,比如還有漢諾塔、二叉樹遍歷等遞歸場景,本篇就不過多展開,真希望未來能寫個算法系列。
專題系列JavaScript專題系列目錄地址:https://github.com/mqyqingfeng/Blog。
JavaScript專題系列預計寫二十篇左右,主要研究日常開發中一些功能點的實現,比如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯里、遞歸、亂序、排序等,特點是研(chao)究(xi) underscore 和 jQuery 的實現方式。
如果有錯誤或者不嚴謹的地方,請務必給予指正,十分感謝。如果喜歡或者有所啟發,歡迎 star,對作者也是一種鼓勵。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/91753.html
摘要:專題系列共計篇,主要研究日常開發中一些功能點的實現,比如防抖節流去重類型判斷拷貝最值扁平柯里遞歸亂序排序等,特點是研究專題之函數組合專題系列第十六篇,講解函數組合,并且使用柯里化和函數組合實現模式需求我們需要寫一個函數,輸入,返回。 JavaScript 專題之從零實現 jQuery 的 extend JavaScritp 專題系列第七篇,講解如何從零實現一個 jQuery 的 ext...
摘要:寫在前面專題系列是我寫的第二個系列,第一個系列是深入系列。專題系列自月日發布第一篇文章,到月日發布最后一篇,感謝各位朋友的收藏點贊,鼓勵指正。 寫在前面 JavaScript 專題系列是我寫的第二個系列,第一個系列是 JavaScript 深入系列。 JavaScript 專題系列共計 20 篇,主要研究日常開發中一些功能點的實現,比如防抖、節流、去重、類型判斷、拷貝、最值、扁平、柯里...
摘要:專題系列第九篇,講解如何實現數組的扁平化,并解析的源碼扁平化數組的扁平化,就是將一個嵌套多層的數組嵌套可以是任何層數轉換為只有一層的數組。 JavaScript 專題系列第九篇,講解如何實現數組的扁平化,并解析 underscore 的 _.flatten 源碼 扁平化 數組的扁平化,就是將一個嵌套多層的數組 array (嵌套可以是任何層數)轉換為只有一層的數組。 舉個例子,假設有個...
摘要:不過的實現中,多了很多細節上的判斷,比如第一個參數是否是布爾值,是否是一個對象,不傳參數時的默認值等。 JavaScritp 專題系列第七篇,講解如何從零實現一個 jQuery 的 extend 函數 前言 jQuery 的 extend 是 jQuery 中應用非常多的一個函數,今天我們一邊看 jQuery 的 extend 的特性,一邊實現一個 extend! extend 基本用...
摘要:專題系列第六篇,講解深淺拷貝的技巧和以及實現深淺拷貝的思路前言拷貝也是面試經典吶數組的淺拷貝如果是數組,我們可以利用數組的一些方法比如返回一個新數組的特性來實現拷貝。所以我們可以看出使用和是一種淺拷貝。 JavaScript 專題系列第六篇,講解深淺拷貝的技巧和以及實現深淺拷貝的思路 前言 拷貝也是面試經典吶! 數組的淺拷貝 如果是數組,我們可以利用數組的一些方法比如:slice、co...
閱讀 3118·2021-11-15 18:14
閱讀 1773·2021-09-22 10:51
閱讀 3282·2021-09-09 09:34
閱讀 3504·2021-09-06 15:02
閱讀 1013·2021-09-01 11:40
閱讀 3186·2019-08-30 13:58
閱讀 2523·2019-08-30 11:04
閱讀 1081·2019-08-28 18:31