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

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

Rangkaian Sensor Cahaya dengan LDR

LDR(Light Depending Resistor) adalah resistor yang nilai hambatannya bergantung dari intensitas cahaya yang ia terima. Jika intensitas cahaya rendah (gelap) maka nilai resistansinya akan menjadi sangat besar (mencapai 1MOhm atau lebih), sedangkan jika intensitas cahaya tinggi (terang) nilai resistansinya menjadi kecil (mencapai 10kOhm atau kurang). Sifat ini dapat kita pergunakan dalam rangkaian sensor cahaya. Misalkan jika kita menginginkan sensor cahaya yang akan menyalakan lampu indikasi ketika ada cahaya dan mematikan lampu indikasi ketika tidak ada cahaya. Kita dapat menggunakan rangkaian seperti gambar di bawah ini. Transistor NPN berfungsi sebagai gate. Arus dari kolektor akan mengalir menuju emitor jika arus dari base besar namun jika arus pada base kecil maka arus dari kolektor tidak akan menuju emitor. Pada rangkaian sensor cahaya dengan LDR, ketika intensitas cahaya tinggi (terang) maka arus dari VCC akan melewati LDR kemudian melewati RESISTOR dan masuk ke

Installing APCu in PHP 7

APCu is one of caching application for PHP. In this case, I use PHP 7.0 on Ubuntu 16.04. In PHP 7.0, this application is provided via PEAR. First, install PEAR. $ sudo apt-get install php-pear Install APCu. If an error occured state that there's no phpize, you need to install PHP 7.0-dev which provide phpize support. $ sudo apt-get install php7.0-dev $ sudo pecl install apcu Create APCu module configuration in PHP modules directory. $ sudo echo "extension = apcu.so" >> /etc/php/7.0/mods-available/apcu.ini Add that configuration to PHP FPM and CLI. $ sudo ln -s /etc/php/7.0/mods-available/apcu.ini /etc/php/7.0/fpm/conf.d/30-apcu.ini $ sudo ln -s /etc/php/7.0/mods-available/apcu.ini /etc/php/7.0/cli/conf.d/30-apcu.ini Restart PHP FPM.

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

Setting Up Next.js Project With ESLint, Typescript, and AirBnB Configuration

If we initiate a Next.js project using the  create-next-app tool, our project will be included with ESLint configuration that we can apply using yarn run lint . By default, the tool installs eslint-config-next and extends next/core-web-vitals in the ESLint configuration. The Next.js configuration has been integrated with linting rules for React and several other libraries and tools. yarn create next-app --typescript For additional configuration such as AirBnB, it is also possible. First, we need to install the peer dependencies of eslint-config-airbnb . We also add support for Typescript using eslint-config-airbnb-typescript . yarn add --dev eslint-config-airbnb eslint-plugin-import eslint-plugin-jsx-a11y eslint-plugin-react eslint-plugin-react-hooks yarn add --dev eslint-config-airbnb-typescript @typescript-eslint/eslint-plugin @typescript-eslint/parser After that, we can update the .eslintrc.json file for the new configuration. { "extends": [ "airb

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