Recursion with fibonacci

JavaScript
#1

Tell us what’s happening:
Describe your issue in detail here.
ok so, im like 95% certain my code works but it times out the test. am i making a mistake or is it too memory heavy?

  **Your code so far**


function sumFibs(num) {
var result = 0
function fibonacci(num) {
  if (num < 1) {
    return 0
  }
  if (num === 1) {
    return 1
  }
  return fibonacci(num - 1) + fibonacci(num - 2)
   
 }
 for(var i = 0; i <= num; i++) {
   if (fibonacci(i) % 2 === 1 && fibonacci(i) < num) {
       result += fibonacci(i)
   }
 }
  return result
}
sumFibs(4);

  **Your browser information:**

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/90.0.4430.212 Safari/537.36

Challenge: Sum All Odd Fibonacci Numbers

Link to the challenge:

#2

Recursion is one of the worst ways to make Fibonacci numbers when it comes to performance. You are better off creating the Fibs in a loop and adding in the odd ones.

#3

Fibonacci number is probably THE example we use to tell how recursion gets really screwed, because you end up computing the same number over and over and over. To get Fib(N), you call Fib(N-1) and Fib(N-2). But Fib(N-1) calls Fib(N-2) and Fib(N-3). Fib(N-2) calls Fib(N-3) and Fib(N-4) …

In addition, you’re making it even worse with this

 if (fibonacci(i) % 2 === 1 && fibonacci(i) < num) {
       result += fibonacci(i)
   }

You’re calling Fib(i) 3 times for each I and each call is very expensive. For a small n, if you change it to

const fib = fibonacci(i)
 if (fib % 2 === 1 && fib < num) {
       result += fib
   }

you might get an answer (provided that the recursive function is correct).

Lastly, there are techniques to implement fibonacci recursively without incurring the recompuation of the same value, but that’s another story.

1 Like
#4

In some ways it is a shame that Fibonacci is one of the canonical examples of recursion given the poor performance, but on the other hand, the conversation that it starts about performance is interesting.

#5 
function sumFibs(num) {
  var result = 0

  function fibonacci(num) {

  if (num < 1) {
    return 0
  }

  if (num === 1) {
    return 1
  }

  return fibonacci(num - 1) + fibonacci(num - 2)
    
  }

  //i can start at 1

  //i <= num is not the condition on which you want to stop
  //that would mean you are calling
  //fibonacci(4000000) which would be an impossibly 
  //big number, and example would be:
  //fibonacci(100) = 354,224,848,179,261,915,075
  //which cannot be shown by normal ints in JS
  for(var i = 0; i <= num; i++) {
    
    //you should save the return value in a 
    //variable rather than calling the function
    //3 times
    if (fibonacci(i) % 2 === 1 && fibonacci(i) < num) {
        result += fibonacci(i)
    }

  }

  return result
}
sumFibs(4);

This advice won’t make you pass the test as I don’t think your recursive function is performant enough even with those changes, but I did get the test to pass by implementing dynamic programing to your recursive function, and it only requires a small change, and I’d be glad to help you with that rout if you want to keep your recursive approach.

1 Like
#6

I find dynamic programming interesting and I’ve used it with recursion a few times myself in some certain cases, but really people need to stop jumping to recursion so much.

In this case, the memory allocation will slow you down for a dynamic approach, and you really only need to know two Fib values at a time.

If a fixed length loop will get the job done, (like in this problem) you almost certainly should not use recursion.

#7

I would agree that in JavaScript recursion probably is not the best choice due to it not implementing tail call optimization.

I did do some testing for speed to see what the fastest approach would be and I found that dynamic programming made it markedly faster.

This is the time my functions took in nano seconds:

dynamicProgrammingMemoization: 136713n

dynamicProgrammingTabulation: 90719n

recursiveFib: 170544687n

iterationFib: 306652n

The functions all return the fib number at a certain spot. The memoization function use recursion whereas the tabulation use iteration.

I don’t know much about memory allocation so I cannot speak on to what effects it may have.

1 Like
#8

I’m suspicious of your implementation using raw loops.

function sumOddFibs(sum) {
  let sum = 0;
  let f0 = 1;
  let f1 = 1;
  while (f1 <= num) {
    if (f1 % 2) sum += f1;
    [f0, f1] = [f1, f0 + f1];
 }
  return sum;
}

Or something like that. Only 3 values to store.

If you use any of the Fibs more than once, then dynamic programming is the way to go. But if you only need each one once, then a raw loops will be fastest. Both dynamic programming and a raw loop will have the mininum number of additions, but dynamic programming will have memory higher memory usage. Performance is driven by memory access as much as floating point operations.

If it’s a race to compute a specific Fib the fastest, then I think fast doubling is the best approach in general?

https://www.nayuki.io/page/fast-fibonacci-algorithms

#9 

function sumOddFibs(num) {
    let sum = 0;
    let f0 = 0;
    let f1 = 1;
    while (f1 <= num) {
      if (f1 % 2) sum += f1;
      [f0, f1] = [f1, f0 + f1];
   }
    return sum;
  }

const start5 = process.hrtime.bigint()

for (let i = 0; i < 20; i++) sumOddFibs(4000000);

const end5 = process.hrtime.bigint()

console.log('sumOddFibs:', end5 - start5);

function sumFibs(num) {
    if (num < 2) return 1;
  
    let sum = 2;
  
    const seq = [1,1];
  
    let i = 2
  
    while (seq[i - 1] <= num) {
      seq[i] = seq[i - 1] + seq[i - 2];
      if (seq[i] % 2 && seq[i] <= num) {
        sum += seq[i];
      }
      i++;
    }
    return sum
  }

  const start6 = process.hrtime.bigint()

for (let i = 0; i < 20; i++) sumFibs(4000000);

const end6 = process.hrtime.bigint()

console.log('sumFibs:', end6 - start6);

These are the respective times in nanoseconds:

sumOddFibs: 925941n

sumFibs: 118169n

sumOddFibs: 923842n

sumFibs: 113974n

I ran it twice. I had to make a function as my examples earlier were simply designed to find a fib number, not not what the lesson was asking.

My function sumFibs uses tabulation so there is no recursion in this, but it is also more similar to your code.

I had to edit your code as when I first copied it, it had some typos so please correct me if you feel I edited improperly.

1 Like
#10

I’m not sure that Javascript is actually recomputing the fibs in the second function. If I understand correctly what ends up happening inside of the JS engine, you are effectively only building your large seq array once and then referencing it in later calls, making this an unfair comparison.

Profiling Javascript is annoyingly difficult.

Dynamically creating an array is expensive. There can’t be a free lunch here.

This shows what I meant where dynamic programming will be faster if you need to store and reuse the values.

#11

Fair enough, that’s implementation dependent and I doubt it’s caching that array that’s instantiated within the function, but just for posterity’s I ran them a few time’s with a singular call each, since process.hrtime is accurate enough to see at least a slight difference:

sumOddFibs(4000000);
sumFibs(4000000);

// First run
sumOddFibs: 105750n
sumFibs: 87915n

// Second
sumOddFibs: 59364n
sumFibs: 49565n

// Third
sumOddFibs: 59250n
sumFibs: 49120n

// Fourth
sumOddFibs: 58960n
sumFibs: 48302n

The dynamic programming approach is slow and takes up more space in comparison to methods like matrix exponentiation, but it’s certainly not slower or comparable to regular recursion, or other naive approaches to the problem.

The general reason your implementation is not as performant, as far as I can tell is because there are actually more O(1) assignments going on, twice as many, due to the need to reassign the two variables you keep in memory over and over, whereas I only need to make one assignment to the end of the array.

1 Like
#12

I am not sold on the idea that two assignments explains the difference.

I get different results when I time things:

const performance = require('perf_hooks').performance;

// ---------------------------------------------------
// Recursive variant
// ---------------------------------------------------
function sumFibsRecursive(num) {
  function fibs(i) {
    if (i == 1 || i == 2) return 1;
    return fibs(i-1) + fibs(i-2);
  }
  let sum = 2;
  let i = 3;
  let fn = fibs(i);
  while (fn <= num) {
    if (fn % 2) sum += fn;
    i++;
    fn = fibs(i);
  }
  return sum;
}

// ---------------------------------------------------
// Store two variant
// ---------------------------------------------------
function sumFibsTwo(num) {
  let sum = 2;
  let f0 = 1;
  let f1 = 2;
  while (f1 <= num) {
    if (f1 % 2) sum += f1;
    f1 = f0 + f1;
    f0 = f1 - f0;
  }
  return sum;
}

// ---------------------------------------------------
// Store two variant
// ---------------------------------------------------
function sumFibsDestructure(num) {
  let sum = 2;
  let f0 = 1;
  let f1 = 2;
  while (f1 <= num) {
    if (f1 % 2) sum += f1;
    f1 = f0 + f1;
    f0 = f1 - f0;
  }
  return sum;
}

// ---------------------------------------------------
// Store all variant
// ---------------------------------------------------
function sumFibsAll(num) {
  let sum = 2;
  const fn = [1,1];
  let i = 2
  while (fn[i - 1] <= num) {
    fn[i] = fn[i - 1] + fn[i - 2];
    if (fn[i] % 2 && fn[i] <= num) {
      sum += fn[i];
    }
    i++;
  }
  return sum
  }

// ---------------------------------------------------
// Store all variant, improved
// ---------------------------------------------------
function sumFibsAllFast(num) {
  let sum = 2;
  let fn = [1, 1, 2];
  let i = 2;
  while (fn[i] <= num) {
    if (fn[i] % 2) sum += fn[i];
    fn[i+1] = fn[i] + fn[i-1];
    i++;
  }
  return sum;
}

// ---------------------------------------------------
// Test cases
// ---------------------------------------------------
const numVariants = 5;
const variants = [
  sumFibsRecursive,
  sumFibsTwo,
  sumFibsDestructure,
  sumFibsAll,
  sumFibsAllFast,
  ];
const variantNames = [
  "Recursion, no tricks",
  "Store current two values",
  "Store current two values, with destructuring",
  "Store entire array",
  "Store entire array, reduced OPs",
]

// ---------------------------------------------------
// Timing function
// ---------------------------------------------------
function timeMe(func, num) {
  const t0 = performance.now();
  // Capturing and returning result, prevents JS from
  //  optimizing out parts of the code
  const result = func(num);
  const t1 = performance.now();

  return {time: t1-t0, result: result};
}

// ---------------------------------------------------
// Multiple test runs
// ---------------------------------------------------
const numCases = 8;
for (let c = 0; c < numCases; c++) {
  let sum = 0;
  const numRuns = 50;
  let times = [[], [], [], [], []];
  const testNum = 20000*(2**c);

  // Summary
  console.log();
  console.log("Test case " + c);
  console.log("  - Test number:");
  console.log("    " + testNum);
  console.log("  - Number runs:");
  console.log("    " + numRuns);

  // Call once and throw away result
  for (let i = 0; i < numVariants; i++) {
    timeMe(variants[i], testNum);
  }

  // Time multiple times
  for (let i = 0; i < numRuns; i++) {
    // Each variant
    for (let j = 0; j < numVariants; j++) {
      let {time, result} = timeMe(variants[j], testNum);
      sum += result;
      times[j][i] = time;
    }
  }
  console.log("  - Validity check:");
  console.log("    " +
    (sum === numRuns*numVariants*sumFibsDestructure(testNum) ? "Valid Runs" : "Invalid Runs"));

  // Output timing data
  for (let i = 0; i < numVariants; i++) {
    // Compute stats
    const minTime = Math.min(...times[i]);
    const maxTime = Math.max(...times[i]);
    const avgTime = times[i].reduce((sum, item) => sum + item, 0) / numRuns;
    const variance = times[i].reduce((sumSqDiff, item) => sumSqDiff + (avgTime - item)**2, 0) / numRuns;
    const stdDev = Math.sqrt(variance);

    // Output
    console.log();
    console.log("  - Variant: " + variantNames[i]);
    console.log("    Statistics:");
    console.log("      Average Time       : " + avgTime);
    console.log("      Minimum Time       : " + minTime);
    console.log("      Maximum Time       : " + maxTime);
    console.log("      Standard Deviation : " + stdDev);
    console.log("      Variance           : " + variance);
  }
}

I really don’t know what is happening in your timing case above. I get the same results, but those results don’t make any sense to me.

  1. I threw away the first timing (usually a garbage measure because it includes initializing other parts of JS)
  2. I switched between the functions to help prevent smart caching of data between function calls.

I am pretty sure the caching occurs, because I’ve run into this before with trying to measure performance of function calls.

#13

It’s a little hard to draw a meaningful comparison between our timing, since we used two different methods (I mean using the Performance API versus using process.hrtime), but your results are very clearly different. I don’t have time right now to do it, but I’ll change mine over to performance or yours over to hrtime when I do, just to see more straightforward comparisons.

1 Like
#14

Updated to use either performance.now() or process.hrtime.bigint(). Same picture, so it isn’t the timing method. I’m still not sure what the difference is.

Updated Code 
// ---------------------------------------------------
// Timing methodology
// ---------------------------------------------------
const performance = require('perf_hooks').performance;
// USE_PERF
//   true: use performance.now()
//   false: use process.hrtime.bigint()
const USE_PERF = true;

// ---------------------------------------------------
// Recursive variant
// ---------------------------------------------------
function sumFibsRecursive(num) {
  function fibs(i) {
    if (i < 3) return 1;
    return fibs(i-1) + fibs(i-2);
  }
  let sum = 2;
  let i = 3;
  let fn = fibs(i);
  while (fn <= num) {
    if (fn % 2) sum += fn;
    i++;
    fn = fibs(i);
  }
  return sum;
}

// ---------------------------------------------------
// Store two variant
// ---------------------------------------------------
function sumFibsTwo(num) {
  let sum = 2;
  let f0 = 1;
  let f1 = 2;
  while (f1 <= num) {
    if (f1 % 2) sum += f1;
    f1 = f0 + f1;
    f0 = f1 - f0;
  }
  return sum;
}

// ---------------------------------------------------
// Store two variant
// ---------------------------------------------------
function sumFibsDestructure(num) {
  let sum = 2;
  let f0 = 1;
  let f1 = 2;
  while (f1 <= num) {
    if (f1 % 2) sum += f1;
    f1 = f0 + f1;
    f0 = f1 - f0;
  }
  return sum;
}

// ---------------------------------------------------
// Store all variant
// ---------------------------------------------------
function sumFibsAll(num) {
  let sum = 2;
  const fn = [1,1];
  let i = 2
  while (fn[i - 1] <= num) {
    fn[i] = fn[i - 1] + fn[i - 2];
    if (fn[i] % 2 && fn[i] <= num) {
      sum += fn[i];
    }
    i++;
  }
  return sum
  }

// ---------------------------------------------------
// Store all variant, improved
// ---------------------------------------------------
function sumFibsAllFast(num) {
  let sum = 2;
  let fn = [1, 1, 2];
  let i = 2;
  while (fn[i] <= num) {
    if (fn[i] % 2) sum += fn[i];
    fn[i+1] = fn[i] + fn[i-1];
    i++;
  }
  return sum;
}

// ---------------------------------------------------
// Test cases
// ---------------------------------------------------
const numVariants = 5;
const variants = [
  sumFibsRecursive,
  sumFibsTwo,
  sumFibsDestructure,
  sumFibsAll,
  sumFibsAllFast,
  ];
const variantNames = [
  "Recursion, no tricks",
  "Store current two values",
  "Store current two values, with destructuring",
  "Store entire array",
  "Store entire array, reduced OPs",
]

// ---------------------------------------------------
// Timing function
// ---------------------------------------------------
function timeMe(func, num) {
  let time = 0, result = 0;
  if (USE_PERF) {
    t0 = performance.now();
    result = func(num);
    t1 = performance.now();
    time = Number(t1 - t0);
  } else {
    t0 = process.hrtime.bigint();
    result = func(num);
    t1 = process.hrtime.bigint();
    time = Number(t1 - t0);
  }

  // Note: Capturing and returning result may prevent JS
  //  from optimizing out parts of the code
  return {time, result};
}

// ---------------------------------------------------
// T-table values
// ---------------------------------------------------
tValues = [
  12.71,
  4.303,
  3.182,
  2.776,
  2.571,
  2.447,
  2.365,
  2.306,
  2.262,
  2.228,
  2.201,
  2.179,
  2.16,
  2.145,
  2.131,
  2.12,
  2.11,
  2.101,
  2.093,
  2.086,
  2.08,
  2.074,
  2.069,
  2.064,
  2.06,
  2.056,
  2.052,
  2.048,
  2.045,
  2.042,
  2.04,
  2.037,
  2.035,
  2.032,
  2.03,
  2.028,
  2.026,
  2.024,
  2.023,
  2.021,
  2.02,
  2.018,
  2.017,
  2.015,
  2.014,
  2.013,
  2.012,
  2.011,
  2.01,
  2.009,
  2.004,
  2,
  1.997,
  1.994,
  1.992,
  1.99,
  1.988,
  1.987,
  1.985,
  1.984,
]

// ---------------------------------------------------
// Multiple test runs
// ---------------------------------------------------
const numCases = 8;
for (let c = 0; c < numCases; c++) {
  let sum = 0;
  const numRuns = 25;
  let times = [[], [], [], [], []];
  const testNum = 20000*(2**c);

  // Summary
  console.log();
  console.log("Test case " + c);
  console.log("  - Test number           : " + testNum);
  console.log("  - Number runs           : " + numRuns);

  // Call once and throw away result
  for (let i = 0; i < numVariants; i++) {
    timeMe(variants[i], testNum);
  }

  // Time multiple times
  for (let i = 0; i < numRuns; i++) {
    // Each variant
    for (let j = 0; j < numVariants; j++) {
      let {time, result} = timeMe(variants[j], testNum);
      sum += result;
      times[j][i] = time;
    }
  }
  console.log("  - Validity check        : " +
    (
      sum === numRuns*numVariants*sumFibsDestructure(testNum) ?
        "\"Valid data\"" :
        "\"Invalid data\""
    )
  );

  // Output timing data
  for (let i = 0; i < numVariants; i++) {
    // Compute stats
    const minTime = Math.min(...times[i]);
    const maxTime = Math.max(...times[i]);
    const avgTime = times[i].reduce((sum, item) => sum + item, 0) / numRuns;
    const variance = times[i].reduce((sumSqDiff, item) => sumSqDiff + (avgTime - item)**2, 0) / numRuns;
    const stdDev = Math.sqrt(variance);

    // Output
    console.log();
    console.log("  - Variant               : \"" + variantNames[i] + "\"");
    console.log("    Statistics:");
    console.log("      Average Time        : " + avgTime);
    console.log("      Minimum Time        : " + minTime);
    console.log("      Maximum Time        : " + maxTime);
    console.log("      Standard Deviation  : " + stdDev);
    console.log("      Variance            : " + variance);
    console.log("      Confidence Interval : [" +
      (avgTime - tValues[numRuns-1]*stdDev).toFixed(5) +
      ", " +
      avgTime.toFixed(5) +
      ", " +
      (avgTime + tValues[numRuns-1]*stdDev).toFixed(5) +
      "]"
    );
  }
}
Repl

https://replit.com/@jeremylt/GrotesqueNoteworthySpheres#index.js

Sample Output - `performance.now()` 
Test case 7
  - Test number           : 2560000
  - Number runs           : 25
  - Validity check        : "Valid data"

  - Variant               : "Recursion, no tricks"
    Statistics:
      Average Time        : 583.5548874399066
      Minimum Time        : 499.1479770001024
      Maximum Time        : 699.4015239998698
      Standard Deviation  : 50.04558719776144
      Variance            : 2504.560797968744
      Confidence Interval : [480.46098, 583.55489, 686.64880]

  - Variant               : "Store current two values"
    Statistics:
      Average Time        : 0.006078719869256019
      Minimum Time        : 0.0032979995012283325
      Maximum Time        : 0.047867000102996826
      Standard Deviation  : 0.00855423692134246
      Variance            : 0.00007317496930645854
      Confidence Interval : [-0.01154, 0.00608, 0.02370]

  - Variant               : "Store current two values, with destructuring"
    Statistics:
      Average Time        : 0.002953760176897049
      Minimum Time        : 0.002258000895380974
      Maximum Time        : 0.0036149993538856506
      Standard Deviation  : 0.0005050616597111463
      Variance            : 2.550872801101778e-7
      Confidence Interval : [0.00191, 0.00295, 0.00399]

  - Variant               : "Store entire array"
    Statistics:
      Average Time        : 0.019145680144429206
      Minimum Time        : 0.01250000111758709
      Maximum Time        : 0.03777799941599369
      Standard Deviation  : 0.007709820181039697
      Variance            : 0.000059441327223966994
      Confidence Interval : [0.00326, 0.01915, 0.03503]

  - Variant               : "Store entire array, reduced OPs"
    Statistics:
      Average Time        : 0.018998439833521844
      Minimum Time        : 0.010862000286579132
      Maximum Time        : 0.03238900005817413
      Standard Deviation  : 0.00672966936878334
      Variance            : 0.000045288449813140766
      Confidence Interval : [0.00514, 0.01900, 0.03286]
Sample Output - `process.hrtime.bigint()` 
Test case 7
  - Test number           : 2560000
  - Number runs           : 25
  - Validity check        : "Valid data"

  - Variant               : "Recursion, no tricks"
    Statistics:
      Average Time        : 670159210.08
      Minimum Time        : 557879905
      Maximum Time        : 1124115614
      Standard Deviation  : 126200359.26571509
      Variance            : 15926530678795560
      Confidence Interval : [410186469.99263, 670159210.08000, 930131950.16737]

  - Variant               : "Store current two values"
    Statistics:
      Average Time        : 3850.28
      Minimum Time        : 2764
      Maximum Time        : 5483
      Standard Deviation  : 838.2283946514816
      Variance            : 702626.8415999999
      Confidence Interval : [2123.52951, 3850.28000, 5577.03049]

  - Variant               : "Store current two values, with destructuring"
    Statistics:
      Average Time        : 3040.08
      Minimum Time        : 1957
      Maximum Time        : 6247
      Standard Deviation  : 1189.4442709097386
      Variance            : 1414777.6735999999
      Confidence Interval : [589.82480, 3040.08000, 5490.33520]

  - Variant               : "Store entire array"
    Statistics:
      Average Time        : 19542.96
      Minimum Time        : 12712
      Maximum Time        : 94988
      Standard Deviation  : 15675.536516444981
      Variance            : 245722445.07840005
      Confidence Interval : [-12748.64522, 19542.96000, 51834.56522]

  - Variant               : "Store entire array, reduced OPs"
    Statistics:
      Average Time        : 13881.92
      Minimum Time        : 10516
      Maximum Time        : 18922
      Standard Deviation  : 2770.221116373204
      Variance            : 7674125.0336
      Confidence Interval : [8175.26450, 13881.92000, 19588.57550]

By the way, this has been a fun and interesting diversion, so thank you.

#15

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.