Generate Fibonacci Sequence

Problem Statement

Solution 1: Fibonacci Sequence using recursion

// Function to generate a list of Fibonacci numbers up to a certain count
function generateFibonacciSequence(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacci(i));
    }
    return sequence;
}

// Recursive function to calculate the nth Fibonacci number
function fibonacci(n) {
    // Base cases
    if (n <= 0) return 0;
    if (n === 1) return 1;

    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
} 

const n1 = 5;
generateFibonacciSequence(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequence(n2);  //output: [] 

Solution 2: Iterative Approach

function generateFibonacciSequenceIterative(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacciIterative(i));
    }
    return sequence;
}

function fibonacciIterative(n) {
    if (n <= 0) return 0;
    if (n === 1) return 1;

    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        const temp = a + b;
        a = b;
        b = temp;
    }
    return b;
} 

const n1 = 5;
generateFibonacciSequenceIterative(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceIterative(n2);  //output: [] 

Solution 3: Memoization Approach

function generateFibonacciSequenceMemo(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacciMemo(i));
    }
    return sequence;
}

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

const n1 = 5;
generateFibonacciSequenceMemo(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceMemo(n2);  //output: [] 

Solution 4: Matrix Exponentiation

function generateFibonacciSequenceMatrix(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacciMatrix(i));
    }
    return sequence;
}

function fibonacciMatrix(n) {
    if (n <= 1) return n;
    const result = matrixPower([1, 1, 1, 0], n - 1);
    return result[0];
}

function matrixPower(matrix, n) {
    if (n === 1) return matrix;
    if (n % 2 === 0) return matrixPower(matrixMultiply(matrix, matrix), n / 2);
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
}

function matrixMultiply(a, b) {
    return [
        a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3],
        a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3]
    ];
} 

const n1 = 5;
generateFibonacciSequenceMatrix(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceMatrix(n2);  //output: [] 

Solution 5: Binet Formula

function generateFibonacciSequenceBinet(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacciBinet(i));
    }
    return sequence;
}

function fibonacciBinet(n) {
    const sqrt5 = Math.sqrt(5);
    const phi = (1 + sqrt5) / 2;
    const psi = (1 - sqrt5) / 2;
    return Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / sqrt5);
} 

const n1 = 5;
generateFibonacciSequenceBinet(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceBinet(n2);  //output: [] 

Solution 6: Generator Function

function generateFibonacciSequenceGenerator(count) {
    const sequence = [];
    const gen = fibonacciGenerator();
    for (let i = 0; i < count; i++) {
        sequence.push(gen.next().value);
    }
    return sequence;
}

function* fibonacciGenerator() {
    let a = 0, b = 1;
    while (true) {
        yield a;
        [a, b] = [b, a + b];
    }
} 

const n1 = 5;
generateFibonacciSequenceGenerator(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceGenerator(n2);  //output: [] 

Solution 7: Dynamic Programming (Bottom-Up Approach)

function generateFibonacciSequenceDynamic(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacciDynamic(i));
    }
    return sequence;
}

function fibonacciDynamic(n) {
    if (n <= 0) return 0;
    if (n === 1) return 1;

    const dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
} 

const n1 = 5;
generateFibonacciSequenceDynamic(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceDynamic(n2);  //output: [] 

Solution 8: Using an Array

function generateFibonacciSequenceArray(count) {
    if (count <= 0) return [];
    if (count === 1) return [0];

    const sequence = [0, 1];
    for (let i = 2; i < count; i++) {
        sequence[i] = sequence[i - 1] + sequence[i - 2];
    }
    return sequence;
} 

const n1 = 5;
generateFibonacciSequenceArray(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceArray(n2);  //output: [] 

Solution 9: Using a Recurrence Relation

function generateFibonacciSequenceRecurrence(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacciRecurrence(i));
    }
    return sequence;
}

function fibonacciRecurrence(n) {
    if (n <= 0) return 0;
    if (n === 1) return 1;
    const fibs = [0, 1];
    for (let i = 2; i <= n; i++) {
        fibs[i] = fibs[i - 1] + fibs[i - 2];
    }
    return fibs[n];
} 

const n1 = 5;
generateFibonacciSequenceRecurrence(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceRecurrence(n2);  //output: [] 

Solution 10: Fibonacci Sequence Using Streams (Functional Programming)

function generateFibonacciSequenceStream(count) {
    const sequence = [];
    const stream = fibonacciStream();
    for (let i = 0; i < count; i++) {
        sequence.push(stream.next().value);
    }
    return sequence;
}

function fibonacciStream() {
    return (function* () {
        let a = 0, b = 1;
        while (true) {
            yield a;
            [a, b] = [b, a + b];
        }
    })();
} 

const n1 = 5;
generateFibonacciSequenceStream(n1);  //output: [0,1,1,2,3] 

const n2 = 0;
generateFibonacciSequenceStream(n2);  //output: [] 

More Problems Solutions