Fibonacci recursive function with an output of the array of the sequence in JavaScript

Question

Hi I was trying to come up with a function to return a fibonacci sequence, that is an array not the usual last n-th fibonacci number.

function fib(n,arr=[0]) {
  if (n===0||n===1) {
    arr.push(n)
    return arr;
  }
  let arr2 = fib(n-2);
  let arr1 = fib(n-1);
  arr1.push(arr2[arr2.length-1]+arr1[arr1.length-1]);
  return arr1;
}

it works fine but I am not happy with the hard coded arr=[0] here. I tried to put arr=[] instead but the sequence I ended up getting excluded the first 0 entries in the array which should've been there.

I am sure there's better approaches to solve this.

P.S: I want to solve this using a recursive approach and I know it has a poor exponential time complexity but I just wanted to pratice my recursive programming skills.

Just as a note: one can certainly overdo avoiding hard coding values. The problem with hard coded values is that they make code less readable and less flexible, but 1's and 0's often don't suffer from these negative side affects. — MyiEye
– MyiEye, Commented Mar 17, 2018 at 20:43

Jonas Wilms · Accepted Answer · 2018-03-17 21:38:17Z

5

  let arr2 = fib(n-2);
  let arr1 = fib(n-1);

You build up two arrays for each step, so you build up n! arrays... Instead just use one recursive call, e.g.:

 function fibonacci(n){
   if(n <= 2)
      return [0, 1].slice(0, n);
   const res = fibonacci(n - 1);
   res.push(res[res.length - 1] + res[res.length - 2])
   return res;
 }

But do you really need recursion?:

 function fibonacci(n){
   const arr = [0, 1].slice(0 , n);
   for(let i = 2; i < n; i++)
     arr[i] = arr[i - 1] + arr[i - 2];
   return arr;
 }

edited Mar 17, 2018 at 21:38

answered Mar 17, 2018 at 20:43

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

pwolaq Over a year ago

fibonacci(1) is not [0,1,1], your code returns wrong values

Joji Over a year ago

yea I know that iterative approach. I used recurssion just for practice. thanks.

scaryguy Over a year ago

Why do you use slice at this line? return [0, 1].slice(0, n); at the Recursive version? Without slice it exactly gives the same result? return [0, 1]

Jonas Wilms Over a year ago

@scaryguy nope, for fibonacci(1) it would return the wrong result

tevemadar · Accepted Answer · 2018-03-17 21:13:36Z

0

Not my proudest code, but has array+recursion. Works fine with n>=2 (will not return [1]):

function fibo(n){
  var ret=[1,1];
  function recurs(n){
    if(!ret[n-1])recurs(n-1);
    //if(!ret[n-2])recurs(n-2); // it is not necessary in fact
    ret[n]=ret[n-1]+ret[n-2];
  }
  if(n>2)recurs(n-1);
  return ret;
}
console.log(fibo(2).join());
console.log(fibo(15).join());

answered Mar 17, 2018 at 21:13

tevemadar

13.3k3 gold badges27 silver badges63 bronze badges

1 Comment

tevemadar Over a year ago

@ZhenghaoHe in terms of Fibonacci-generation it would be iterative. In fact, this one also builds the list iteratively, that ret[n]=... line could be a simple ret.push(...) and would provide the exact same result. So the "recursion" directly replaces a simple for loop, which is not something I would be proud of. The only "plus" part is that it builds a single list only.

georg · Accepted Answer · 2018-03-17 22:07:02Z

A recursive fibonacci is easy, but how about making it tail-recursive?

let fib = n => fib2(2, n, [0, 1]);
let fib2 = (k, n, a) => k >= n ? a :
    fib2(k + 1, n, a.concat(a[k - 1] + a[k - 2]));

If you're a happy user of the Safari browser, whose JS engine already implements the ES6 tail call spec, you can test it with this snippet (warning: might take significant time or exhaust the memory!)

'use strict';

const BIG = 1e5;


let fibNaive = n => {
    if (n <= 2)
        return [0, 1].slice(0, n);
    const res = fibNaive(n - 1);
    res.push(res[res.length - 1] + res[res.length - 2])
    return res;
};

try {
    console.log('naive', fibNaive(BIG).slice(0, 100));
} catch(e) {
    console.log('naive', e.message) // RangeError: Maximum call stack size exceeded.
}


let fibCool = n => fib2(2, n, [0, 1]);
let fib2 = (k, n, a) => k >= n ? a :
    fib2(k + 1, n, a.concat(a[k - 1] + a[k - 2]));

console.log('cool', fibCool(BIG).slice(0, 100)) // works!

Mwangi Njuguna · Accepted Answer · 2018-03-18 06:23:38Z

-1

var fib = function(n) {
  if (n === 1) {
    return [0, 1];
  } else {
    var arr = fib(n - 1);
    arr.push(arr[arr.length - 1] + arr[arr.length - 2]);
    return arr;
  }
};

console.log(fib(8));

edited Mar 18, 2018 at 6:23

answered Mar 17, 2018 at 20:47

Mwangi Njuguna

752 silver badges10 bronze badges

1 Comment

Joji Over a year ago

did you really look at my question? of course I know there is this good old solution. but I wanted to output the array of the sequence not the value of the n-th fibonacci value

Collectives™ on Stack Overflow

Fibonacci recursive function with an output of the array of the sequence in JavaScript

4 Answers 4

4 Comments

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related