递归浅析

js中一些递归的demo

递归的简单入门

数字递归(最简单)

// 加法的递归
function sum(num){
    if (num === 0) {
        return 0;
    } else {
        return num + sum(--num)
    }
}
sum(4); // 10

// 再来一个阶乘的递归
function fn(num) {
  if(num === 1) {
    return 1;
  }else {
    return num*fn(num-1)
  }
}
fn(5) // 120

数组递归

// 数组中的各个元素相加之和
function fn(arr) {
  if(arr.length === 1) {
    return arr[0];
  }else {
    var val = arr.shift();
    return val + fn(arr);
  }
}
fn([1,2,3,4,6,5,7,8,9,10]) // 55

// 将嵌套的多维数组转成一维数组
var arr = [1,2,3,[4,5,6,[7,[8,[9,10]]]],11,[12]];
function transformArr(arr) {
  var newArr = [];
  recursiveArr(arr, newArr);
  return newArr;
}
function recursiveArr(arr, newArr) {
  arr.forEach(function(item) {
    if(item instanceof Array) {
      recursiveArr(item, newArr);
    }else {
      newArr.push(item);
    }
  });
}
console.log(transformArr(arr), '@_@');
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

// 一维数组，元素都是对象，互相有父子关系，将这些数组转换成父子结构的对象格式
// 数据，parentId是其父节点的id 
var data = [
  {
    name: '数据1',
    id: 11,
    parentId: 1
  },
  {
    name: '数据2',
    id: 12,
    parentId: 11
  },
  {
    name: '数据3',
    id: 13,
    parentId: 11
  },
  {
    name: '数据4',
    id: 14,
    parentId: 12
  },
  {
    name: '数据5',
    id: 15,
    parentId: 13
  },
  {
    name: '数据6',
    id: 16,
    parentId: 15
  },
  {
    name: '数据7',
    id: 17,
    parentId: 16
  },
  {
    name: '数据8',
    id: 18,
    parentId: 16
  },
];
// transformData这个函数是辅助生成对象的函数
function transformData(data, parentId) {
  var obj = {
    children: []
  };
  generaterTree(data, obj, 1);
  return obj;
}
// generaterTree这个函数是递归调用的核心函数
function generaterTree(data, obj, parentId) {
  data.forEach(item=> {
    item.children = item.children?item.children:[];
    if(item.parentId === parentId) {
      obj.children.push(item);
      generaterTree(data, item, item.id); // 继续递归回调
    }
  });
} 
console.log(transformData(data));

对象的递归

对象的递归里边也包含了数组等的一些基础型数据，常用的就是对象的深拷贝

var data = {
  "name": "jinux",
  "like": ["football","basketball","voliball"],
  "work": {
    "company": "technology",
    "address": "hunnan",
    "tongshi": ["lining","lvnan"],
    "isLeader": false
  }
}
function deepClone(data) {
  if(typeof data !== 'object') {
    return data;
  }
  if(data === null) {
    return data;
  }
  var obj = Object.prototype.toString.call(data)==='[object Array]'?
            []:{};
  for(var key in data) {
    obj[key] = arguments.callee(data[key]);
    // obj[key] = deepClone(data[key]); 与上边的一个意思
  }
  return obj;
}
console.log(deepClone(data), "<->");

常用递归demo

demo所使用数据

const data = [
  {
    id: 1,
    name: 'A',
    type: 'admin',
    children: [
      {
        id: 2,
        name: 'A_1',
        type: 'admin',
        children: [
          {
            id: 3,
            name: 'A_1_1',
            type: 'user',
          }
        ]
      },
      {
        id: 4,
        name: 'A_2',
        type: 'user',
      },
    ]
  },
  {
    id: 5,
    name: 'B',
    type: 'admin',
    children: [
      {
        id: 6, 
        name: 'B_1',
        type: 'user',
        children: [
          {
            id: 7,
            name: 'B_1_1',
            type: 'admin',
          }
        ]
      }
    ]
  }
]

深度优先遍历

通过id查节点

const tree = (root, id) => {
  if (!root || !root.length)  return;

  for (const item of root) {
    if (id === item.id){
        return item;
    }
    const find = tree(item.children, id)
    if (find) return find;
  }
}

广度优先遍历

通过id查节点

const tree = (root, id) => {
  if (!root || !root.length)  return

  for (const item of root) {
    if (id === item.id){
      return item
    }
  }

  const childrens = root.reduce((total, current) => {
    return total.concat(current.children || [])
  },[])

  return tree(childrens, id)
}

打平树形结构

// 方法一
const flatten = (tree) => {
  let list = []
  tree.forEach(node => {
    const {children, ...obj} = node
    list.push(obj)
    if (children && children.length){
      const tempList = flatten(children)
      list.push(...tempList)
    }
  })
  return list
}

// 方法二
const flatten = (tree) => {
  return (tree|| [ ]).reduce((total, current) => {
  const {children, ...obj} = current
    return total.concat(obj, flatten(children))
  }, [])
}

根据id获取父节点

function findParentByChildId(data, id, list, parent) {
  for(let i=0; i<data.length; i++) {
    let item = data[i];
    if(item.id==id&&parent) list.push(parent);
    if(item.children&&item.children.length) {
      findParentByChildId(item.children, id, list, item);
    }
  }
  return list[0] || null;
}

findParentByChildId(data, 3, [], null);

深度过滤

const formatTree = (root) => {
  return (root || []).filter(node => node.type === 'admin').map(node => {
    const { children } = node
    return {
      ...node,
      children: formatTree(children)
    }
  })
}
// 只保留type是admin的节点