Multiple Fibonacci Implementations (v5)

/**
 * 尾递归版
 * [NodeJS] 爆栈的临界值7390左右，耗时1ms左右（仍然发生爆栈错误说明还是保留了栈，并未完全去栈化）。
 *   其性能明显比非尾递归调用要更好，但是跟迭代版的远不在一个数量级。
 */
//const NonPrimitiveModeNum = 100;
let fb_tail_call_count = 0
// (5, 1, 1) , (4, 1, 2), (3, 2, 3), (2, 3, 5), (1, 3, 5), (0, 5, 8)
function fb_tail_call(n, a=1, b=1){
    fb_tail_call_count++
    if(n < 1){
        return a
    }
    return fb_tail_call(n-1, b, a+b) 
}
fb_tail_call(NonPrimitiveModeNum);

/**
 * 递归改迭代（循环）版
 * 运行结果：
 * [NodeJS] 没有使用栈，纯粹计算耗时，在n=5kw时耗时才达到1s的级别，综合性能最优。
 */ 
//const NonPrimitiveModeNum = 100;
function fb_iterator(n){
    if(n < 2){
        return 1
    }
    let results = [1, 1]
    for(let i = 2; i<n+1; i++){
        results[i] = results[i-2] + results[i-1]
    }
    return results[n]
}

fb_iterator(NonPrimitiveModeNum);

/**
 * 普通递归+缓存优化版
 * 运行结果：
 * [NodeJS] 爆栈的临界值是n在 `[10471-10473]` 左右,time cost 10ms 上下
 */
// const NonPrimitiveModeNum = 100;
let fb_cachelize_call_count = 0
const cacheMap = new Map()
function fb_cachelize(n){
    fb_cachelize_call_count++
    if(n < 2){
        return 1 
    }
    if(cacheMap.has(n)){
        return cacheMap.get(n)
    }else{
        let res = fb_cachelize(n-1) + fb_cachelize(n-2)
        cacheMap.set(n, res)
        return res
    }
}
fb_cachelize(NonPrimitiveModeNum);