How step through elements of an Array or properties of an Object for Recursion Functions

user_13097767 0
Viewed 79

I apologize if this is a dumb question. I can't really find any resources via google that go through this topic. I don't understand how to step through an array of properties of an object in a recursion function since by definition a recursion will loop through itself. I know how to iterate through an array without a for loop in a recursion. What I don't understand is how to loop through an object for a Recursion. This is just some code I made up to demonstrate my lack of understanding.

var input1 = [1, 2, 3, 4, 5];
var input2 = {1: 'a', 2: 'b', 3: 'c'};

//for arrays
var arrayRecursion = function(someArray) {
  var result = [];

  //base case
  if (someArray.length === 0) {
    return result;
  } else {
    result.push(someArray.slice(0, 1));
    return result.concat(arrayRecursion(someArray.slice(1)));
  }
}

//for objects trying to copy input into results
var objectRecursion = function(someObject) {
  var result = {};

  for (var value in someObject) {
  //base case
  if (typeof(someObject[key]) !== 'object') {
      return result;
  }
  //recursion
  }
}

The main question I have is for my object recursion. If I have an established for - in loop for an object. How does it ever iterate through it? I don't have a recursion filled in because I have no clue how to approach this. If I call the recursion for the object, does it move onto the next property of the object? If so, how? Wouldn't you be starting the for - in loop all over again from the start? I guess where my logic lies is that the for loop is NOT continued from every recursion called because it executes the function which starts the loop from the first property

recursion object javascript
3 Answers

for..in loops iterate over properties, not values - (var value in someObject) will be quite misleading and result in bugs.

Once you have a reference to a value of the object, check whether it's an object or not. If it's an object, call the recursive objectRecursion and assign the result to the result object at the same property. (Don't return at this point, since that'll terminate the function)

Note that typeof is a keyword, not a function - don't put parentheses after it.

A related issue is that null's typeof is object too, so you'll have to compare against that as well.

var input2 = {1: 'a', 2: 'b', 3: 'c', foo: { prop: 2 }};

const objectRecursion = (someObject) => {
  const result = {};
  for (const [key, value] of Object.entries(someObject)) {
    result[key] = typeof value === 'object' && value !== null
      ? objectRecursion(value)
      : value;
  }
  return result;
};
console.log(objectRecursion(input2));

For a more flexible function which handles and copies arrays as well:

var input2 = {1: 'a', 2: 'b', 3: 'c', foo: { prop: 2, prop2: [3, 4, 5, { nested: 'nested' }] }};

const objectRecursion = (someItem) => {
  if (typeof someItem !== 'object' && someItem !== null) {
    return someItem;
  }
  if (Array.isArray(someItem)) {
    return someItem.map(objectRecursion);
  }
  const result = {};
  for (const [key, value] of Object.entries(someItem)) {
    result[key] = objectRecursion(value)
  }
  return result;
};
console.log(objectRecursion(input2));

user_95152070

My experience with using recursion with Objects has mainly been with recursing through nested objects rather than through sets of keys and values on the same object. I think this is because recursion as a pattern lends itself naturally to things that are fractal -- that is, where the data being operated on at each level of recursive depth is structurally similar.

Trees are a great example of this. Suppose I have a tree of node objects with the following structure:

4 - 8 - 9
|   |
2   5 - 7
|
1

As a JS object, it might look like this.

{
  val: 4,
  left: {
    val: 2,
    left: {
      val: 1
    }
  },
  right: {
    val: 8,
    left: {
      val: 5,
      right: {
        val: 7
      }
    },
    right: {
      val: 9
    }
  }
}

Notice how if I were to look at the object representing the left or right node from the root, it's structured the same as its parent? They're each effectively their own tree, but combined into a larger tree (this is what I mean by fractal).

If you wanted to find the largest value in this tree, you could do so by using recursion to iterate through the branches.

const getLargest = function (node) {
  return Math.max(node.val, getLargest(node.left), getLargest(node.right));
};

That said, it's totally possible to use recursion on smaller and smaller sets of key-value pairs within an object. It might look something like this:

const exampleObject = {
  a: 1,
  b: 2,
  c: 3
};

const recurse = function(obj) {
  const keys = Object.keys(obj);
  const firstKey = keys[0];
  console.log(obj[firstKey]); // Or whatever; do a thing with the first key-value pair.

  const smallerObj = Object.assign({}, obj); // Create a clone of the original; not necessary, but probably a good idea.
  delete smallerObj[firstKey]; // Remove the key that we've just used.
  recurse(smallerObj);
};

It's a little less natural in JS, but still totally doable. JavaScript object keys aren't sorted, but you could add a sort to const keys = Object.keys(obj) if you wanted to run through the keys in some specific order.

user_50220440

This should work recursively, using apply

https://jsfiddle.net/cz1frnL8/

var o = {1: 'a', 2: 'b', 3: 'c', foo: { prop: 2, prop2: [3, 4, 5, { nested: 'nested' }] }};


function process(key,value) {
    console.log(key + " : "+value);
}

function traverse(o,func) {
    for (var i in o) {
        func.apply(this,[i,o[i]]);  
        if (o[i] !== null && typeof(o[i])=="object") {
             traverse(o[i],func);
        }
    }
}

traverse(o,process);
user_7916000
Related