Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Recursive function does not iterate to next element in foreach

It seems to me that the code for the 2nd item in items is never reached in the for loop.

How to fix this method?

class Item {
  items: Item[] = [];
  constructor(public id: string) {}
}

function getItembyIdRecursively(id: string, items: Item[]): Item | undefined {
  for (const item of items) {
    if (item.id === id) {
      return item;
    } else {
      return getItembyIdRecursively(id, item.items);
    }
  }
  return undefined;
}

const item1 = new Item("1");
const item2 = new Item("2");
item1.items.push(new Item("1.2"));
const items = [item1, item2];

const foundItem = getItembyIdRecursively("2", items);

console.log(foundItem.id);

You can find a repro sample here:

sample repro link

Tags:

2

Answers


  1. 0

    The problem is your else statement, you are returning the result in all cases, even if it is undefined. Basically since the first Item has children, you return the result of search in its children, and since the id is not matched, you get undefined.

    function getItembyIdRecursively(id: string, items: Item[]) : Item  | undefined
{
  for(const item of items)
  {
    if(item.id === id)
    {
      return item;
    }
    else
    {
      const elem = getItembyIdRecursively(id, item.items);
      if(elem) {
        return elem;
      }
    }
  }
  return undefined;
}

    Which is the same as this.

    function getItembyIdRecursively(id: string, items: Item[]) : Item  | undefined
{
  for(const item of items)
  {
    if(item.id === id) return item;
    const elem = getItembyIdRecursively(id, item.items);
    if(elem !== undefined) return elem;
  }
  return undefined;
}
    Login or Signup to reply.
  2. 0

    generators

    I think generators offer a natural way to express searching or traversal functions. We can see how the generator does not need an additional if check before continuing with yield*. Another benefit is the consumer is always guaranteed a value

    function getItem(id: string, items: Item[]): undefined | Item {

  function* find(items: Item[]): Generator<Item> {
    for (const item of items) {
      if (item.id == id) yield item
      yield* find(item.items)         // unconditional
    }
  }

  for (const match of find(items))
    return match                      // unconditional
}

    class Item {
  items: Item[]
  constructor(
    public id: string,
    items?: Item[],
  ) {
    this.items = items ?? []
  }
}

const example = [
  new Item("A", [
    new Item("B", [new Item("C"), new Item("D", [new Item("E")])]),
    new Item("F"),
  ]),
]

    Run this example on typescript playground

    console.log(getItem("D", example)) // Item: { id: "D", items: [ Item: { id: "E", items: [] } ] }
console.log(getItem("X", example)) // undefined

    generic find

    Instead of embedding the generator within the getItem function, we can define find as a standalone function, independent of the Item type –

    function* find<T>(
  values: Iterable<T>,
  matchFn: (value: T) => boolean,
  recurFn?: (value: T) => Iterable<T>,
): Generator<T> {
  for (const value of values) {
    if (matchFn(value)) yield value
    if (recurFn) yield* find(recurFn(value), matchFn, recurFn)
  }
}

    Now find is reusable anywhere we need this functionality, as in getItem –

    function getItem(id: string, items: Item[]): undefined | Item {
  for (const match of find(  // find..
    items,                   // iterable
    i => i.id == id,         // match
    i => i.items,            // recur
  ))
    return match             // unconditional
}

    Run this example on typescript playground

    console.log(getItem("D", example)) // Item: { id: "D", items: [ Item: { id: "E", items: [] } ] }
console.log(getItem("X", example)) // undefined

    convenience and control: $0.99

    Generators give us all sorts of power and flexibility. getItem returns just the first result, which immediately terminates the generator and stops scanning other items. With a tiny change, we could write getItems that returns all results –

    function getItems(ids: string[], items: Item[]): Item[] {
  return Array.from(find(          // unconditional
    items,
    i => ids.includes(i.id),
    i => i.items,
  ))
}

    Run this example on typescript playground

    console.log(getItems(["E", "F"], example)) // [ Item: { id: "E" }, Item: { id: "F" } ]
console.log(getItems(["X"], example)) // []
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search