Category Archives: Javascript

Javascript’s Prototype-Based Inheritance

Leave a reply

Let’s create a Dragon “class” in Javascript that we can use to inherit from.

var Dragon = function(color) {
  this.color = color;
}

// prototype is a special object used for inheritance in Javascript.
// We could have added the attack method as a member variable similar to color, however we'll use it on the prototype
// later.
Dragon.prototype.attack = function() {
  console.log("The " + this.color + " dragon breathes fire!");
}

var dragon = new Dragon("red");
dragon.attack();  // The red dragon breathes fire!

Calling “new Dragon();” creates a new object that inherits anything set on the Dragon.prototype object. First, Javascript will check to see if a property exists on Dragon itself. If it doesn’t exist on Dragon, it will check Dragon.prototype. We can check to see whether properties exist on Dragon or it’s prototype as follows:

dragon.hasOwnProperty("color"); // true
dragon.hasOwnProperty("attack"); // false, this is not an "own" property - it's part of the prototype

The hasOwnProperty method differentiates between an objects properties and those that were inherited from it’s prototype. Where does the “hasOwnProperty” method come from? The hasOwnProperty method comes from Object.prototype:

1) dragon inherits from Dragon.prototype
2) Dragon.prototype inherits from Object.prototype
3) Object.prototype inherits from “null” prototype – essentially, null allows is the dead-end in our prototype chain

Let’s try some inheritance out:

Dragon.prototype.fly = function() { console.log("The " + this.color + " dragon flaps its wings and flies!"); }
dragon.fly(); // The red dragon flaps its wings and flies!

// Now lets create a Baby Dragon

var BabyDragon = function(color) {
  Dragon.call(this, color); // Essentially super().  Set color, but on BabyDragon, not Dragon.
  this.fly = function() { console.log("The " + this.color + " dragon tries to fly, but is still too young!"); }
}

// We need to set the BabyDragon prototype to inherit from the Dragon prototype.  This will give us access to the attack method.
BabyDragon.prototype = Object.create(Dragon.prototype);

// Set this, otherwise it will be Dragon
BabyDragon.prototype.constructor = BabyDragon;

var baby = new BabyDragon("green");
baby.fly(); // The green dragon tries to fly, but is still too young!
baby.attack(); // The green dragon breathes fire!

ECMAScript 2015 (6th Edition) introduces the class keyword to Javascript which adds some interesting syntatic sugar for you to explore.

Recursion Optimization: Fibonacci Sequence in Javascript

Leave a reply

The Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, …

The nth Fibonacci number is defined as (n-1) + (n-2). For example, the 5th Fibonacci number is the sum of the 4th (n-1) and 3rd (n-2) Fibonacci numbers: 3 + 2 = 5.

The 8th Fibonacci number is the sum of the 7th (8-1) and 6th (8-2) Fibonacci numbers: 13 + 8 = 21.

A recursive Fibonacci function in Javascript works as follows:

var recursiveFib = function(n) {
  // base case: the first two Fib numbers are 1
  if (n <= 2) { 
    return 1; 
  } else {
    // The nth Fib # is (n-1) + (n-2)
    return recursiveFib(n-1) + recursiveFib(n-2);
  }
}

This works, but my browser cannot compute recursiveFib(100); Too much for it to handle?

We can optimize this function using tail-recursion. In the recursiveFib function, a call stack is created to keep track of all the calls to recursiveFib.

function tailRecFib(n) {
  return function(n,a,b) {
    return n > 1 ? arguments.callee(n-1,b,a+b) : a;
  }(n,1,1);
}

This tail-recursive version is more efficient because it simply accumulates the Fibonacci computation in an argument to the function (a+b). No longer do we need to store a tremendous amount of calculations on the stack – it’s now treated much like an iterative for loop.

Finally, there exists a closed-form formula to calculate the nth Fibonacci number. Using this formula, we can arrive at the function:

function closedFormFib(n) {
  var sqrt5 = Math.sqrt(5);
  var a = (1 + sqrt5)/2;
  var b = (1 - sqrt5)/2;
  var ans = Math.round((Math.pow(a, n) - Math.pow(b, n))/sqrt5);
  return ans;
}

* These functions do contain rounding errors due to Javasript’s internal handling of numbers.