Problem
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 ?
Solution
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 usesnake_case
-
DO NOT include code that does nothing.
Some examples
-
var fibonacci = fibonacci;
Not needed at all. -
fiboNums.toString()
inconsole.log
. toString is automatic. Can beconsole.log(fiboNums);
-
The brackets in
(prev_num === 0) ? (prev_num + 1) : cur_num;
and the next line in your code. Can beprevNum = prevNum === 0 ? prevNum + 1 : curNum;
orprevNum = !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;
}