Skip to main content

Fibonacci In Javascript Using Generator Function and Iterable

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

Popular posts from this blog

Configuring Swap Memory on Ubuntu Using Ansible

If we maintain a Linux machine with a low memory capacity while we are required to run an application with high memory consumption, enabling swap memory is an option. Ansible can be utilized as a helper tool to automate the creation of swap memory. A swap file can be allocated in the available storage of the machine. The swap file then can be assigned as a swap memory. Firstly, we should prepare the inventory file. The following snippet is an example, you must provide your own configuration. [server] 192.168.1.2 [server:vars] ansible_user=root ansible_ssh_private_key_file=~/.ssh/id_rsa Secondly, we need to prepare the task file that contains not only the tasks but also some variables and connection information. For instance, we set /swapfile  as the name of our swap file. We also set the swap memory size to 2GB and the swappiness level to 60. - hosts: server become: true vars: swap_vars: size: 2G swappiness: 60 For simplicity, we only check the exi

Rangkaian Sensor Infrared dengan Photo Dioda

Keunggulan photodioda dibandingkan LDR adalah photodioda lebih tidak rentan terhadap noise karena hanya menerima sinar infrared, sedangkan LDR menerima seluruh cahaya yang ada termasuk infrared. Rangkaian yang akan kita gunakan adalah seperti gambar di bawah ini. Pada saat intensitas Infrared yang diterima Photodiode besar maka tahanan Photodiode menjadi kecil, sedangkan jika intensitas Infrared yang diterima Photodiode kecil maka tahanan yang dimiliki photodiode besar. Jika  tahanan photodiode kecil  maka tegangan  V- akan kecil . Misal tahanan photodiode mengecil menjadi 10kOhm. Maka dengan teorema pembagi tegangan: V- = Rrx/(Rrx + R2) x Vcc V- = 10 / (10+10) x Vcc V- = (1/2) x 5 Volt V- = 2.5 Volt Sedangkan jika  tahanan photodiode besar  maka tegangan  V- akan besar  (mendekati nilai Vcc). Misal tahanan photodiode menjadi 150kOhm. Maka dengan teorema pembagi tegangan: V- = Rrx/(Rrx + R2) x Vcc V- = 150 / (150+10) x Vcc V- = (150/160) x 5

Installing VSCode Server Manually on Ubuntu

I've ever gotten stuck on updating the VSCode server on my remote server because of an unstable connection between my remote server and visualstudio.com that host the updated server source codes. The download and update process failed over and over so I couldn't remotely access my remote files through VSCode. The solution is by downloading the server source codes through a host with a stable connection which in my case I downloaded from a cloud VPS server. Then I transfer the downloaded source codes as a compressed file to my remote server through SCP. Once the file had been on my remote sever, I extracted them and align the configuration. The more detailed steps are as follows. First, we should get the commit ID of our current VSCode application by clicking on the About option on the Help menu. The commit ID is a hexadecimal number like  92da9481c0904c6adfe372c12da3b7748d74bdcb . Then we can download the compressed server source codes as a single file from the host.

Resize VirtualBox LVM Storage

VirtualBox is a free solution to host virtual machines on your computer. It provides configuration options for many components on our machine such as memory, storage, networking, etc. It also allows us to resize our machine storage after its operating system is installed. LVM is a volume manager in a Linux platform that helps us to allocate partitions in the system and configure the storage size that will be utilized for a specific volume group. There are some points to be noticed when we work with LVM on VirtualBox to resize our storage. These are some steps that need to be performed. 1. Stop your machine before resizing the storage. 2. Set new storage size using GUI by selecting " File > Virtual Media Manager > Properties " then find the desired virtual hard disk name that will be resized. OR , by running a CLI program located in " Program Files\Oracle\VirtualBox\VBoxManage.exe ".  cd "/c/Program Files/Oracle/VirtualBox" ./VBoxManage.exe list

Managing MongoDB Records Using NestJS and Mongoose

NestJS is a framework for developing Node.js-based applications. It provides an additional abstraction layer on top of Express or other HTTP handlers and gives developers a stable foundation to build applications with structured procedures. Meanwhile, Mongoose is a schema modeling helper based on Node.js for MongoDB. There are several main steps to be performed for allowing our program to handle MongoDB records. First, we need to add the dependencies which are @nestjs/mongoose , mongoose , and @types/mongoose . Then, we need to define the connection configuration on the application module decorator. import { MongooseModule } from '@nestjs/mongoose'; @Module({ imports: [ MongooseModule.forRoot('mongodb://localhost:27017/mydb'), ], controllers: [AppController], providers: [AppService], }) Next, we create the schema definition using helpers provided by NestJS and Mongoose. The following snippet is an example with a declaration of index setting and an o

Communicate Through RabbitMQ Using NodeJS and Fastify

If we have two or more services that need to talk to each other but it is allowed to be asynchronous, we can implement a queue system in our system using RabbitMQ. RabbitMQ server will maintain all queues and connections to all services connected to it. This post will utilize Fastify as a NodeJS framework to build our program. This framework is similar to Express but implements some unique features like a plugin concept and an improved request-respond handler. First, we need to create two plugins, one is for sending a message, another one is for consuming the sent message. At first, we will make it using a normal queue. There is one mechanism for how a queue works, it is like a queue in the real world. When there are five persons in a queue and three staff to handle the queue, one person is served only by one staff, there is no need for other staff to handle any person that has been served, and there is no need for a person to be handled repeatedly by other staffs. For example