纯粹的递归版

/**
 * 单纯的进行递归操作效率及其低下，因为算法内部做了大量的重复计算，时间复杂度为O(2^n)
 */
function fibonacci(n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

带缓存的递归版

/**
 * 将计算好的结果缓存起来，这样可以避免重复计算，时间复杂度为O(n)
 */
const memory = [0, 1];
function fibonacci(n) {
    if (typeof memory[n] === 'number') {
        return memory[n];
    } else {
        const result = fibonacci(n - 1) + fibonacci(n - 2);
        memory[n] = result;
        return result;
    }
}

循环版

/**
 * 循环计算，时间复杂度为O(n)
 */ 
const memory = [0, 1];
function fibonacci(n) {
    if (n <= 1) {
        return memory[n];
    } else {
        let i = 2;
        while (i <= n) {
            memory[i] = memory[i - 1] + memory[i - 2];
            i++;
        }
        return memory[n];
    }
}