depth first search with javascript: cannot get the record I want

Question

I have some difficulty to understand how recursion works. I have this literal object:

let obj = {
    pizze:{
        type:"pizze",
        typeOne:{
            title: "Pizze Rosse",
            data:[
                {id:1,type:"pizza",name:"Margherita",price:4,ingredients:["pomodoro","mozzarella"],quantity:0,inventory:100},
                {id:2,type:"pizza",name:"Marinara",price:3.5,ingredients:["aglio","pomodoro"],quantity:0,inventory:100},
                {id:3,type:"pizza",name:"Salsiccia e funghi",price:6,ingredients:["salsiccia","funghi","mozzarella","pomodoro"],quantity:0,inventory:100},
                {id:4,type:"pizza",name:"Carciofi",price:4,ingredients:["mozzarella","carciofi","pomodoro"],quantity:0,inventory:100},  
            ]
        },
        typeTwo:{
            title:"Pizze Bianche",
            data:[
                {id:5,type:"pizza",name:"Gorgonzola e noci",price:5.50,ingredients:["gorgonzola","noci","mozzarella"],quantity:0,inventory:100},
                {id:6,type:"pizza",name:"Stracchino e rucola",price:4.50,ingredients:["stracchino","rucola","basilico"],quantity:0,inventory:100},
                {id:7,type:"pizza",name:"Tartufo e salsiccia",price:8,ingredients:["tartufo","salsiccia","mozzarella"],quantity:0,inventory:100},
                {id:8,type:"pizza",name:"Zucchine e Gamberi",price:5,ingredients:["zucchine","gamberi","pomodorini"],quantity:0,inventory:100},
            ]

        }
    },
    primiPiatti:{
        type:"primiPiatti",
        typeOne:{
            title: "Primi di carne",
            data:[
                {id:12,type:"primiPiatti",name:"Lasagne alla Bolognese",price:9,quantity:0,inventory:100},
                {id:13,type:"primiPiatti",name:"Spaghetti alla carbonara",price:14,quantity:0,inventory:100},
                {id:14,type:"primiPiatti",name:"pennette all'amatriciana",price:10,quantity:0,inventory:100},
                {id:15,type:"primiPiatti",name:"paccheri salsiccia e funghi",price:12,quantity:0,inventory:100},  
            ]
        },
        typeTwo:{
            title:"Primi di pesce",
            data:[
                {id:16,type:"primiPiatti",name:"spaghetti allo scoglio",price:8.50,quantity:0,inventory:100},
                {id:17,type:"primiPiatti",name:"zuppa di cozze",price:14.50,quantity:0,inventory:100},
                {id:18,type:"primiPiatti",name:"pappardelle asparagi e gamberi",price:18,quantity:0,inventory:100},
                {id:19,type:"primiPiatti",name:"lasagne al salmone",price:15,quantity:0,inventory:100},
            ]

        },
        typeThree:{
            title:"Primi vegetariani",
            data:[
                {id:20,type:"primiPiatti",name:"Potage di cavolfiori e porri",price:15.50,quantity:0,inventory:100},
                {id:21,type:"primiPiatti",name:"lasagne con patate e taleggio",price:14.50,quantity:0,inventory:100},
                {id:22,type:"primiPiatti",name:"crespelle formaggio e zucca",price:12,quantity:0,inventory:100},
                {id:23,type:"primiPiatti",name:"cannelloni coste e noci",price:15,quantity:0,inventory:100},
            ]

        },
    },
    secondiPiatti:{
        type:"secondiPiatti",
        typeOne:{
            title: "secondi di carne",
            data:[
                {id:24,type:"secondiPiatti",name:"agnello al forno con patate",price:9,quantity:0,inventory:100},
                {id:25,type:"secondiPiatti",name:"arrosto di vitello",price:12.5,quantity:0,inventory:100},
                {id:26,type:"secondiPiatti",name:"coniglio al forno",price:11,quantity:0,inventory:100},
                {id:27,type:"secondiPiatti",name:"vitello al tonno",price:12.5,quantity:0,inventory:100},  
            ]
        },
        typeTwo:{
            title:"secondi di pesce",
            data:[
                {id:28,type:"secondiPiatti",name:"seppie con piselli",price:8.5,quantity:0,inventory:100},
                {id:29,type:"secondiPiatti",name:"orata al forno",price:14.5,quantity:0,inventory:100},
                {id:30,type:"secondiPiatti",name:"filetto di merluzzo al forno",price:18.5,quantity:0,inventory:100},
                {id:31,type:"secondiPiatti",name:"calamari ripieni",price:16,quantity:0,inventory:100},
            ]

        },
        typeThree:{
            title:"secondi vegetariani",
            data:[
                {id:32,type:"secondiPiatti",name:"parmigiana di melanzane",price:9.50,quantity:0,inventory:100},
                {id:33,type:"secondiPiatti",name:"polpette di verdure",price:7.50,quantity:0,inventory:100},
                {id:34,type:"secondiPiatti",name:"frittata di asparagi",price:7,quantity:0,inventory:100},
                {id:35,type:"secondiPiatti",name:"burger di patate",price:12,quantity:0,inventory:100},
            ]

        },

    },  

}

And I want to implement a system that returns to me a specific record stored in the data array, retrieving by his ID.

Now, since the data arrays are stored at the end of the tree, I have thought to use deepth first search

I not use much recursion, so I'm having some trouble with that.

My first attempt was this, I put a counter so I can see what happens and seems that yes, is a deepth first search:

let i = 0;

let search = (where, haystack,id,record=null) =>{
        Object.keys(haystack).forEach(key=>{ // loop over the key of the main object
        console.log("point",i,key)
        if(key === where){ //if key === data
          console.log("inside the data",i)
                    let record = haystack[key].find(rec => rec.id === id ); //find the record I want
                    if(record){ // if exist
                        return record   //return it
                    } 
                  }
       else if(typeof haystack[key] === 'object'){ // else repeat the procedure with subobject
                    return search(where, haystack[key],id,record); 
                  }  
      })
      i++
      return false
    }

console.log(search('data',obj,23))

I start from 'pizze' object and I go down until the data stored in typeOne object, then I go to the data stored in typeTwo and so on...

But this method not works, I get false everytime... I think I'm not understand yet what happens there, how works the call stack in a recursion function..

Also my goal is: when you find the record, return it and exit. This is not possible with ForEach, so I opted for a classic for loop with a different strategy:

    let record;

    let search2 = (where, haystack,id) =>{
    let keys = Object.keys(haystack);
    for(let i=0; i<keys.length;i++){
        if(keys[i] === where){
            record = haystack[keys[i]].find(rec => rec.id === id );
            if(record){ 
                console.log(record) // I have the record assigned 
                break
            }
        }    
       if(typeof haystack[keys[i]] === 'object'){
        search2(where, haystack[keys[i]],id,record)
        }
    }
    return false
}





    console.log(search2('data',obj,24)) // return false but is ok
    console.log("record: ",record) //undefined

As you can see, I tried with declaring a variable in the outer scope, when I found the object I want inside the loop, I assign it to the record and then I I exit from the loop, but record is still undefined.

If I do a console.log() inside the most inner if, I actually have the value I want printed out on the console. But then seems the break not working

What am I missing? Can someone explain me why my two methods are not working and, most important, what happens during recursion?

many thanks

Answer 1

OK, finally I think I get what was the problem, in the first function:

if(key === where){

     let record = haystack[key].find(rec => rec.id === id ); 
                    if(record){ 
                        return record
                    } 
                  }

Record is constantly reassigned I think, so what I need is something that keep track the result, for example an array:

let search = (where, haystack,id,found=[]) =>{
        Object.keys(haystack).forEach(key=>{ 
        if(key === where){
                    let record = haystack[key].find(rec => rec.id === id );
                    if(record){
                        found.push(record)
                        return found    //return found to the next caller
                    } 
                  }
       else if(typeof haystack[key] === 'object'){
                    return search(where, haystack[key],id,found); 
                  }  
      })

      return found[0] //finally return the record I want
    }

If the record exist inside the collection, is pushed into the found array, that is passed as argument to the next caller, but the next caller doesn't reassign it, simply upgrade the found array and return it to the next caller.

I hope I understood was what the problem in the first case. Someone can confirm?

Of course in this case I have to iterate over the entire collection, but at least I think I understand why the first search function was not working

Answer 2

Maybe use an iterator to simplify it:

  function* flatPizza() {
     for(const type of ["typeOne", "typeTwo", "typeThree"])
       yield* obj.pizze[type].data.values();
  }

 for(const el of flatPizza())
   if(el.id === 23) return el;

---

Or in a more general case:

   function* flatIterate(sth) {
     if(Array.isArray(sth)) {
          for(const el of sth)
             yield* flatIterate(el);
     } else if(typeof prop === "object") {
           yield obj;
           yield* flatIterate(Object.values(obj));
     }
  }

  for(const el of flatIterate(obj))
    if(el.id === 23) return el;