Can I optimize my implementation of generating Fibonacci series using recursion?

Question

My function accepts a number, which generates total Fibonacci numbers. I am using recursion.

Please follow the code below,

var fibo = (n) => {
 var fibonacci = fibonacci;
 var fiboNums = [], prevNum = 0, currentNum = 0;
 
 fibonacci(n, prevNum, currentNum);
 
 console.log(fiboNums.toString());
 
 function fibonacci(num, prev_num, cur_num){
 var temp = prev_num;
 
 fiboNums.push(prev_num);
 
 prev_num = (prev_num === 0) ? (prev_num + 1) : cur_num;
 
 cur_num = (prev_num === 1 || prev_num === 2) ? (prev_num + 1) : prev_num + temp;
 
 num--;
 
 if(num > 0) {
 fibonacci(num, prev_num, cur_num);
 }
 }
}
fibo(6);
fibo(8);
fibo(10);
fibo(12);

The output is as below,

PS D:\> node .\fibonacci.js
0,1,2,3,5,8
0,1,2,3,5,8,13,21
0,1,2,3,5,8,13,21,34,55
0,1,2,3,5,8,13,21,34,55,89,144
PS D:\>

Please review the above code and let me know is there any room for improvement. Can I further optimise the code ?

• greybeard: You may get more useful reviews if you stated your goal in coding the above. You have been pointed to avoidable special casing more than once.
• RobH: The Fibonacci sequence is 0, 1, 1, 2, 3... i.e. 1 is there twice. Your code isn't correct.

Answer 1

Bug

As pointed out in comments the start of the sequence is [0, 1, 1, 2 ...] you function starts with [0, 1, 2 ...]

Code style

• Use constants for variables that do not change.

• The JS convention is to use camelCase, we don't use snake_case

• DO NOT include code that does nothing.

  Some examples

  • var fibonacci = fibonacci; Not needed at all.

  • fiboNums.toString() in console.log. toString is automatic. Can be console.log(fiboNums);

  • The brackets in (prev_num === 0) ? (prev_num + 1) : cur_num; and the next line in your code. Can be prevNum = prevNum === 0 ? prevNum + 1 : curNum; or prevNum = !prevNum ? prevNum + 1 : curNum;

  • The 2 single use variables prevNum, currentNum are unnecessary.

Design

Single role

Move the console.log out of the function. The role of the function is to create an array of numbers, outputting to the console is outside the role of the function. The log make the function un-reusable without modification.

Source code complexity

You have an array of previous values, there is no need to store the previous two values in variables as you have them in the array.

Recursion

JavaScript is very bad at recursion. For example your function will fail if you want the first 50000 numbers as this is greater than the call stack size.

Each time you recurs a function JavaSctipt needs to create a new function context and push it to the call stack. When the function returns that entry needs to be removed, and needs to be deleted (more overhead).

Use recursion if the loop is to complex (has many states to manage), or the processing need is small and the recursion count in within the call stack limit (10K-30K depending on the engine). Else use a standard loop as they are much quicker and a lot safer.

Rewrites

Rewrite using recursion. Note that there is a limit of ~9K (may still fail as the call stack use can not be known)

const fiboRecurs = n => {
 if (n > 9_000) { return [] }
 if (n <= 0) { return [] }
 if (n === 1) { return [0] }
 const result = [0, 1]; 
 if (n === 2) { return result }
 return fibonacci(n - 2);
 function fibonacci(n) {
 result[result.length] = result[result.length - 2] + result[result.length - 1];
 n -= 1;
 return n > 0 ? fibonacci(n) : result;
 }
}

Rewrite using a loop. Only limit is the memory to store array. Will be many time quicker than the recursive version (depending on the size of the array) (6 times faster for fibo(5000))

const fibo = n => {
 if (n <= 0) { return [] }
 if (n === 1) { return [0] }
 const res = [0, 1];
 if (n === 2) { return res }
 n -= 2;
 while (n > 0) {
 res[res.length] = res[res.length - 2] + res[res.length - 1];
 n -= 1; 
 }
 return result;
}

• qwr: If the function returns results as a list, then too large input should not silently return an empty list but some kind of error or special value.
• Blindman67: @qwr I am in partial agreement with you, however as the original code did not return anything I just added it to highlight the call stack limit and as stated ",,, call stack use can not be known" so the line is unreliable. The only reliable solution is to wrap the code in a try catch and deal the the call stack overflow as it happens (or use the safe looping solution) .