Применение рекурсии в javascript (рекурсивная обработка массивов и объектов)

внешний интерфейс структура данных

"Это 29-й день моего участия в августовском испытании обновлений. Узнайте подробности события:Испытание августовского обновления" Я был в контакте с рекурсией в течение длительного времени.По сравнению с первоначальным невежеством, я добился некоторого прогресса.Эта статья в основном организует некоторые приложения рекурсии в JavaScript.

Прежде всего, рекомендуется, чтобы студенты, которые изо всех сил пытаются изучить рекурсию, прочитали эту статью и очень четко объяснили принцип рекурсии. адрес:Tickets.WeChat.QQ.com/Yes/Suning 9VM1KY U…

В этой статье в основном объясняются некоторые применения рекурсии в работе с двух аспектов массива и объекта. Мое общее представление о рекурсии в основном обращает внимание на следующие два момента

  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);
        }
    });
}
Категории