This is the 29th day of my participation in The August More Text Challenge. I have been in touch with recursion for a long time. Compared with the initial ignorance, I have made some progress now.

First of all, I suggest students who have trouble learning recursion to read this article and explain the principle of recursion very clearly. Address: mp.weixin.qq.com/s/sn9vM1kYu…

This article mainly from the array and object two aspects to explain recursion in the work of some applications. My general approach to recursion is to focus on two things

  1. Take one small step (the simplest case first) and tune yourself
  2. Find exit conditions

An array of

Maximizing an array

Ideas:

  • The simplest case: if the length of the array is 1, return it; The array is of length 2, maximized

Solution: Cut the array in half, find the maximum on the left and maximum on the right.

var arr=[1.4.2.90.189.20.1.23.3.10]
// Divide into two parts, find Max left and Max right
//
function findMax(arr){
    if(arr.length==0)return null
    if(arr.length==1)return arr[0]
    // It can be optimized here
    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))
    returnmaxLeft>=maxRight? maxLeft:maxRight }const max=findMax(arr)
console.log("max", max)
Copy the code

Through the array

  • The simplest case: Print a number first
  • The solution: Print one number first, and then leave the rest to “me” to print
// Array traversal, using recursive implementation
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 (5-tetrafluorobenzoic [2])

iteration(arr)
Copy the code

An array of the horse

Assume that all but one element has been processed, then combine reverse(2,3,4,5) and arr[0] into an array

// array reverse, Using recursive implementation var arr = [1, 2, 3, 4, 5] / / reverse (2, 5-tetrafluorobenzoic) arr [0] the 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)Copy the code

object

Processing of an object can be thought of as processing of a tree because the nested structure of an object is similar to that of a tree.

Object property traversal

If the value of the attribute is still the object, iterate recursively

var obj={
    id:1.value:'parent'.child: {id:11.value:'child'.child: {id:111.value:'child-child'}}}// Iterate over the print
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)

Copy the code

The object is flat

I have an object that looks like this:

const oldObject = {
    "KeyA": 1."KeyB": {"c": 2."d": 3."e": {"f": 7."" : 2}}}Copy the code

I want the output to look something like this:

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

The processing logic is as follows:

  1. The use of aflattenHelperFunctions process objects recursively
  2. The core logic is the same as above, using for-in to traverse the properties of an object, if the value of the property is still the object, recursive traversal
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)
Copy the code

Recursive application – Read files recursively

The idea is simple: determine whether you are currently reading a file or a folder, and if it is a folder, recursively read

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); }}); }Copy the code