Any tips for designing a function that uses recursion?

[fuzzybabybunny]

I always have a very very difficult time thinking through recursion. For me it's just so weird to be calling the function in the definition of the function. It's hard enough for me to follow an already written recursive function, much less write one myself. And everything just goes to hell if the function starts calling itself *multiple* times in its own function definition, such as in the case of Fibonacci.

Having a loop and looping straight through from the start condition to the end condition just makes more intuitive sense to me.

I've got an array of nested objects

    var myArray = [
      {
        tires: 2,
        exterior: {
          color: 'white',
          length: 2,
          width: 1
        }
      },{
        tires: 4,
        exterior: {
          color: 'blue',
          length: 5,
          width: 3
        }
      },{
        tires: 4,
        exterior: {
          color: 'white',
          length: 2,
          width: 3
        }
      }
    ];

I want to create a function such that:

    var findItems = function(arr, value){
      // return array of found items
    };

====

    findItems(myArray, 'white');

returns:

    [{
      tires: 2,
      exterior: {
        color: 'white',
        length: 2,
        width: 1
      }
    },{
      tires: 4,
      exterior: {
        color: 'white',
        length: 5,
        width: 3
      }
    }]

=======

    findItems(myArray, 2);

returns:

    [{
      tires: 2,
      exterior: {
        color: 'white',
        length: 2,
        width: 1
      }
    },{
      tires: 4,
      exterior: {
        color: 'white',
        length: 2,
        width: 3
      }
    }]

======

    findItems(myArray, { tires: 2 });

returns:

    [{
      tires: 2,
      exterior: {
        color: 'white',
        length: 2,
        width: 1
      }
    }]

findItems(myArray, { width:1, color:'white' })

returns

      [{
        tires: 2,
        exterior: {
          color: 'white',
          length: 2,
          width: 1
        }
      }]

It's easy enough to find values for arrays with non-nested objects or if you know the exact level that you want to search in. But I'm not sure how to go about just finding "any value, anywhere" in an array that can contain any kind of object. I quickly get into looping hell and people say that recursion is where I should be heading.

I can use Underscore if that helps.

 

[smackababy]

The real question is: why are your trying to use recursion? For the most part, unless you're doing tail recursion (which isn't in Javascript), you're using more of the stack. Each recurse will create a new entry on the stack. If you're going down a huge tree, this quickly becomes a problem.

One of the major benefits is it makes code easier to follow and the algorithm in a tree a lot easier to do. In something like SCALA, it allows for a lot of one line functions.

 

[brianmanahan]

it helps with recursion to think about 2 scenarios:

1. base case, where you just return a value. this is the simple scenario.
2. recursive case, where you return a call to the same function but with more specific parameters. this is more complicated but by giving more specific parameters, you'll eventually reach the base case.

in your scenario, it looks like the base case would be if a value being searched is a primitive, not an object. and the recursive case is if the value is an object. so perhaps an algorithm something like this:

function findItems(anArray, searchParameter) {
    var matchingItems = [];
    for (var i = 0; i < anArray.length; i++) {
         if (isSearchParameterFoundInObject(anArray[i], searchParameter) {
             matchingItems.push(anArray[i]);
         }
    }
    return matchingItems;
}

// assumes searchParameter is a primitive, not an object.
// this would be a little more complicated if searchParameter was an object
function isSearchParameterFoundInObject(anObject, searchParameter) {
    var keys = Object.keys(anObject);
    var searchParamFound = false;

    for (var i = 0; i < keys.length && !searchParamFound; i++) {
       var value = anObject[key];
       if (value !== null && typeof value === 'object') {
           // recursive case - the value is an object, need to search within that object
           searchParamFound = isSearchParameterFoundInObject(value, searchParameter);
       }
       else {
           // base case - the value is a primitive, just compare the search param to that
           searchParamFound = (value === searchParameter);
       }
    }
    return searchParamFound;
}

note: i didn't actually try to run this, it was just a thought experiment.

 

[Ken g6]

For the most part, unless you're doing tail recursion (which isn't in Javascript), you're using more of the stack.

Which leads to something important. Anything you can do with recursion you can do with a stack instead.

Which means you can do something like this pseudocode for each element of the array:

Function:
  While the stack is not empty:
    Pop the next object off the stack.
    For each value in this object:
      If this value is another object, push it onto the stack.
      Else check this value against the search parameter.

Push the object to be searched onto the stack.
Call the Function.

 

[Tweak155]

I use recursion very infrequently - only when I've given something structure, such as tree nodes. You have to be careful though, if your data set is too large you'll consume a lot of processing time.

 

[K7SN]

I use recursion very infrequently - only when I've given something structure, such as tree nodes. You have to be careful though, if your data set is too large you'll consume a lot of processing time.

I use recursion all the time, especially writing complex sorts or solving regression but I try to use a language like C# where the just in time execution can sort 1,000,000 derive values pairs or triplets in a few seconds. Yes I'm a scientific programmer.

As Ken G6 stated any recursive method or function can be soled non-recursively but language limitations as Tweak155 pointed out can increase processing time to a point you start a program, go lunch and return to see if you have a solution yet! The proof is if you have infinite resources like a Turing machine you can construct anything. You don't have infinite resources. I recommend getting your algorithm book and seeking a better solution if you must use JavaScript.

While there is a way to change anything that logically is recursive, like solving the 8 queens problem, can be written non-recursively but seeking a complex solution is more than just a stack which can overflow. The last time I converted anything was to mess with a fellow adjunct professor friend (I was best man at his wedding). It took me some time to write an efficient C function to check another function for a solution. The key to solving all the 8 queens solutions is to not consume finite resources.

My friend, now a tenured professor, always assigned the 8 Queens program in Fortran. He assigned that homework problem near the end of the semester to teach that nested loops is not always the best process. The Harris Mainframe used by our students timed out if you ran a process that used enough resources (like 1 or 2 seconds of actual computer time) because some newbie fool would write a program with an endless loop and slow up a mainframe computer otherwise. Eight nested loops of 8 would time out in about 7 minutes of real time long before solving the problem.

I had another close friend who was a hardware person (Telephone snot computers) and decided he would needed to understand programming as everything was going digital (Remember this was the 1970s). He had decided to take that Fortran class. I wrote the future Fortran subroutine as a function in C and let my friend and came to me for help.

Fortran then did not support recursion; I wrote a recursive solution in C; then a duplicate non-recursive function in C and gave him my simple program. He converted it to Fortran. He wrote the function to check an 8 by 8 matrix and verify a correct solution and return a one or fail because to queens could attack each other and return a zero The assignment was to solve all solutions but without recursion you couldn't solve for a single solution.

My Hardware friend submitted the correct results and program, which wasn't supposed to happen. It took my fellow adjunct professor friend about three seconds to figure out how a solution in a basic Fortran (First computer language taught then) could get a solution. The three of us raced motorcycles together and were all licensed amateur radio hams. He was not amused at the time (Our friendship that has lasted almost 50 years and he still remembers how his whole planed lecture was ruined and he had to explain how someone got a solution) .

The method and proof to do such things was in some 70's algorithm book, maybe Knuth. I have avoided non-recursive programming languages (except Fortran) since 1975. If your using recursion is that deep, a script language like JavaScript is not the solution.

 

[purbeast0]

based on what your data set in the OP is, there is absolutely no reason to use recursion in that case.

i'm actually a bit confused by this thread since you are asking about recursion but then give us an example of an object where recursion wouldn't give you any benefit.

recursion is usually most useful when you are traversing an object of type A that could have children that are of type A or a child list of type A. it's where you basically want to say "return the value of this object or traverse it's children and get the value of the object the same way you're trying to now".

 

[fuzzybabybunny]

based on what your data set in the OP is, there is absolutely no reason to use recursion in that case.

i'm actually a bit confused by this thread since you are asking about recursion but then give us an example of an object where recursion wouldn't give you any benefit.

recursion is usually most useful when you are traversing an object of type A that could have children that are of type A or a child list of type A. it's where you basically want to say "return the value of this object or traverse it's children and get the value of the object the same way you're trying to now".

Hmmm... all the guys on Stack seem to think recursion is the answer here, because I'm traversing object nodes to find values. How would you code this in a non-recursive way?

 

[dave_the_nerd]

The only time I really use recursion is when traversing directory trees, looking for something in particular.

Example (assuming other functions also exist and without checking my syntax because it's Sunday):

def returnAllJPEGs(directoryPath):
    listOfJPEGs = list()
    getListing(directoryPath)
    for Item in getListing:
        if isJPEG(Item):
            listOfJPEGs.append(Item)
        else if isDirectory(Item):
            listOfJPEGs += returnAllJPEGs(Item)
    return listOfJPEGs

 

[purbeast0]

Hmmm... all the guys on Stack seem to think recursion is the answer here, because I'm traversing object nodes to find values. How would you code this in a non-recursive way?

with the data structure in the OP, you won't even have to call the function recursively to traverse the whole thing. you'd simply hit the for loop for 3 iterations and be done traversing the object since it has 3 items in it.

your array just looks like it's an array of "vehicles" and none of those even have any kind of child "vehicle" object so recursion just isn't necessary or even an option to traverse this list.

just because you have "nested objects" doesn't mean recursion will get you anything. it's when you have nested objects that could be of the same type where recursion can be beneficial.

 

[dave_the_nerd]

Hmmm... all the guys on Stack seem to think recursion is the answer here, because I'm traversing object nodes to find values. How would you code this in a non-recursive way?

Iterate once through the array and return all the entries that match the query?

I mean, assuming you know the structure of the parent object.

If you didn't - if you wanted to write a function that would take any and all JSON structures of any arbitrary depth, and search for certain key:value pairs, then I suppose recursion would be useful.

But since I learned recursion on computers with 512kB of RAM, I would caution you to keep track of how many layers you're going. If you want to know what happens when you dig too deep, ask the Dwarves of Moria. :biggrin:

 

[fuzzybabybunny]

Iterate once through the array and return all the entries that match the query?

I mean, assuming you know the structure of the parent object.

If you didn't - if you wanted to write a function that would take any and all JSON structures of any arbitrary depth, and search for certain key:value pairs, then I suppose recursion would be useful.

But since I learned recursion on computers with 512kB of RAM, I would caution you to keep track of how many layers you're going. If you want to know what happens when you dig too deep, ask the Dwarves of Moria.

Ah yes, well that's what I meant. The "cars" example was just for brevity. The actual array of objects could be any kind of structure, different depths, etc.

I just wanted a function that could search an array of objects (any) for instances of a value that I send in as an argument, and then bring back those matching objects as another array of objects.

 

[Ken g6]

He (presumably) needs to recurse through each object and its sub-objects. Not through the array.

 

[fuzzybabybunny]

He (presumably) needs to recurse through each object and its sub-objects. Not through the array.

Yes.

 

[purbeast0]

He (presumably) needs to recurse through each object and its sub-objects. Not through the array.

based on the object in the OP that isn't the case though.

 

[Ken g6]

based on the object in the OP that isn't the case though.

Yes, it is. One such object is:

{
        tires: 4,
        exterior: {
          color: 'blue',
          length: 5,
          width: 3
        }
      }

He needs to recurse to find values inside the "exterior" object, which is inside the outer object.

 

[fuzzybabybunny]

based on the object in the OP that isn't the case though.

Sorry, I could have been clearer. I've edited the lower part of the OP to state any array containing any kind of object.

Basically a universal filter function for any kind of array of objects.

 

[purbeast0]

Sorry, I could have been clearer. I've edited the lower part of the OP to state any array containing any kind of object.

Basically a universal filter function for any kind of array of objects.

still not sure what you are trying to do based on your sample data. you can't really write a "universal function" that will just traverse an object or array.

or if you are literally just trying to look at every item in an array and traverse it, then just use underscores _.each instead of the headache of writing your own.

 

[purbeast0]

Yes, it is. One such object is:

{
        tires: 4,
        exterior: {
          color: 'blue',
          length: 5,
          width: 3
        }
      }

He needs to recurse to find values inside the "exterior" object, which is inside the outer object.

he doesnt though according to that sample data. just iterate over the array and check the exterior object on each iteration. in his sample data, "exterior" is not the same type as his objects in the array.

 

[fuzzybabybunny]

Here's the function that someone on Stack wrote that goes through an array of objects and finds stuff. It works in every example in the OP. It doesn't seem to search through prototypical properties, which is fine, and it will ignore null values.

Unfortunately, when I look at it, it boggles my mind.

var findInArray = function(arr, value){

  var isObject = function(val) {
    return typeof val === 'object';
  };

  var search = function(val, ctx) {

    var valIsObject = isObject(val);

    return (function search(context) {
      if(context){
        if(!isObject(context)){
          return val === context;
        };

        if(valIsObject && Object.keys(val).every(function(key) {
          return context[key] === val[key];
        })){
          return true;
        };

        return Object.keys(context).some(function(key) {
          return search(context[key]);
        });
      };
    })(ctx);
  };

  return arr.filter(function(item) {
      return search(value, item);
  });

};

 

[smackababy]

still not sure what you are trying to do based on your sample data. you can't really write a "universal function" that will just traverse an object or array.

or if you are literally just trying to look at every item in an array and traverse it, then just use underscores _.each instead of the headache of writing your own.

The best you could do is have a function that simply "handles" the head of an array and then recurse with the fail.

function(array) {
  if (array.isEmpty) {
    end condition 
  }
  else {
    do your stuff on array.head (possibly check for inner objects and simply call function on those)
    function(array.tail)
  }
}

But, even that isn't truly "universal". I guess you could do something where you pass in a function to do things to, and that would be a bit more universal.


Fuzzy, you're looking at complex examples without seemingly basic understanding of what is happening.

Take this for example:

myFunc(BranchOrLeaf) {
  if(Leaf) {
    return someValue
  }
  if(Branch) {
    return myFunc(_.left) + myFunc(_.right)
  }
  //some escape condition if neither here
}

var answer = myFunc(topOfTree)

Now, this won't compile and run, as it is mostly pseuocode, but it just illustrates recursion on a tree.

 

[mikeliddell]

Recursion is a nice was to both describe and implement an algorithm where you have an obvious way to simplify one step at a time.

If this case:
1. Simple case is you have an element that is a plain value
2. Hard case is you have an object that contains other things. So the simplification if to list the inner things and then call f() for each

F(node, x)
If node is simple, return node.equals(x)
Else: for each element m in node: if f(m, x) return true
//if get to end of function then none of the inner elements matched, so return false
Return false

Recursion has some costs associated with it but if you can show the total depth of recursion is less than a few hundred calls then basically all languages/run times will be fine. In this case he depth is limited by the maximum amount of nesting .. Having input with nesting depth of 100s seems very unlikely hence no issues.

 

[purbeast0]

Here's the function that someone on Stack wrote that goes through an array of objects and finds stuff. It works in every example in the OP. It doesn't seem to search through prototypical properties, which is fine, and it will ignore null values.

Unfortunately, when I look at it, it boggles my mind.

var findInArray = function(arr, value){

  var isObject = function(val) {
    return typeof val === 'object';
  };

  var search = function(val, ctx) {

    var valIsObject = isObject(val);

    return (function search(context) {
      if(context){
        if(!isObject(context)){
          return val === context;
        };

        if(valIsObject && Object.keys(val).every(function(key) {
          return context[key] === val[key];
        })){
          return true;
        };

        return Object.keys(context).some(function(key) {
          return search(context[key]);
        });
      };
    })(ctx);
  };

  return arr.filter(function(item) {
      return search(value, item);
  });

};

just remember that the "findInArray" function isn't actually recursive. it's using recursion down inside, but that function can't be called recursively in the example you posted from stackoverflow.

now that it really matters, just pointing that out to you.

i was under the impression that you were looking for a top level "findInArray" recursive function, which is why i was saying it's not necessary with the example dataset you posted, and that just traversing the list was all you needed to do.

 

[BoberFett]

N/M, it's been covered.