javascript - 使用 javascript 深度优先搜索 : cannot get the record I want

Question

我很难理解递归的工作原理。我有这个文字对象:

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},
            ]

        },

    },  

}

而且我想实现一个系统，该系统通过他的 ID 检索存储在数据数组中的特定记录返回给我。

现在，由于数据数组存储在树的末尾，我想使用 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))

我从 'pizze' 对象开始，一直向下直到存储在 typeOne 对象中的数据，然后转到存储在 typeTwo 中的数据，依此类推...

但是这个方法行不通，我每次都是假的...我想我还不明白那里发生了什么，递归函数中的调用堆栈是如何工作的..

另外我的目标是:当你找到记录时，返回它并退出。这is not possible with ForEach ，所以我选择了具有不同策略的经典 for 循环:

    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

如您所见，我尝试在外部作用域中声明一个变量，当我在循环中找到我想要的对象时，我将其分配给记录，然后退出循环，但记录仍未定义。

如果我在最内部的 if 中执行 console.log()，我实际上已经在控制台上打印了我想要的值。但似乎中断不起作用

我错过了什么？谁能解释一下为什么我的两种方法不起作用，最重要的是，递归期间会发生什么？

非常感谢

Answer 1

也许使用迭代器来简化它:

  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;

---

或者在更一般的情况下:

   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;