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?

Mike 'Pomax' Kamermans · Accepted Answer · 2015-06-25 22:25:56Z

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.

Simon Forsberg · Accepted Answer · 2015-06-21 23:51:46Z

1

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])
            }
        }
    }
}

answered Jun 21, 2015 at 23:51

Simon Forsberg

13.4k11 gold badges67 silver badges109 bronze badges

2 Comments

Keon Cummings Over a year ago

So what i'm getting is that recursion is good for readability at best, but it's more a stylistic option? Is that correct?

Simon Forsberg Over a year ago

@Keon It's different from case to case, sometimes recursion can be good, sometimes it can be bad. I'd recommend getting some practice with both, and getting a feel for it. And if you ever find yourself wondering: "OK, this code works now, but is it readable? Is it clean? Is it good code?", that is what Code Review is for.

Oriol · Accepted Answer · 2015-06-22 00:25:20Z

0

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.

answered Jun 22, 2015 at 0:25

Oriol

291k71 gold badges459 silver badges535 bronze badges

Comments

Keon Cummings · Accepted Answer · 2015-06-26 05:19:34Z

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));
}

As I stated in my answer: Algorithms makes code fast or slow, not recursion. Your recursiveSolution and your iterativeSolution must be doing different things, not the same thing in different ways.

Collectives™ on Stack Overflow

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

4 Answers 4

Comments

2 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related