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

Posted on

Problem

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

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

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