递归算法

• 2021 年 5 月 3 日
• 筆記
• js, 前端, 算法

递归算法

1. 什么是递归

   在运行过程中，自身调用自身。

   一个条件：至少应该有一个结束条件。

例子：

1. 你和你的朋友在一个地方约见面，他已经到了，你距离你们约定的地方还差100步。
   那么最后这一百步，你肯定是需要一步一步走过去。

   那么咱们如何用递归的方式来实现最后这100步呢

   示例代码：

   function walk(step) {
       if (step == 0) {
           console.log('已经到达目的地')
       }else {
           step--
           console.log(`已经走了一步，还剩${step}步`)
           walk(step)
       }
   }
   walk(100)
   

   递归一般应用在什么场景下

   在有很多层级结构，并且每个层级的结构都是大致相同的。一般情况下，前后都有依赖。

   递归的方式和普通的函数调用的方式，递归效率更低。

   所以呢，在日常的开发当中，我们不要滥用递归。

2. 某一个数与另外一个数之间的和怎么递归实现

   示例代码：

   // min 最小值
   // max 最大值
   
   function sum(min, max) {
      if (min == max) {
         return max
      }else {
         return min + sum(min + 1, max)
      }
   }
   
   let result = sum(1,100)
   console.log(result)
   

3. 将列表型的数据转化成树形数据

   示例代码：

   export function tranListToTreeData(list, rootValue) {
    var arr = []
    list.forEach(item => {
        if (item.pid === rootValue) {
            const children = tranListToTreeData(list, item.id)
            if (children.length) {
                item.children = children
            }
            arr.push(item)
        }
   })
   return arr
   }