Tag Archives: Recursion

POW Answer – Explain That SQL #1

To answer last week’s POW, the purpose of the SQL was to generate a random string of letters and numbers. I actually wrote two different JavaScript function that can produce the same results. The following is the slightly more straight-forward solution:

function randomChars(len) {
  for(var n, s = ""; --len;) {
    n = parseInt(Math.random() * 62);
    s = String.fromCharCode(n + (n < 26 ? 65 : n < 52 ? 71 : -4));
  }
  return s;
}

The next version is a bit harder to follow because it involves recursion:

function recRandomChars(len) {
  if(!len){ return ""; }
  var n = parseInt(Math.random() * 62);
  return recRandomChars(--len)
    + String.fromCharCode(n + (n < 26 ? 65 : n < 52 ? 71 : -4));
}

One practical application of this is to generate a password with random characters.

JScript – Recursively Call A Script

Have you ever wondered how you can recursively call a JScript? Here is an example which shows how it can be done:

WshShell = new ActiveXObject("WScript.Shell");
switch(WshShell.Popup("Do you want to run this script again?", 10, "Run Script Again", 4 + 32))
{
  case -1:
    WScript.Echo("I guess you aren't there.  See'ya!!!");
    break;
  case 6:
    WshShell.run('"' + WScript.ScriptFullName + '"');
    break;
  case 7:
    WScript.Echo("Take it easy.");
    break;
}

It is important to note that the above example will not pass any variables that were passed to it. If you want to try this out on your Windows machine, download Recursive Script to your computer and double-click it.

JavaScript – Binary Search

The following is an implementation of a binary search for arrays which gives you the ability to do fuzzy matches (default), exact matches, or specify your own comparison function:

(function() {
  // Use this if the search isn't called with a 2nd param or it
  // is false.
  function fnFuzzy(a, b) {
    return a < b ? -1 : a > b ? 1 : a == b ? 0 : null;
  }
  
  // Use this if the search is called with a 2nd param of true.
  function fnExact(a, b) {
    return a < b ? -1 : a > b ? 1 : a === b ? 0 : null;
  }
  
  // Recursively does a binary search.
  function binarySearch(arr, item, min, max, fnCmp) {
    if(min > max) {
      return -1;
    }
    var mid = parseInt((min + max) / 2);
    var ret = fnCmp(item, arr[mid]);
    if(ret) {
      return binarySearch(arr, item,
        ret > 0 ? mid + 1 : min,
        ret < 0 ? mid - 1 : max, fnCmp);
    }
    else if(ret == 0) {
      return mid;
    }
  }
  
  // Define the prototypal function.
  Array.prototype.binarySearch = function(item, extactMatch) {
    return binarySearch(this, item, 0, this.length - 1,
      extactMatch
        ? typeof extactMatch == "function"
          ? extactMatch
          : fnExact
        : fnFuzzy);
  };
})();

I used the following to test the normal execution of this binary function:

// Create a pre-sorted array of distinct random numbers ranging
// from 0 to 9999 and keep a reverse index to validate what is
// being returned by the binarySearch() function:
var arr = [], reverseIndex = {"-1" : -1};
for(var limit = 10000, i = 0; i < limit; i++) {
  if(Math.random() < 0.5) {
    reverseIndex[i] = arr.length;
    arr.push(i);
  }
  else {
    reverseIndex[i] = -1;
  }
}
reverseIndex[limit] = -1;

// Run through all numbers from -1 to 10000, using the reverse
// index making sure that the binarySearch() function works
// properly:
for(var v1, v2, i = -1; i <= limit; i++) {
  // If the binary search doesn't return the correct thing,
  // let the user know.
  if((v1 = arr.binarySearch(i)) != (v2 = reverseIndex[i])) {
    alert("The search for " + i + " returned an index of "
      + v1 + " when it should have returned " + v2
      + ".");
    break;
  }
}

// If all of the tests were successfully run, tell the user.
if(i == limit + 1) {
  alert("All " + arr.length
    + " numbers that should have been found were found.");
}