Tag Archives: Recursion

POW Answer – Unnamed Function #1

The answer to last week’s Problem of the Week is that the following definitions represent the factorial of the given non-negative integer:

Mathematical Definition

Function Definition Condition
unnamed(n) = 1 if n = 0
n × unnamed(n – 1) if n > 0

JavaScript Definition

function unnamed(n) {
  if(n == 0)
    return 1;
  if(n > 0)
    return n * unnamed(n - 1);
}

Although it may have been easy for some people to follow, for those of you who are not familiar with recursion, it may have been a bit difficult. Let’s use the number 4 as an example to step through the process:

  1. When we pass 4 into unnamed we get the following definition for the output:
    unnamed(4) = 4  × unnamed(4 - 1) = 4 × unnamed(3)
  2. Now we have to find the definition for passing 3 into unnamed:
    unnamed(3) = 3  × unnamed(3 - 1) = 3 × unnamed(2)
  3. Now we have to find the definition for passing 2 into unnamed:
    unnamed(2) = 2  × unnamed(2 - 1) = 2 × unnamed(1)
  4. Now we have to find the definition for passing 1 into unnamed:
    unnamed(1) = 1  × unnamed(1 - 1) = 1 × unnamed(0)
  5. Now we have to find the definition for passing 0 into unnamed:
    unnamed(0) = 1
  6. Now we go back to step 4 and replace unnamed(0) with 1:
    unnamed(1) = 1  × 1 = 1
  7. Now we go back to step 3 and replace unnamed(1) with 1:
    unnamed(2) = 2  × 1 = 2
  8. Now we go back to step 2 and replace unnamed(2) with 2:
    unnamed(3) = 3  × 2 = 6
  9. Now we go back to step 1 and replace unnamed(3) with 6:
    unnamed(4) = 4  × 6 = 24

After stepping through each part of the process, you can more easily see the pattern.

  • unnamed(4) is really equal to 4 × 3 × 2 × 1 × 1
  • unnamed(3) is really equal to 3 × 2 × 1 × 1
  • unnamed(2) is really equal to 2 × 1 × 1
  • unnamed(1) is really equal to 1 × 1
  • unnamed(0) is really equal to 1
    NOTE: The above (0! = 1) is more of a technicality that many people don’t really think about for factorial.

Forcing A Constructor In JavaScript

Did you know that you can force a function to only act as a constructor? The following is an example of a Person pseudo-class which can be defined with or without the new keyword:

// Defines a person object.
function Person(firstName, lastName, age) { 
  // If called without parameters.
  if(!arguments.length) {
    // If this is a recursive call, allow the properties to now be defined.
    if(arguments.callee.caller === arguments.callee) {
      return this;
    }
    // If this is a non-recursive call, throw an error since the constructor
    // can't be called without parameters.
    else {
      throw new Error("No parameters were specified for the Person object.");
    }
  }
  
  // Allows make sure this function acts as a constructor.
  var me = !(this instanceof arguments.callee) ? new Person : this;
    
  // Define the properties.
  me.firstName = firstName;
  me.lastName = lastName;
  me.age = age;
  
  // Return a reference to the new Person instance.
  return me;
}

// Define the prototypal functions.
Person.prototype = {
  toString : function() {
    return this.firstName + " " + this.lastName + " is " + this.age
      + " years old.";
  }
};

One of the things that you may have noticed is the fact that I am throwing an error if the constructor is called without any arguments. If you don’t want that to happen, you can simply remove that else statement. Everything is probably pretty self explanatory.

The following are two examples which prove the above code actually works:

// Create an instance of a person without the "new" keyword.
var p = Person("Chris", "West", 23);
alert(p.firstName);  // display "Chris"
alert(p instanceof Person);  // display true
alert(p);  // use toString() function

// Create an instance of a person with the "new" keyword.
var p = new Person("Tamara", "Thomas", 21);
alert(p.age);  // display 21
alert(p instanceof Person);  // display true
alert(p);  // use toString() function.

Deep Copy of Arrays

With jPaq and many other JavaScript libraries, it is very easy to do a shallow copy of an array. On the other hand, it isn’t as easy to do a deep copy of arrays. For this reason, I plan on replacing the Array.prototype.clone() function with the following:

Array.prototype.clone = function(doDeepCopy) {
    if(doDeepCopy) {
        var encountered = [{
            a : this,
            b : []
        }];

        var item,
            levels = [{a:this, b:encountered[0].b, i:0}],
            level = 0,
            i = 0,
            len = this.length;

        while(i < len) {
            item = levels[level].a[i];
            if(Object.prototype.toString.call(item) === "[object Array]") {
                for(var j = encountered.length - 1; j >= 0; j--) {
                    if(encountered[j].a === item) {
                        levels[level].b.push(encountered[j].b);
                        break;
                    }
                }
                if(j < 0) {
                    encountered.push(j = {
                        a : item,
                        b : []
                    });
                    levels[level].b.push(j.b);
                    levels[level].i = i + 1;
                    levels[++level] = {a:item, b:j.b, i:0};
                    i = -1;
                    len = item.length;
                }
            }
            else {
                levels[level].b.push(item);
            }

            if(++i == len && level > 0) {
                levels.pop();
                i = levels[--level].i;
                len = levels[level].a.length;
            }
        }

        return encountered[0].b;
    }
    else {
        return this.slice(0);
    }
};

The above code can be used to make deep copies of arrays. It is important to note, though, that only sub-arrays are deeply copied, not objects. The reason so much code is used is to even make it possible to make a deep copy of a recursive array structure. The following code exemplifies how to use this function:

// Create a recursive array to prove that the cloning function can handle it.
var arrOriginal = [1,2,3];
arrOriginal.push(arrOriginal);

// Make a shallow copy of the recursive array.
var arrShallowCopy = arrOriginal.clone();

// Prove that the shallow copy isn't the same as a deep copy by showing that
// arrShallowCopy contains arrOriginal.
alert("It is " + (arrShallowCopy[3] === arrOriginal)
    + " that arrShallowCopy contains arrOriginal.");

// Make a deep copy of the recursive array.
var arrDeepCopy = arrOriginal.clone(true);

// Prove that the deep copy really works by showing that the original array is
// not the fourth item in arrDeepCopy but that this new array is.
alert("It is "
    + (arrDeepCopy[3] !== arrOriginal && arrDeepCopy === arrDeepCopy[3])
    + " that arrDeepCopy contains itself and not arrOriginal.");

If you want to use this code right now, there is nothing stopping you. The code doesn’t require any library references and is fully cross-browser compatible. A JSBin example can be found here. It even works in JScript. The only thing that I ask is that you give credit where it is due. :D