Relearn recursion

For most of the front end (including me), the time to learn recursion is the time to learn function, the cognition of recursion is the function call itself, and then define an exit for the function, through this function to break one thing into the same type of small things. But you will find that you write recursion rarely, because in many cases recursion can be used to achieve the same effect with a loop, so for the specific use of recursion, when to use recursion, is the main topic of this article.

Can recursion only solve the problem of tree structure?

It’s easy for people who rarely use recursion to solve problems to think of recursion as something that can only be done in the tree case, so let’s start by solving the tree case to get a better understanding of what situations recursion can solve and what other problems it can solve in addition to tree-structured data?

Problem 1: Obtain the root node name

Click the current node to get the name of the root node

The root node does not include the virtual root node in the tree, which refers to the root node of the data

This is the virtual root node

The result is this

This requirement is very simple, we can easily think of recursion, why?

• Obtain the root level: continuously obtain the parent level of the current node until no parent level is the root level
• Recursive exit condition: passNode) or the parent node) level
• Changing state values in recursion:node.parent

getRootNodeName(node) {
  if(! node)return
  if (node.level === 1) {
    return node.label
  }
  return this.getRootNodeName(node.parent)
}
Copy the code

We implement this recursive function using the above three conditions. What we need to pay attention to here is the changing state value in the recursion. This is the most difficult and important part of the recursion, which will be discussed later

The recursion is actually very easy to write, and the loop can only achieve the same effect

getRootNodeName(node) {
  if(! node)return
  while (node.level > 1) {
    node = node.parent
  }
  return node.label
}
Copy the code

Problem 2: Obtain the node at the specified level in the tree where the current node resides

There is also a constraint, node node does not have the level attribute, only the parent attribute points to the parent node, here for better expression, we remove the virtual root node in the node.

We want to achieve something like this: click on the current node to get the current node’s hierarchy

The recursive implementation

getNodeLevel(node) {
  if(! node.parent)return 1
  return this.getNodeLevel(node.parent) + 1
}
Copy the code

If node.parent does not exist, the current node is the first level node, and in the process of backtracking, the parent node + 1 = the current level node

Recursion: You open the door in front of you and see another door in the room. You walk up to it and find that the key in your hand can still open it. You push the door open and find another door inside. You keep opening it. A few times later, you open the door in front of you and there is only one room, no door. Then you go back the way you came, and count each time you come to a room, and when you get to the entrance, you can answer how many doors you opened with this key.

Cycle to achieve

getNodeLevel(node) {
  let n = 1
  let p = node
  while (p.parent) {
    p = p.parent
    n++
  }
  return n
}
Copy the code

Loop: You open the door in front of you and see another door inside. You go to the door and find that the key in your hand can open it. You push the door open and find another door inside. (If the first two doors are the same, then this door is the same as the first two; If the second door is smaller than the first door, then this door is smaller than the second door, and you keep opening this door, and you keep doing this until you open all the doors. However, the person at the entrance can’t wait for you to come back and tell him the answer

Since loops have no backtracking, our current loop has to store state data for each recursion

Problem 3: Tree node filtering

One might ask tree node filtering isn’t that in the el-Tree use case? But that doesn’t solve the problem of our actual scenario, let me give you an example

<el-tree ... :filter-node-method="filterNode" /> <script> export default { methods: { filterNode(value, data) { if (! value) return true return data.label.indexOf(value) ! == -1 }, } } </script>Copy the code

Existing problems

The current filter only filters out all the nodes that do not meet the criteria by means of label inclusion, and the desired effect should be to filter out the branches that do not meet the criteria, if the current level meets the criteria then its children should not be filtered out

The recursive implementation

methods: {
  filterNodeMethod(value, data, node) {
    if(! value) {return true
    }
    return this.deepfilterChildNode(value, node)
  },
  deepfilterChildNode(value, node) {
    if (node.level === 1) return false
    const { filterNodeByIndexOf, deepfilterChildNode } = this
    if (filterNodeByIndexOf(node.label, value)) {
      return true
    }
    return deepfilterChildNode(value, node.parent)
  },
  filterNodeByIndexOf(label, value) {
    returnlabel.indexOf(value) ! = = -1}}Copy the code

Cycle to achieve

The main implementation function is deepfilterChildNode, followed by a loop to achieve the synchronization effect

methods: {
  deepfilterChildNode(value, node) {
    const { filterNodeByIndexOf } = this
    if (filterNodeByIndexOf(node.label, value)) {
      return true
    }
    // Tier 1 nodes have no parent
    if (node.level === 1) return false
    // Find the largest node
    const maxNode = 1 
    // The parent of the multi-level node meets the requirement, do not filter the child
    let parentNode = node.parent
    while (parentNode.level > maxNode) {
      if (filterNodeByIndexOf(parentNode.label, value)) {
        return true
      }
      parentNode = parentNode.parent
    }
    // The maximum parent of the current node is not found
    return false}},Copy the code

Problem 4: Implement Instanceof

• Function: Checks whether the stereotype object of the right constructor exists in the stereotype chain of the left object
• Principle: The left prototype chain contains the right prototype object

The left-hand side must be objects

1 instaceof Number // false
Number(1) instaceof Number // false
new Number(1) instaceof Number // true
Copy the code

The right hand side must be a constructor

let f1 = () = > {};
let f2 = function () {}
class f3 {}
obj instanceof f1; / / an error
obj instanceof f2 // false
obj instanceof f3 // false
Copy the code

There is a stereotype object on the right in the left stereotype chain

let obj = {}
class ctor {}
console.log(obj instanceof ctor); // false
Object.setPrototypeOf(obj, new ctor)
console.log(obj instanceof ctor); // true

let getProto = Object.getPrototypeOf
getProto(getProto(obj)) === ctor.prototype // true
Copy the code

The recursive implementation

function _instaceof(obj, ctor) {
  // The left side must be the object
  if(! (obj &&typeof obj === 'object')) {
    return false
  }
  // Get the prototype chain object of the object
  let proto = Object.getPrototypeOf(obj)
  // Check whether the object's prototype chain object is the prototype object of the constructor function
  return proto === ctor.prototype || _instaceof(proto, ctor)
}
Copy the code

Cycle to achieve

function instanceOf1(obj, ctor) {
  if(! (obj &&typeof obj === 'object')) {
    return false
  }
  let proto 
  while(proto = Object.getPrototypeOf(obj)) {
    if (Object.is(proto, ctor.prototype)) return true
    obj = proto
  }
  return false
}
Copy the code

“Problem five” depth attributes

The test data

let obj = {
  a: {
    b: {
      c: 1.cc: {
        dd: {
          f: 'f Val'}}}},data: {
    v1: 'v1'.v2: 'v2'.v3: 'v3'}}Copy the code

Retrieve attributes

function getDeepObjAttr(obj, deepPath) {
  const deepGet = (o, paths) = > {
    if(! paths.length)return o
    return deepGet(Reflect.get(o, paths.shift()), paths)
  }
  return deepGet(obj, deepPath.split('. '))}Copy the code

console.log(getDeepObjAttr(obj, 'a.b.cc.dd.f')) // f Val
Copy the code

Set properties

function setDeepObjAttr(model, deepPath, val) {
  let paths = deepPath.split('. ')
  if(! paths.length)return model
  const setDeep = (o, p, i) = > {
    if (i < 0) return o
    let prop = p[i]
    // The value to be set for the last layer
    if (i === p.length - 1) {
      Reflect.set(o, prop, val)
    } else {
      Reflect.set(o, prop, { ... getDeepObjAttr(model, p.slice(0, i + 1).join('. ')),
        ...o
      })
      Reflect.deleteProperty(o, paths[i + 1])}return setDeep(o, p, --i)
  }
  return Object.assign(model,
    setDeep({}, [...paths], paths.length - 1))}Copy the code

setDeepObjAttr(obj, 'a.b.c'.'2')
setDeepObjAttr(obj, 'a.b.cc.dd.f'.'f Val21')
Copy the code

Obj after the change

{
    "a": {
        "b": {
            "c": "2"."cc": {
                "dd": {
                    "f": "f Val21"}}}},"data": {
        "v1": "v11"."v2": "v2"."v3": "v3"}}Copy the code

This recursion has multiple exit conditions and is not simply doing one type of thing, and the free variable (global variable) model referenced in the recursive function will be affected if the model is modified during the recursive process

Think of recursively those state values (variables) that need to be extracted globally

Similar to Inception, I have $10 in my hand, I have the first dream (n), in which I spend $2, and then I have another dream (n +1), in which I still have $10, and the money spent in the previous dream does not affect my money in this dream. The state value (variable) is a local variable created inside the recursive function, otherwise the state value (variable) needs to be placed globally

The implementation of the loop is also shown here

function getDeepObjAttr(obj, deepPath) {
  let paths = deepPath.split('. ')
  if(! paths.length)return obj
  let prop,
    targetVal,
    tempObj = obj
  while ((prop = paths.shift()) && paths.length) {
    if (!Reflect.has(tempObj, prop)) {
      return
    }
    tempObj = tempObj[prop]
  }
  return tempObj[prop]
}
Copy the code

function setDeepObjAttr(model, deepPath, val) {
  / / path
  let paths = deepPath.split('. ')
  // Target value, which stores all attributes that match the path
  let targetVal = {}
  // Find the prop for each object
  let pathsNew = paths.concat([])
  let prop
  for (let i = paths.length - 1, j = i; i >= 0; i--) {
    prop = paths[i]
    // The value to be set for the last layer
    if (i === j) {
      targetVal[prop] = val
    } else if (i === 0) {
      // The first layer needs to replace the first attribute directly
      const obj = this.getDeepObjAttr(model, prop);
      Reflect.set(model, prop, Object.assign({}, obj, targetVal))
    } else {
      // Update the values of each level (excluding stored values)
      let curDeppObj = getDeepObjAttr(model, pathsNew.join('. '))
      // Store the values of the current hierarchy
      Reflect.set(targetVal, prop, Object.assign({}, curDeppObj, targetVal))
      // Delete the value stored in the previous path
      Reflect.deleteProperty(targetVal, paths[i + 1])}// Remove the processed paths
    pathsNew.pop()
  }
  return model
}
Copy the code

We still haven’t answered the question of whether recursion can only solve the problem of tree structure, which raises another question, what’s the difference between recursion and loop?

What’s the difference between recursion and loop?

Through the above five examples, we found that recursion and loop can be realized. In fact, recursion and loop are two different typical ways of solving problems, which have the same characteristics, namely, doing repetitive tasks. In terms of algorithm design alone, recursion and loop are not superior or inferior. In practice, however, recursion often causes performance problems because of the overhead of function calls, especially if the solution size is uncertain; Loops are more efficient than recursion because they have no function call overhead.

By the way, solving for indeterminacy also involves implicitly large data sizes, but front-end pages rarely deal with very large data sizes, so recursion is fine

Similarities:

• Breaking big things down into small things is ** repetitive tasks ** (loop, recursive calls)
• In the process, state value transformation is called state expansion

The difference between:

• If we use loops we have to build a stack instead of a system stack to hold the contents that deal with the current state

So recursion again

let arr = [1.2.3.4.5.6]

function logArr(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}
logArr(arr)
Copy the code

Let you print each item in turn, can this be done recursively??

consider

---

---

---

---

---

---

The answer is yes

function logArr(arr) {
  const dfs = (idx) = > {
    if (idx === arr.length) return
    console.log(arr[idx]);
    dfs(idx + 1)
  }
  dfs(0)}Copy the code

Fibonacci numbers

Fibonacci sequence refers to the sequence 1, 1, 2, 3, 5, 8, 13, 21, which is simply the sum of the first two numbers after the second number: F0=0, F1=1, Fn=F(n-1)+F(n-2) (n >=2).

Recursive solution

function fibonacci(n) {
  // Recursive termination condition
  if (n <= 2) {
    return 1
  }
  // Repeat the same logic to reduce the size of the problem
  return fibonacci(n - 1) + fibonacci(n - 2)}Copy the code

fibonacci(5)
Copy the code

State expands spanning tree

There’s a lot of double counting going on here, when you compute fib of 5

1Fib (4)
2Fib (3)
3Fib (2)
5Fib (1) 
3Fib (0)
Copy the code

Such repeated calculations are equivalent to the same branch, and there is an important operation in DFS called pruning; In the current implementation of recursion we can cache the repeated computations and not call them when they happen later, which is pruning, which is a big performance optimization for recursion.

// Create an empty object as a container for the cache
let cache = {};
function fibonacci(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  if (cache[n]) {
    return cache[n];
  }
  return cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
Copy the code

There is also a caching scheme, where the computation is performed recursively and the final result is returned backtracking

function fibonacci(n, cur = 0, next = 1) {
    if(n == 0) return 0;
    if(n == 1) return next; 
    return fibonacci(n - 1, next, cur + next);
}
Copy the code

Cycle to solve

function fibonacci(n) {
  if (n <= 2) return 1
  // Maintain the state value of "stack" for state backtracking
  let first = 1
  // Maintain the state value of "stack" for state backtracking
  let second = 1
  let ret = 0
  n -= 2

  while (n--) {
    // Current number = previous number + previous two numbers
    ret = first + second
    first = second
    second = ret
  }
  return ret
}
Copy the code

Now, to answer the first question, recursion is not just for tree data structures and data with distinct hierarchies. For this case, data is very recursive and we can easily imagine things like Fibonacci numbers, factorials, Yang Hui triangles… The way that you can solve it recursively you can also solve it recursively by changing the state values as you recurse.

Binary search

Cycle to achieve

function binarySearch(nums, target) {
  let l = 0
  let r = nums.length - 1
  let mid

  while (l <= r) {
    mid = (l + r) >> 1
    if (nums[mid] === target) {
      return mid
    } else if (nums[mid] > target) {
      r = mid - 1
    } else {
      l = mid + 1}}return -1
}
Copy the code

The recursive implementation

Transform the state value and expand the spanning tree

function binarySearch(nums, target, l = 0, r = nums.length - 1) {
  let mid
  while (l <= r) {
    mid = (l + r) >> 1
    if (nums[mid] === target) {
      return mid
    } else if (nums[mid] > target) {
      return binarySearch(nums, target, l, mid - 1)}else {
      return binarySearch(nums, target, mid + 1, r)
    }
  }
  return -1
}
Copy the code

Application of recursion in algorithms

In the algorithm for recursion application scenarios are particularly special, DFS: backtracking, binary tree traversal, rollover, path summation… , the above types of problems with recursion brush a few questions, for recursion will have a deeper cognition and understanding, if the needs encountered behind the recursive solution, naturally you can think of recursion.

Now give some recursively solvable Leetcode problems, not to say to learn algorithm brush problems, the purpose here is to do these problems can let us have a deeper understanding of the use of recursion, recursion is not too much may take some time, after mastering all of them is also a promotion for myself

Binary tree traversal

There are three ways to traverse a binary tree:

• Front-order traversal: root, left, right
• Middle order traversal: left, root, right
• Subsequent traversal: left, right, root

The former sequence traversal

Leetcode144. Antecedent traversal of binary trees

/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function(root) {
  let ans = []
  const preIterator = (root) = > {
    if(! root)return
    ans.push(root.val)
    preIterator(root.left)
    preIterator(root.right)
  }
  preIterator(root)
  return ans
}
Copy the code

In the sequence traversal

Leetcode94. Middle order traversal of binary trees

/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
  let ans = []
  const inIterator = (root) = > {
    if(! root)return
    inIterator(root.left)
    ans.push(root.val)
    inIterator(root.right)
  }
  inIterator(root)
  return ans
};
Copy the code

After the sequence traversal

Leetcode145. Post-order traversal of binary trees

/ * * *@param {TreeNode} root
 * @return {number[]}* /
var postorderTraversal = function(root) {
  let ans = []
  const postIterator = (root) = > {
    if(! root)return
    if(! postIterator(root.left)) {if(! postIterator(root.right)) { ans.push(root.val) } } } postIterator(root)return ans
};
Copy the code

Path to the combined

Leetcode112. Sum of paths

var hasPathSum = function (root, targetSum) {
  if(! root)return false
  targetSum = targetSum - root.val

  // The current node is a leaf node
  if(! root.left && ! root.right) {// If the current node matches all ragetsums, the current node is the target node
    return targetSum === 0
  }

  return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum)
};
Copy the code

Leetcode113. Sum of paths II

/ * * *@param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}* /
var pathSum = function (root, targetSum) {
  let ans = []
  const dfs = (root, targetSum, temp = []) = > {
    if(! root)return
    temp.push(root.val)
    targetSum -= root.val
    if(! root.left && ! root.right && targetSum ===0) {
      ans.push([...temp])
    }
    dfs(root.left, targetSum, temp)
    dfs(root.right, targetSum, temp)
    temp.pop()
  }
  dfs(root, targetSum)
  return ans
};
Copy the code

back

Leetcode39. Sum of combinations

/ * * *@param {number[]} candidates
 * @param {number} target
 * @return {number[][]}* /
 var combinationSum = function (candidates, target) {
  const ans = []
  const dfs = (idx, target, temp = []) = > {
    if (idx === candidates.length) return
    if (target < 0) return
    if (target === 0) {
      ans.push([...temp])
      temp = []
      return
    }
    temp.push(candidates[idx])
    dfs(idx, target - candidates[idx], temp)

    temp.pop()
    dfs(idx + 1, target, temp)
  }
  dfs(0, target)
  return ans
};
Copy the code

Write in the last

Practice makes perfect, shortage in play

If there is that piece of writing is not good or there is a problem, you are welcome to point out, I will also keep modifying in the following article. I hope I can grow with you as I progress. Friends who like my article can also follow it, I will be grateful for the first batch of people to follow me. At this time, young you and I, travel light; Then, rich you and I, full of goods.