# Recursion with fibonacci

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

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.

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

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.

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

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.

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

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

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

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.

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

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.

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

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.

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