Generating the Fibonacci sequence is usually demonstrated in computer science courses to show an implementation of a recursive function. Besides the recursive function, we can utilize the generator function in Javascript for generating the sequence. Let us take a look at a few methods that we can perform. For instance, we will create some functions to get the value of a certain position in the Fibonacci sequence. Then, we will measure up the performance to get solid ground on what we should choose in our application.
Recursive Function
This is the simplest method for getting the value in the sequence. We use 1, not 0, as starting position to make this function more human.
function getFibonacci1(pos) {
if (pos === 1) {
return 0;
}
if (pos === 2) {
return 1;
}
return getFibonacci1(pos - 1) + getFibonacci1(pos - 2);
}Generator Function
In this method, we create a generator function for generating sequence and the actual function for providing the result. The generator function results in an iterator that implements the next() method to iterate over the results.
function* fibonacci() {
let a = 0;
let b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
export function getFibonacci2(pos) {
const gen = fibonacci();
for (let i = 1; i < pos; i++) {
gen.next();
}
return gen.next().value;
}Iterable Object
We can also create an iterable object which implements a generator function as its property. We can iterate an iterable object using the for-of statement.
const fibonacciObj = {
*[Symbol.iterator]() {
let a = 0;
let b = 1;
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
};
export function getFibonacci3(pos) {
let count = 1;
let result = 0;
for (const val of fibonacciObj) {
if (count === pos) {
result = val;
break;
}
count++;
}
return result;
}We start the test to get the value of the number at position 10. The result is as follows.
| No. | Recursive | Generator Function | Iterable Object |
| 1 | 0.044599950313568 | 0.095099985599518 | 0.094399988651276 |
| 2 | 0.042400002479553 | 0.085600018501282 | 0.095099985599518 |
| 3 | 0.043699979782104 | 0.087499976158142 | 0.09799998998642 |
| 4 | 0.042400002479553 | 0.086300015449524 | 0.096100032329559 |
| 5 | 0.042699992656708 | 0.087100028991699 | 0.104199945926666 |
| Average | 0.043159985542297 | 0.088320004940033 | 0.097559988498688 |
It shows that the recursive method seems more superior to the rest. But. what if we try to get the value of the number at a higher position such as 40. The result is as follows.
| No. | Recursive | Generator Function | Iterable |
| 1 | 682.451999962329 | 0.213900029659271 | 0.122600018978118 |
| 2 | 701.861900031566 | 0.204699993133544 | 0.121100008487701 |
| 3 | 667.377600014209 | 0.206699967384338 | 0.122200012207031 |
| 4 | 675.731999993324 | 0.218099951744079 | 0.126100003719329 |
| 5 | 659.384400010109 | 0.203800022602081 | 0.11540001630783 |
| Average | 677.361580002307 | 0.209439992904663 | 0.121480011940002 |
The result shows that recursion performance is very poor compared to other methods. The recursive method initiates a new function every time it is called. While the others basically only run a loop process. They only need chunks of time at the beginning of the process to set up the generator. The third method performs better because it only initiates the iterable object once in the process. While the second method still needs to reinitiate the generator function every time the main process is run.
In conclusion, we must be careful in utilizing recursive functions. It may consume a lot of our computing resources. Alternatively, the generator function may become another option in generating any kind of sequence in a Javascript program.
Comments
Post a Comment