I've seen several posts on generating a given fibonacci sequence, such as this one. However, I can't figure out how to generate the sequence (return an array) of fibonnaci numbers for a given n using recursion. What I have clearly doesn't work, but I really can't figure out how to do it otherwise.

var fibArray = function(n) {
    var f = [];
    n < 2 ? f.push(n) : f.push(fibArray(n-1) + fibArray(n-2));
    return f;
};

I've seen several posts on generating a given fibonacci sequence, such as this one. However, I can't figure out how to generate the sequence (return an array) of fibonnaci numbers for a given n using recursion. What I have clearly doesn't work, but I really can't figure out how to do it otherwise.

var fibArray = function(n) {
    var f = [];
    n < 2 ? f.push(n) : f.push(fibArray(n-1) + fibArray(n-2));
    return f;
};

• javascript
• arrays
• recursion
• fibonacci

• 4 Literally the first search result ~ How does the the fibonacci recursive function "work"? – Phil Commented Apr 5, 2016 at 0:39
• 1 thats not the same question,he wanted to return an array – omarjmh Commented Apr 5, 2016 at 0:51
• 2 @Phil not 100% sure, but this may have been a premature close, or wrong duplicate – omarjmh Commented Apr 5, 2016 at 0:53
• @Omarjmh was more thinking it could point OP in the right direction – Phil Commented Apr 5, 2016 at 1:02
• @Phil I get that, your call of course, I submitted an edit - before your last comment, I feel like its a unique enough problem, but of course I defer to you all! – omarjmh Commented Apr 5, 2016 at 1:05

3 Answers 3

A slightly modified version from the previous answer:

function fib(n) {
  if (n == 0) return [0]
  if (n == 1) return [0, 1]
  const arr = fib(n - 1)
  return [...arr, arr[n-1] + arr[n-2]]
}

console.log(fib(15))

Notice that you start each function call with an empty array and then only add 1 member to it. That won't work.

You have to add the new element to the array that was returned from the previous fib(n - 1) step. Like so:

function fib (n) {
    if (n < 2) {
        return [1];   
    }
    if (n < 3) {
        return [1, 1];
    }

    var a = fib(n - 1);
    a.push(a[n - 2] + a[n - 3]);
    return a;
};

The nth number appears on the position n - 1 on the array. That justifies the n - 2 = n - 1 - 1 and n - 3 = n - 2 - 1.

This is an option without spread operator and with an option to start the sequence when you want:

function fibonacciRecursion(amountNumbers = 4, sequence = [0, 1]) {
    if (amountNumbers > 0) {
        sequence.push(sequence[sequence.length - 1] + sequence[sequence.length - 2]);
        return fibonacciRecursion(amountNumbers - 1, sequence);
    }
    return sequence
}
    
console.log(fibonacciRecursion(10, [3,5]))