递归在javascript中的应用 (递归处理数组和对象)

“这是我参与8月更文挑战的第29天，活动详情查看：8月更文挑战” 接触递归已经很久了，相比于最初的懵懂现在自己多少也有了些许长进，本文主要整理一些递归在JavaScript中的应用。

首先建议学递归有些吃力的同学看下这篇文章，把递归的原理讲的很清楚。 地址： mp.weixin.qq.com/s/sn9vM1kYu…

本文主要从数组和对象两个方面来讲解递归在工作中的一些应用。 我一般处理递归的思路主要注意以下两点

1. 先处理一小步（先处理最简情况）,然后自己调自己
2. 找到退出条件

数组

数组求最大值

思路：

• 最简单的情况：数组中长度为1时，直接返回；数组中长度为2，求最大值 解决方案：把数组切成两半，求左边的最大值，求右边的最大值。

var arr=[1,4,2,90,189,20,1,23,3,10]
//分成两半，求max左和max右
//
function findMax(arr){
    if(arr.length==0)return null
    if(arr.length==1)return arr[0]
    // 此处可以再优化一下
    if(arr.length==2){
        return arr[0]>=arr[1]? arr[0]:arr[1] 
    }
    const center= Math.floor(arr.length/2)

    const maxLeft=findMax(arr.slice(0,center))
    const maxRight=findMax(arr.slice(center))
    return maxLeft>=maxRight?maxLeft:maxRight
}

const max=findMax(arr)
console.log("max", max)

遍历数组

• 最简单的情况：先打印一个数
• 解决方案：先打印一个数，然后其他的数交给“自己”打印

//数组遍历，使用递归实现
var arr=[1,2,3,4,5]

function iteration(arr){
    if(arr.length==0)return 
    if(arr.length==1){
        console.log(arr[0])
        return 
    }
    console.log(arr[0])
    iteration(arr.slice(1))
}

// 1 iteration([2,3,4,5])

iteration(arr)

数组倒置

解决思路：假设其他元素都已经处理了，只剩下最后一个元素了,然后把reverse(2,3,4,5)和arr[0]拼成一个数组即可

//数组reverse，使用递归实现
var arr=[1,2,3,4,5]
//reverse(2,3,4,5) arr[0]
function reverse(arr){
    if(arr.length==0 || arr.length==1)return arr
    return [...reverse(arr.slice(1)),arr[0]]
}
const res=reverse(arr)
console.log("res", res)

对象

对对象的处理可以看做是对树的处理，因为对象的嵌套结构和树很类似。

对象属性遍历

思路：使用for-in遍历对象的属性，如果属性的值还是对象，递归遍历

var obj={
    id:1,
    value:'parent',
    child:{
        id:11,
        value:'child',
        child:{
            id:111,
            value:'child-child'

        }
    }
}


// 遍历打印
function recursiveObj(obj){
    for(let k in obj){
        if(obj.hasOwnProperty(k)){
            if(typeof obj[k] =='object'){
                recursiveObj(obj[k])
            }else{
                console.log(`${k}:${obj[k]}`)
            }
        }
    }
}

recursiveObj(obj)

对象扁平化

我有一个对象长下面这样：

const oldObject = {
    "KeyA": 1, 
    "KeyB":{
        "c": 2, 
        "d": 3, 
        "e":{
            "f": 7, 
            "" : 2
         }
      }
}

我要得到输出是这样子的：

const output={
    "KeyA": 1, 
    "KeyB.c": 2, 
    "KeyB.d": 3, 
    "KeyB.e.f": 7, 
    "KeyB.e": 2
}

处理逻辑如下：

1. 使用一个flattenHelper函数递归处理对象
2. 核心逻辑同上，使用for-in遍历对象的属性，如果属性的值还是对象，递归遍历

function flattenObject(oldObject) {
    const newObject = {};
  
    flattenHelper(oldObject, newObject, '');
  
    return newObject;
  
    function flattenHelper(currentObject, newObject, previousKeyName) {
      for (let key in currentObject) {
        let value = currentObject[key];
  
        if (value.constructor !== Object) {
          if (previousKeyName == null || previousKeyName == '') {
            newObject[key] = value;
          } else {
            if (key == null || key == '') {
              newObject[previousKeyName] = value;
            } else {
              newObject[previousKeyName + '.' + key] = value;
            }
          }
        } else {
          if (previousKeyName == null || previousKeyName == '') {
            flattenHelper(value, newObject, key);
          } else {
            flattenHelper(value, newObject, previousKeyName + '.' + key);
          }
        }
      }
    }
  }

const result=flattenObject(oldObject)
console.log("result", result)

递归应用-递归读取文件

思路很简单：判断当前读取的是文件还是文件夹，如果是文件夹，递归读取

const fs = require('fs');
const path=require('path')

function walkSync(currentDirPath, callback) {
    fs.readdirSync(currentDirPath).forEach(function (name) {
        var filePath = path.join(currentDirPath, name);
        var stat = fs.statSync(filePath);
        if (stat.isFile()) {
            callback(filePath, stat);
        } else if (stat.isDirectory()) {
            walkSync(filePath, callback);
        }
    });
}