CODEWITHSUNDEEP
javascriptrecursionfibonacci
Joji
Joji

Reputation: 5625

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

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.

Upvotes: 2

Views: 2953

Answers (4)

Mwangi Njuguna
Mwangi Njuguna

Reputation: 75

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

Upvotes: -1

georg
georg

Reputation: 214959

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!

Upvotes: 0

Jonas Wilms
Jonas Wilms

Reputation: 138277

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

Upvotes: 5

tevemadar
tevemadar

Reputation: 13195

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

Upvotes: 0

Related Questions