Числа Фибоначчи

Задача

Вычислите n-е число Фибоначчи. Покажите варианты: рекурсия с мемоизацией и итеративные подходы за O(1) по памяти.

Решение

Оптимальное решение (итеративное, O(n) время, O(1) память)

function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
 
    let prev = 0; // F(0)
    let curr = 1; // F(1)
 
    for (let i = 2; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
    }
 
    return curr;
}
 
// Примеры:
// fibonacci(0) → 0
// fibonacci(1) → 1
// fibonacci(6) → 8
// fibonacci(10) → 55

Итеративное через деструктуризацию (та же сложность)

function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
 
    let [prev, curr] = [0, 1];
 
    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }
 
    return curr;
}

Рекурсия с мемоизацией (O(n) память + стек вызовов)

function fibonacciMemo(n, memo = {}) {
    if (n < 0) return undefined;
    if (n === 0) return 0;
    if (n === 1) return 1;
    if (memo[n]) return memo[n];
 
    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

Замыкание + кеш (O(n) память)

const fibonacciMemo = (() => {
    const cache = { 0: 0, 1: 1 };
 
    return function fibonacci(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }
        cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return cache[n];
    };
})();
 
// Без мемоизации: fibonacci(40) → ~2 секунды (повторные вычисления)
// С мемоизацией: fibonacci(40) → мгновенно

См. также

• factorial
• memoize