关于javascript:递归算法

43次阅读

共计 2926 个字符，预计需要花费 8 分钟才能阅读完成。

程序调用本身的编程技巧称为递归（recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或阐明中有间接或间接调用本身的一种办法，它通常把一个大型简单的问题层层转化为一个与原问题类似的规模较小的问题来求解，递归策略只需大量的程序就可形容出解题过程所须要的多次重复计算，大大地缩小了程序的代码量。递归的能力在于用无限的语句来定义对象的有限汇合。一般来说，递归须要有边界条件、递归后退段和递归返回段。当边界条件不满足时，递归后退；当边界条件满足时，递归返回。

留神：递归是有进口的，没有进口就会造成内存溢出。

给你讲一个故事就明确了，什么故事呢？

  从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的是从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的是从前有座山...

这时候必须须要给讲故事的人限定一个完结值，比方第十次提到小和尚时完结该故事（否则就是一个死递归），这就是一个典型的递归。

有一组多级嵌套数据，用于生成一个树形组件，数据蕴含 label，id，children 属性，每一个数据 id 值都不同，这时已知一个固定 id，须要查找出这个 id 对应的 label 值，就能够用到递归。

例如：后盾返回以下数据结构：

[{
  label: '一级 1',
  id: 1,
  children: [{
    label: '二级 1-1',
    id: 2,
    children: [{
      id: 3,
      label: '三级 1-1-1'
    }]
  }]
}, {
  label: '一级 2',
  id: 4,
  children: [{
    label: '二级 2-1',
    id: 5,
    children: [{
      id: 6,
      label: '三级 2-1-1'
    }]
 }, {
    label: '二级 2-2',
    id: 7,
    children: [{
      id: 8,
      label: '三级 2-2-1'
    }]
 }]
}, {
  label: '一级 3',
  id: 9,
  children: [{
    label: '二级 3-1',
    id: 10,
    children: [{
      id: 11,
      label: '三级 3-1-1'
    }]
 }, {
    label: '二级 3-2',
    id: 12,
    children: [{
      id: 13,
      label: '三级 3-2-1'
    }]
  }]
}]

前端须要获取 id=12 时的 label，这时你会怎么做？

const data = 该数据
let label = ''
const recursionFn = (currentData) => {
  currentData.forEach(item => {if (item.id === 12) { 
      label = item.label
      return
    }
    item.children && recursionFn(item.children)
  })
}

recursionFn(data)
console.log(label)

进阶：合并对象：

有两个对象，其中

a 对象为：

 const a = {
  name: 'a', 
  children: false,
  color: '#ccc',
  attribute: {
    label: '测试',
    text: 'age',
    attributes: {js: false}
  }
}

const b = {
  name: 'b', 
  children: true,
  age: 30,
  color: '#ccc',
  attribute: {
    label: '默认',
    text: '默认',
    attributes: {
      js: true,
      json: false
    }
  }
}

此时须要将 a 和 b 的属性以及其上面的所有属性进行合并，失去的对象必须含有 a 和 b 的所有属性，但如果该属性在 a 中已有时，以 a 已有的属性为主。

   const mergeObjects = (obj, otherObj, valueKey = null) => {for (const key in otherObj) {if (otherObj[key] !== null && (typeof otherObj[key] === 'object')) {obj[key] = {...otherObj[key],
         ...obj[key]
       }
       const keys = valueKey ? `${valueKey}.${key}` : (valueKey === null ? null : key)
       mergeObjects(obj[key], otherObj[key], keys)
     } else {
       const objKey = valueKey || key
       obj[objKey] = obj[objKey] !== undefined ? obj[objKey] : otherObj[objKey]
     }
   }
   return obj
 }
 const mergeObj = mergeObjects(a, b)

递归实现深拷贝：

深拷贝在日常开发中常常被用到，晓得如何实现吗？

const cloneDeep = (obj) => {const temp = {}
  for (var key in obj) {if (typeof obj[key] == 'object') {temp[key] = clone(obj[key])
    } else {temp[key] = obj[key]
    }
  }
  return temp
}

递归实现阶乘：

阶乘：一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且 0 的阶乘为 1。自然数 n 的阶乘写作 n!。

任何大于等于 1 的自然数 n 阶乘示意办法：

n! = 1 2 3 … (n – 1) * n
```
  const factorial = (num) => {return num < 0 ? -1 : (num === 0 || num === 1 ? 1 : (num * factorial(num - 1)))
  }
  factorial(3)
```
递归实现斐波拉契数列：

斐波拉契数列：数列从第 3 项开始，每一项都等于前两项之和。

如：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…..

求其中某一项的值：
```
  const fib = (num) => {if (n === 1 || n === 2) return n - 1
    return fib(num - 1) + fib(num - 2)
  }
```

递归实现树结构：

现有一组数据：


  [
    {
        "area_id": 5,
        "name": "广东省",
        "parent_id": 0,
    },  
    {
        "area_id": 6,
        "name": "广州市",
        "parent_id": 5,
    },
    {
        "area_id": 7,
        "name": "深圳市",
        "parent_id": 5,
    },
    {
        "area_id": 4,
        "name": "北京市",
        "parent_id": 3,
    },
    {
        "area_id": 3,
        "name": "北京",
        "parent_id": 0,
    },
    {
        "area_id": 2,
        "name": "测试子地区",
        "parent_id": 1,
    },
    {
        "area_id": 1,
        "name": "测试地区",
        "parent_id": 0,
    }
]

 这种一级的数据结构怎么转化为无限极的属性构造呢？```
  const toTreeData = (data, pid = 0) => {let arr = []
    data.filter(item => {return item.parent_id === pid;}).forEach(item => {
        arr.push({
            area_id: item.area_id,
            label: item.name,
            children: toTreeData(data, item.area_id)
        })
    })
    return arr
  }
```

正文完