[数据结构与算法]算法题练习

斐波那契数列问题

该问题最传统的做法就是使用递归，但是如果递归的深度过大，就会导致栈溢出

动态规划法（最优解）

思路

将每次前两数之和存起来，便于下次直接使用，减少了内存压力。

示例

function fib(n) {
    let n1 = 0, n2 = 1, sum
    for(let i = 0; i < n; i++) {
        sum = (n1 + n2) % 1000000007
        n1 = n2
        n2 = sum
    }
    return n1
}

ES6尾调用优化

什么是尾调用优化

在ES5中，尾调用的实现是创建一个新的stack frame(栈帧)，将其推入调用栈中表示函数调用，因此每一个未用完的stack frame都会保存在内存中，当调用栈变得特别大时，程序就不好了

在ES6的严格模式下（非严格模式下时不受影响的），满足以下三个条件，尾调用不再创建新的stack frame，而是重用当前的stack frame

• 函数不是一个闭包
• 在函数内部，尾调用是最后一条语句
• 尾调用的结果作为函数值返回

什么是尾调用，就是外部函数的返回值是一个内部函数的返回值

'use strict';
function outerFunction() {
    return innerFunction() //尾调用
}

示例

var fib = function(n) {
    return fibImpl(n)
}
function fibImpl(n,a=0,b=1) {
    if(n === 0) {
        return a
    }
    return fibImpl(n-1,b,(a+b)%1000000007)
}