快捷導(dǎo)航

Javascript尾遞歸編程的實(shí)現(xiàn)

更新時(shí)間：2022年06月20日 10:17:05 作者：Jimmy0_0

本文主要介紹了Javascript尾遞歸編程的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

尾遞歸編程思想

遞歸是編程中必不可少的一環(huán)，在算法和工程上會(huì)經(jīng)常使用，但是隨著計(jì)算量的增大，函數(shù)堆棧會(huì)大量堆積上一函數(shù)上下文中的變量和方法，會(huì)導(dǎo)致主線程棧的空間不足而造成棧溢出錯(cuò)誤，由于新的函數(shù)壓入堆棧后，上一函數(shù)仍然在堆棧中未被釋放，因此內(nèi)存資源消耗會(huì)十分大，對(duì)性能也會(huì)有很大影響。

我們知道遞歸寫起來確實(shí)方便，邏輯也容易理解，最簡單的斐波那契數(shù)列問題，跳樓梯，一次只能1步或2步，跳n格有多少種方法

最容易的遞歸

// 限制條件 countOfStep>0
function jump(countOfStep) {
    if (countOfStep <= 0) return 0;
    function jumpRecursive(innerCountOfStep) {
        if (innerCountOfStep < 0) return 0;
        if (innerCountOfStep === 1 || innerCountOfStep === 0) return 1;
        return jumpRecursive(innerCountOfStep - 1) + jumpRecursive(innerCountOfStep - 2);
    }
    return jumpRecursive(countOfStep);
}

很明顯上述遞歸沒有任何優(yōu)化，利用函數(shù)堆棧來實(shí)現(xiàn)對(duì)上一結(jié)果的保存作為下一結(jié)果的支撐，函數(shù)開銷大。

運(yùn)用緩存結(jié)果思想解決函數(shù)開銷

function jumpWithoutFuncCost(countOfStep) {
    if(countOfStep<=0) return 0;
    const saves = new Array(countOfStep + 1).fill(0);
    [saves[0], saves[1]] = [1, 1];
    for (let i = 2; i <= countOfStep; i++) {
        saves[i] = saves[i - 1] + saves[i - 2];
    }
    return saves[countOfStep];
}

是解決了數(shù)據(jù)過大棧溢出問題了，不過也同時(shí)帶來空間開銷

迭代方法

function jumpIteritive(countOfStep) {
    if(countOfStep<=0) return 0;
    let [prefix, suffix] = [1, 1];
    for (let i = 2; i <= countOfStep; i++) {
        let temp = suffix;
        suffix += prefix;
        prefix = temp;
    }
    return suffix;
}

如果是復(fù)雜點(diǎn)的問題迭代法是比較難想出來的。但凡可以實(shí)現(xiàn)迭代處理的方法可以用尾遞歸實(shí)現(xiàn)，遞歸的實(shí)現(xiàn)更具有可讀性和簡潔性。

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

function jumpTailRecursive(countOfStep, prev = 1, next = 1) {
    if(countOfStep<=0) return 0;
    if (countOfStep === 1) return next;
    return jumpTailRecursive(--countOfStep, next, prev + next);
}

原理圖解

關(guān)于Javascript沒有實(shí)現(xiàn)尾遞歸優(yōu)化

Javascript由于某些原因，JavaScript引擎實(shí)現(xiàn)者認(rèn)為特性不合理，以及各大廠商的權(quán)力糾紛問題，TC39提案仍未落實(shí)尾遞歸優(yōu)化方案。

如果要實(shí)現(xiàn)JavaScript尾遞歸優(yōu)化，需要采用蹦床函數(shù)輔助實(shí)現(xiàn)，才能實(shí)現(xiàn)和迭代一樣避免棧溢出情況。

trampoline實(shí)現(xiàn)

function jumpTailRecursiveTrampolined(countOfStep, prev = 1, next = 1) {
    if (countOfStep <= 0) return 0;
    if (countOfStep === 1) return next;
    return () => jumpTailRecursiveTrampolined(--countOfStep, next, prev + next);
}

function trampoline(F){
    return function(...args){
        F = F.bind(this, ...args);
        while (F instanceof Function) {
            F = F();
        }
        return F;
    }
}

const uniformLog = (element) => console.log(JSON.stringify(element, undefined, 4));
uniformLog(trampoline(jumpTailRecursiveTrampolined)(3));

到此這篇關(guān)于Javascript尾遞歸編程的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Javascript尾遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: