preface

Recently, I have been studying the application of data structures and algorithms in the front-end domain, and I hope to open a series of discussions to help you better abstract and design JavaScript code. Because these days I am writing an interesting thing, which involves the object Proxy, but the native Proxy is shallow processing, does not support the deep processing of an object, just like deep copy, the core algorithm is recursion.

Plus recursion is kind of a hard algorithm to understand in the basic algorithms, and it’s not easy to write in practice, so with that in mind, let’s talk about recursion

The body of the

In fact, there are a lot of articles about algorithms on nuggets, but considering the front-end scene, it is not very close. It is more explained from the perspective of algorithms themselves, or general technology, or from the perspective of LeetCode, which is generally understood by authors but not by readers. In order to better understand recursion, Let’s take it literally

The literal meaning of recursion

A lot of computer terms translate very well in China, or very nonsense, such as Socket. But recursion is not the same, in my opinion, recursion this translation is very vivid, to the Chinese concise and comprehensive good explanation of recursion this word.

And by transmitter, I mean forward,

By returning, I mean going backwards,

And the way you understand the recursion graphically is something like this

And what makes recursion hard to understand is this logical section

A logical section in recursion

Recursion is a special kind of algorithm, and in the front end or in the field of JavaScript, usually what we call recursion is actually incomplete. You use a function to implement a recursive function, but you actually rely on the function stack provided to you by the JavaScript environment

In other words, recursive algorithms rely on a particular stack of structures

And we know that the characteristics of the stack are first in, last out

If the diagram above is represented in terms of stacks, it looks something like this

How do we interpret this diagram, which might be easier to understand with some code, let’s go deep through an object and then proxy the child objects

const nestObject = {
	a:1.b: {a:1.b: {a:1}},c:2
}

function deepProxy(target){
	/ / code
	let proxyTarget = new Proxy(target, proxyHandle)
	for(let key in target){
    	if(target.hasOwnProperty(key)){
        	proxyTarget[key] = deepProxy(proxyTarget[key]) // The call itself is the logical section}}/ / return code
    retrun proxyTarget
}
Copy the code

Because the call itself creates a logical cross section, our understanding of the linear execution of a function is often broken, and code after deepProxy() is delayed until all of the recursion code has been executed, which is the number of loops, the number of layers of nested objects.

This phenomenon explains two things well

  • Why do recursive loops cause stack overflows
  • Optimization principle of tail recursion

Recursive loops cause stack overflows

Because of the existence of the logic section has broken the conventional function, the way of carrying one only performs a function stack cannot be destroyed half of the function, especially the statement of the variables that must be stored in the corresponding in the heap, so as the recursive cycles increase inevitably leads to upper limit of the stack, cannot continue to save more function execution environment.

Optimization principle of tail recursion

Similarly, if there is no logical cross section, that is, all the code in the recursive function is the recursive code, the JavaScript engine can optimize the function stack and safely reclaim the memory of the executed recursive code without saving it, so that the stack will not overflow even if the number of times the loop is repeated.

The relatively complete deepProxy code is attached

const proxyHandle = {
  get(target, props) {
    console.log(props)
    return Reflect.get(target, props)
  },
  set(target, props, value) {
    console.log(props)
    return Reflect.set(target, props, value)
  }
}

function isObject(target) {
  return typeof target === 'object'
}

function isNotArray(target) {
  return Array.isArray(target) ! = =true
}

function deepProxy(target) {
  let proxyTarget = new Proxy(target, proxyHandle)
  for (let key in target) {
    if (target.hasOwnProperty(key)) {
      if (isObject(target[key]) && isNotArray(target[key])) {
        proxyTarget[key] = deepProxy(proxyTarget[key])
      }
    }
  }
  return proxyTarget
}

export default deepProxy

Copy the code

The latter

Recursive maximum benefit is elegant, can be a very elegant to traverse all sorts of data structures, whether linear or tree or graph, you can through the basic method of recursive algorithm to achieve through this book, understanding and mastering the recursion will help you to better use the commonly used data structure to write better code abstract.

This elegance is also reflected in the fact that you don’t need an extra context to share with recursive functions; the recursive functions themselves can be combined into one context.