How to fix the error when working with recursion and array?

Question

I'm trying to solve a problem - need to return an array after entering a value to search. The depth of an array can be theoretically infinite. So I'm recursing to find suitable elements among any depth level and add them to the array and then return this array. But this code does not work as expected. I can't figure out what exactly I did wrong here.

const newList = [
  {
      role: "role111",
      title: "title1",

  },
  {
      role: "role222",
      title: "title2",
  },
  {
      role: "role333",
      title: "title3",
  },
  {
      role: "role444",
      title: "title4",
      items: [{
          role: "role555",
          title: "title5",
      }, {
          role: "role666",
          title: "title6",
      }, {
          role: "role777",
          title: "title7",
          items: [{
              role: "role888",
              title: "title888",
          },{
              role: "role8888",
              title: "title8888",
          },]
      },]
  },
  {
      role: "role999",
      title: "title999",
  },
];

const text = "role888";


const testFunction = (
  list,
  text,
  emptyArray
) => {
  let arrayForRender = emptyArray;

  return list?.filter((item) => {
      if (item.title.toLowerCase().includes(text.toLowerCase())) {
          arrayForRender = [...arrayForRender, item];
          return arrayForRender;
      }
      if (item.items && item.items?.length > 0) {
          testFunction(item.items, text, arrayForRender);
      }
  });
};

console.log(testFunction(newList, text, []));

P.S. I'm so sorry, but my question was originally formulated incorrectly and it is no longer relevant. But thanks to everyone who suggested and will tell you how to work with recursion correctly!

@user16320675 ok, thanks! i will delete this link – Jul 14 '22 at 10:17 — , Jul 14 '22 at 10:17

Woodsy · Answer 1 · 2022-07-14T14:01:31.917

I don't think the filter method will work here, instead try the forEach method to loop through the array and push found items into your arrayForRender. Also I noticed in your code that your search text is a role but your condition looks at the title.

const testFunction = (
  list,
  text,
  arrayForRender
 ) => {
 list.forEach((item) => {
    if (item.items && item.items?.length > 0) {
       testFunction(item.items, text, arrayForRender);
     } 
    if (item.role.toLowerCase().includes(text.toLowerCase())) {
       arrayForRender.push(item);  
       //arrayForRender.push({'role':item.role, 'title':item.title})
     } 
  });
  return(arrayForRender)
};

console.log("search results:",testFunction(newList, text,[]));

based on your comment below, here is code that returns only the top level node if it matches the search or any of its children match the search:

const testFunction = (
  list,
  text
) => {
  return list?.filter((item) => {
    if (item.items && item.items?.length > 0) {
        return testFunction(item.items, text);
    }

    return item.role.toLowerCase().includes(text.toLowerCase());
  });
};


console.log("search results:",testFunction(newList, text));

Thanks a lot for your help! In fact, I just recently realized that solving a problem through recursion may not be ideal for me. Since it is necessary to return not just matches, but only the topmost parents if there are matches in children. So my question is just wrong. But thanks a lot for your suggestion! I understood recursion even better thanks to him — , Jul 14 '22 at 13:07
@Timofeus91 I included a way to return only the top item if its child matches your search — Woodsy, Jul 14 '22 at 13:23
with my real array, this option, unfortunately, did not work. I don't know what the problem is, but it produces an incorrect array in total. Always at least 7 elements. But with the array that I gave above, it works out fine. Thanks a lot! — , Jul 14 '22 at 15:33

Scott Sauyet · Accepted Answer · 2022-07-14T18:57:58.097

If I understand your updated requirements, then we can write a simple generic deep filtering function that shows all the elements that match a predicate or which have (recusively nested) descendants that match it.

We can configure this with a function that tests whether the title matches a query string. It might look like this:

const filterDeep = (pred) => (xs) =>
  xs .filter (x => pred (x) || filterDeep (pred) (x .items || []) .length > 0)

const titleMatch = (query) => filterDeep (
  ({title}) => title .toLowerCase () .includes (query .toLowerCase ())
)


const newList = [{role: "role111", title: "title1"}, {role: "role222", title: "title2"}, {role: "role333", title: "title3"}, {role: "role444", title: "title4", items: [{role: "role555", title: "title5"}, {role: "role666", title: "title6"}, {role: "role777", title: "title7", items: [{role: "role888", title: "title888"}, {role: "role8888", title: "title8888"}]}]}, {role: "role999", title: "title999"}];

['title2', '888', 'itl'] .forEach (
  query => console .log (`"${query}"`, ':', titleMatch (query) (newList) .map (x => x .title))
)

.as-console-wrapper {max-height: 100% !important; top: 0}

(Note that the result is the actual original nodes, but here we display only their titles.)

I think this is simple code, and filterDeep is quite likely usable elsewhere.

Update

So clearly, I didn't get the requirement. If I'm now correct, and you want the full object hierarchy for any nodes that match the predicate, then this version should do, which simply has a different implementation of filterDeep:

const filterDeep = (pred) => (xs) =>
  xs .flatMap (({items = [], kids = filterDeep (pred) (items), ...rest}) =>
    pred (rest) || kids.length
      ? [{...rest, ...(kids.length ? {items: kids} : {})}]
      : []
  )

const titleMatch = (query) => filterDeep (
  ({title}) => title .toLowerCase () .includes (query .toLowerCase ())
)


const newList = [{role: "role111", title: "title1"}, {role: "role222", title: "title2"}, {role: "role333", title: "title3"}, {role: "role444", title: "title4", items: [{role: "role555", title: "title5"}, {role: "role666", title: "title6"}, {role: "role777", title: "title7", items: [{role: "role888", title: "title888"}, {role: "role8888", title: "title8888"}]}]}, {role: "role999", title: "title999"}];

['title2', '888', 'itl'] .forEach (
  query => console .log (`"${query}"`, ':', titleMatch (query) (newList))
)

.as-console-wrapper {max-height: 100% !important; top: 0}

We use flatMap here as a way to filter and map in one go. If the item does not match, we return an empty array; if it does, then we return an array containing just its transformed value.

I really like your solution! But I need, in a real task, not just to return the title, but to return all the parents above. That is, if there is a match in some items object, you need to return not it, but its parent (the object in the items of which the object with the match was located) of everything. And if he had a parent, then even higher and so endlessly — , Jul 14 '22 at 15:08
We return the entire objects, but log only their titles to the console. But you want the whole hierarchy up to and including the found object(s)? That's a different task than I understood, where I thought you wanted just the root nodes. I've done that before, and I'll try to dig up an example soon. — Scott Sauyet, Jul 14 '22 at 16:02
Do you simply want to retain the same tree structure, but keeping only those parts of the hierarchy which include something matching your condition? Or do you want to flatten it in some way? What about descendants of a matching node? Do you want them if they themselves don't match? — Scott Sauyet, Jul 14 '22 at 16:04
Added an update that *may* do what you want. It's a minor tweak of [an earlier answer](https://stackoverflow.com/a/65442868/1243641) to a related question. — Scott Sauyet, Jul 14 '22 at 18:59
It's something great. The code works, but I haven't figured out how or why yet. I study your function. Thanks a lot for your help! Thanks to your function, I have already learned several interesting solutions for myself in writing code, and I have not even figured out this function to the end until now. Thank you! — , Jul 27 '22 at 12:58
I have only one question - what is "pred" in filterDeep? I understand that xs is Array, but I can`t understand what "pred" — , Jul 27 '22 at 13:27
It's my usual abbreviation for a predicate function, a function that returns a boolean, to indicate if some condition is true. — Scott Sauyet, Jul 27 '22 at 13:28

How to fix the error when working with recursion and array?

2 Answers2

Update