How can I recursively generate an Array of the Fibonacci sequence?

Question

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;
};

Literally the first search result ~ [How does the the fibonacci recursive function "work"?](http://stackoverflow.com/questions/8845154/how-does-the-the-fibonacci-recursive-function-work) — Phil, Apr 05 '16 at 00:39
@Phil not 100% sure, but this may have been a premature close, or wrong duplicate — omarjmh, Apr 05 '16 at 00:53
@Omarjmh was more thinking it could point OP in the right direction — Phil, Apr 05 '16 at 01: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, Apr 05 '16 at 01:05
@Phil just to be clear I assumed he wants to create and return the array recursively, if its just pushing to the array recursively and returning that array, yes this is a dupe. — omarjmh, Apr 05 '16 at 01:07
@Phil I know how the sequence works, I don't know how to make an array out of it recursively. — TheRealFakeNews, Apr 05 '16 at 01:46

Damjan Pavlica · Answer 1 · 2018-07-03T12:49:26.150

13

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))

edited Jul 03 '18 at 12:49

answered May 10 '18 at 13:25

Damjan Pavlica

31,277
10
71
76

SlySherZ · Accepted Answer · 2016-04-05T01:49:32.810

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.

score 0 · Answer 3 · edited Jul 11 '21 at 12:48

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]))

How can I recursively generate an Array of the Fibonacci sequence?

3 Answers3