How to you use recursion in javascript to create key value objects

Question

I understand how to go about tasks using loops, recursion is kind of a mystery to me, but from what I understand in certain cases it can save a ton of time if looping through a lot of data.

I created the following function to loop through a large(ish) data set.

var quotes = require('./quotes.js');
//Pulls in the exported function from quotes.js
var exportedQuotes = quotes.allQuotes();
var allAuthors = exportedQuotes.author;
//Create an empty key value object, we use these to coerce unique values to an array
var uniqs = {};
//I create this object to hold all the authors and their quotes
var fullQuote = {};
//Create an object with only unique authors
for(var i = 0; i < allAuthors.length ; i++){
        fullQuote[allAuthors[i]] = null;
}
//Coerce unique authors from javascript object into an array
var uniqAuthors = Object.keys(uniqs);

var quoteCount = exportedQuotes.author.length;



var iterativeSolution = function(){
        for(var i = 0; i < Object.keys(fullQuote).length; i++){
            for(var j = 0; j < exportedQuotes.author.length; j++){
                //If the author in the unique list is equal to the author in the duplicate list
                if(Object.keys(fullQuote)[i] == exportedQuotes.author[j]){
                    //if an author has not had a quote attributed to its name
                    if(fullQuote[exportedQuotes.author[j]] == null){
                        //assign the author an array with the current quote at the 0 index
                        fullQuote[exportedQuotes.author[j]] = [exportedQuotes.quote[j]]
                    } else {
                        //if an author already has a quote assigned to its name then just add the current quote to the authors quote list
                        fullQuote[exportedQuotes.author[j]].push(exportedQuotes.quote[j])
                    }
                }
            }
        }
    }

---

I don't currently have the skills to do analyze this, but, I'm wondering if there is a case for recursion to save the time it takes to get through all the loops. And if there is a case for recursion what does it look like for nested loops in javascript, specifically when creating key value objects recursively?

Answer 1

I got really curious and created a recursive solution just to see how it works. Then timed it, my iterative solution took 53 seconds to run, while my recursive solution took 1 millisecond to run. The iterative approach can obviously be tweaked based on the answers provided below, to run faster, but a recursive approach forced me to think in a "leaner" manner when creating my function.

    var exportedQuotes = quotes.allQuotes();
    var allAuthors = exportedQuotes.author;
    var n = allAuthors.length
    var fullQuote = {};
    var recursiveSolution = function(arrayLength) {
    //base case
    if(arrayLength <= 1){
        if(fullQuote[exportedQuotes.author[0]] == null){
            fullQuote[exportedQuotes.author[0]] = [exportedQuotes.quote[0]];
        }else{
            fullQuote[exportedQuotes.author[0]].push(exportedQuotes.quote[0])
        }
        return;
    };
    //recursive step
    if(fullQuote[exportedQuotes.author[arrayLength]] == null){
            fullQuote[exportedQuotes.author[arrayLength]] = [exportedQuotes.quote[arrayLength]];
        }else{
            fullQuote[exportedQuotes.author[arrayLength]].push(exportedQuotes.quote[arrayLength])
        }
    newLength = arrayLength - 1;
    return recursiveSolution(newLength);
}

////////Timing functions

var timeIteration = function(){
    console.time(iterativeSolution);

    iterativeSolution(); // run whatever needs to be timed in between the statements

    return console.timeEnd(iterativeSolution);
}

var timeRecursive = function(){
    console.time(recursiveSolution(n));

    recursiveSolution(n); // run whatever needs to be timed in between the statements

    return console.timeEnd(recursiveSolution(n));
}

Answer 2

There may be a slight misunderstanding about what recursion is: recursion does not save time. It's just a different way of doing the same traversal. It generally a little easier to read, and depending on the problem, will map to certain algorithms better. However, one of the first things we do when we need to start optimizing code for speed is to remove recursion, turning them back into loops, and then even "unrolling" loops, making code much uglier, but fast, in the process. Recursion vs plain loops is almost always a matter of taste. One looks nicer, but that's hardly the only quality we should judge code on.

And also: just because it sounds like I'm advocating against using it, doesn't mean you shouldn't just try it: take that code, put it in a new file, rewrite that file so that it uses recursion. Doing so lets you compare your code. Which one is faster? Which is easier to read? Now you know something about how (your) code behaves, and you'll have learned something valuable.

Also don't sell yourself short: if you wrote this code, you know how it works, so you know how to analyze it enough to rewrite it.

Answer 3

You don't have to iterate Object.keys(fullQuote).

var quotes = require('./quotes.js'),
    exportedQuotes = quotes.allQuotes(),
    allAuthors = exportedQuotes.author,
    fullQuote = Object.create(null);
for(var i=0; i < allAuthors.length; ++i)
  (fullQuote[allAuthors[i]] = fullQuote[allAuthors[i]] || [])
  .push(exportedQuotes.quote[i])

I don't recommend recursion. It won't improve the asymptotic cost, and in JS calling functions is a bit expensive.

Answer 4

Algorithms makes code fast or slow, not recursion. Some quite fast algorithms can use recursion, but that's a whole different story. Many algorithms can be written as both with recursion, and without recursion.

However, your code has a big problem. Notice how many times you call this code?

Object.keys(fullQuote)

You are re-computing the value of that many many times in your code. Don't do that. Just call it once and store in a variable, like the following:

var uniqAuthors = Object.keys(uniqs);
var uniqFullQuote = Object.keys(fullQuote);

var quoteCount = exportedQuotes.author.length;

//Loop through all quotes and assign all quotes to a unique author::Each author has many quotes
for(var i = 0; i < uniqFullQuote.length; i++){
    for(var j = 0; j < exportedQuotes.author.length; j++){
        //If the author in the unique list is equal to the author in the duplicate list
        if(uniqFullQuote[i] == exportedQuotes.author[j]){
            //if an author has not had a quote attributed to its name
            if(fullQuote[exportedQuotes.author[j]] == null){
                //assign the author an array with the current quote at the 0 index
                fullQuote[exportedQuotes.author[j]] = [exportedQuotes.quote[j]]
            } else {
                //if an author already has a quote assigned to its name then just add the current quote to the authors quote list
                fullQuote[exportedQuotes.author[j]].push(exportedQuotes.quote[j])
            }
        }
    }
}