js递归学习

梦里梦外; 2022-10-12 12:10 180阅读 0赞

**递归**：就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。  
**递归的两个必要因素**：  
递归方程，递归结束条件  
递归算法的核心：

*  在有限次可预见性结果中，找到结果与上一次结果之间的关系
 *  梳理清楚本次结果和上一次结果的关系有哪些方面或是因素
 *  在草稿纸上写出前几次的结果，或者画图，更容易找到规律，这种规律实际上就是递归方程

## 递归的步骤 ##

1.  寻找递推规律的关系
2.  判断递推关系的临界条件
3.  将递推关系的结构转换为递归体
4.  将临界条件加入递归体中

## 经典案例 ##

### 1. 求和 ###

求 1-100的和  
**分析**：计算 1 + 2 + … + 99 + 100 的和，我们可以看成 1-n 的和  
假设 n 为 3，即 和为 3 + (3-1) + ((3-1) -1)，多观察不难发现递推关系 n + (n-1)的递归体  
找到临界条件 1 的时候，和为1

function sum(n) { 
      if (n === 1) return 1
      return sum(n - 1) + n
    }

### 2. 斐波那契数列 ###

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … 求第 n 项  
**分析**：第1项和第2项都为1；第3项为第2项+第1项的和；第4项为第3项+第2项的和，可以看出递推关系：第n项为第n-1项+第n-2项的和  
临界条件是：第1项和第2项都为1

function febo(n) { 
      if ([1, 2].includes(n)) return 1
      return febo(n - 1) + febo(n - 2)
    }

### 3.爬楼梯 ###

js 递归案例：假设楼梯有 n 个台阶，每次可走1个或2个台阶，问走完这 n 个台阶有几种走法  
**分析**：假设n为1，只有1种走法，n为2，只有2种走法，n为3有3种走法，n为4有5种走法，n为5有8种走法，…得出递归关系  
临界条件就是n 为1和2时

function climb(n) { 
      if (n === 1) return 1
      if (n === 2) return 2
      return climb(n - 1) + climb(n - 2)
    }

### 4.深拷贝 ###

克隆一个对象返回一个对象

function clone(obj) { 
      let temp = { }
      for (let i in obj) { 
        if (typeof obj[i] === 'object') { 
          temp[i] = clone(obj[i])
        } else { 
          temp[i] = obj[i]
        }
      }
      return temp
    }

### 5.求阶乘 ###

计算 n 的阶乘  
**分析**：临界条件当n为1时，值为1  
假设n为2，即2*1，n为3，即 3*2\*1，得出递归体：n \* fn(n-1)

function fn(n) { 
      if (n === 1) return 1
      return n * fn(n - 1)
    }

### 多级遍历测试 ###

测试数据

let data = [
      { 
        name: "所有物品",
        children: [
          { 
            name: "水果",
            children: [{ name: "苹果", children: [{ name: '青苹果'}, { name: '红苹果'}]}]
          },
          { 
            name: '主食',
            children: [
              { name: "米饭", children: [{ name: '北方米饭'}, { name: '南方米饭'}]}
            ]
          },
          { 
            name: '生活用品',
            children: [
              { name: "电脑类", children: [{ name: '联想电脑'}, { name: '苹果电脑'}]},
              { name: "工具类", children: [{ name: "锄头"}, { name: "锤子"}]},
              { name: "生活用品", children: [{ name: "洗发水"}, { name: "沐浴露"}]}
            ]
          }
        ]
      }
    ]

功能要求：拿到每一级的最后一个数据的name值，即

['青苹果', '红苹果', '北方米饭', '南方米饭', '联想电脑', '苹果电脑', '锄头','锤子', '洗发水', '沐浴露']

递归实现：

function fn (data, arr = []) { 
      data.forEach(item => { 
        if (item.children && item.children.length > 0) { 
          fn(item.children, arr)
        } else { 
          arr.push(item.name)
        }
      })
      return arr
    }

需求：需要依次输出1, 2, 3, 4, 5,每个输出中间间隔1s

function fn(i) { 
      console.log(i)
      setTimeout(() => { 
        if (i > 4) return
        i++
        return fn(i)
      }, 1000)
    }
    
    fn(1)