Javascript尾递归编程的实现

目录

• 尾递归编程思想
• 最容易的递归
• 运用缓存结果思想解决函数开销
• 迭代方法
• 尾递归实现
• 原理图解
• 关于Javascript没有实现尾递归优化
• trampoline实现

尾递归编程思想

递归是编程中必不可少的一环，在算法和工程上会经常使用，但是随着计算量的增大，函数堆栈会大量堆积上一函数上下文中的变量和方法，会导致主线程栈的空间不足而造成栈溢出错误，由于新的函数压入堆栈后，上一函数仍然在堆栈中未被释放，因此内存资源消耗会十分大，对性能也会有很大影响。

我们知道递归写起来确实方便，逻辑也容易理解，最简单的斐波那契数列问题，跳楼梯，一次只能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);
}

很明显上述递归没有任何优化，利用函数堆栈来实现对上一结果的保存作为下一结果的支撑，函数开销大。

运用缓存结果思想解决函数开销

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];
}

是解决了数据过大栈溢出问题了，不过也同时带来空间开销

迭代方法

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;
}

如果是复杂点的问题迭代法是比较难想出来的。但凡可以实现迭代处理的方法可以用尾递归实现，递归的实现更具有可读性和简洁性。

尾递归实现

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

原理图解

关于Javascript没有实现尾递归优化

Javascript由于某些原因，JavaScript引擎实现者认为特性不合理，以及各大厂商的权力纠纷问题，TC39提案仍未落实尾递归优化方案。

如果要实现JavaScript尾递归优化，需要采用蹦床函数辅助实现，才能实现和迭代一样避免栈溢出情况。

trampoline实现

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));

到此这篇关于Javascript尾递归编程的实现的文章就介绍到这了,更多相关Javascript尾递归内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！