前端算法

1. 常用算法： dfs-深度优先查找, bfs-广度优先查找
2. 数组查找
3. 链表查找

深度优先查找(dfs)

1. 常见场景：多维数组递归查找， 调用栈

递归

1. 递归定义：调用自身函数
2. 条件：递归条件(继续调用自身的条件)、基线条件(不继续递归的条件)
3. 递归优化用法：尾递归

示例

1. 递归

   function recursionFun(i) {
      //基线条件
      if(i>10){
        console.log("结束递归");
        return i;
      }
      //递归条件
      if (i) {
        i++;
        console.log(i)
        recursionFun(i)
      }else{
        console.log('error')
      }
      return i
    }

2. 尾递归

   function recursionFun(arr, result) {
      //基线条件
      if(!arr.length){
        console.log("结束递归");
        return result;
      }
      //递归条件
      if (arr[0]?.children?.length) {
        result.push([...arr[0].children])
        arr.shift()
        recursionFun(arr, result)
      }else{
        console.log(arr[0])
      }
      return result
    }

调用栈

1. 定义： 同栈的概念(压入、弹出)
2. 特点： 栈很高，容易占用大量的内存

迭代

 function* logArr(currArr) {
    while (currArr.length) {
      yield console.log({currArr});
      yield currArr.shift()
    }
  }
  const logObj = logArr(['1','3','7','55'])
  logObj.next()

广度优先查找(bfs)

1. 优先在顶点中查找，然后弹出顶点，直到查找到目标

示例

const arr = [
  {
    id: "1",
    na: "no1",
    children: [
      {
        id: "1-1",
        na: "no1-1",
        children: [{ id: "1-1-1", na: "no1-1-1" }],
      },
    ],
  },
  {
    id: "2",
    na: "no2",
    children: [{ id: "2-1", na: "no2-1", children: [] }],
  },
];
function SearchInBreadth (arr){
  const result = [];
  const queue = [];
  if(!queue)return result;
  queue.push(...Arr);
  while (queue.length) {
    //取顶点
    const firstNode = queue.shift();
    /* 查找目标元素的条件 */
    result.push(firstNode);
    /* 查找目标元素的条件 end*/
    //将叶子节点加入队列
    queue.push(...(item.children ?? []))
  }
  return result;
}
const result = SearchInBreadth(arr);
console.log({ result });