In this problem, you are required to write a JavaScript function that generates the Fibonacci sequence using recursion. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Specifically, the sequence is defined as follows:
F(0) = 0
F(1) = 1
For n > 1: F(n) = F(n - 1) + F(n - 2)
Input: n = 5
Output: [0,1,1,2,3]
Input: n = 0
Output: []
// 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: []
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: []
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: []
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: []
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: []
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: []
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: []
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: []
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: []
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: []