1. What is recursion

Recursion is a double-edged sword, it is an algorithm that calls itself, and the key is to find its exits and entrances, otherwise it will cause the stack to overflow and fall into an endless loop. Many FP languages do not use loops; They only use recursion. The idea of recursion is to turn an unknown problem into a solved one.

2. The key to recursion

• Write the recursive function well
• Look for recursive relationships
• Find the recursive exit condition
• Form recursive functions based on conditions and relationships

3. Head and tail recursion

A recursion is header recursion if it has code statements to execute after a function call. Header recursion is often difficult to translate into looping statementsCopy the code

        function head(n){
            if(n==0) {return 0
            }
            head(n-1)
            console.log(n);
        }

Copy the code

Tail recursion does not have any code statements after a function call, usually at the end of a function declaration. Tail recursion is easily converted into loop statements.Copy the code

 function last(n){
            if(n==0) {return 0
            }
            console.log(n);
            last(n-1)}Copy the code

In general, tail recursion is better. Although they all have the same time and space complexity, tail-recursion has the advantage in terms of memory in the function stack. Header recursion waits in function stack memory until after execution before recursing code statements, which results in an overall delay in execution, while tail recursion terminates execution directly on the function stack.

4. Common recursive operations

4.1 o factorial

// Recurse from itself and multiply the recursed numbers. The result is used for the next calculation
        function jiecheng(num){
            // Find the exit
            if(num<=1) {return 1
            }
            else{
                return num*jiecheng(num-1)}}console.log(jiecheng(4));

Copy the code

4.2 Recursion to achieve deep copy of nested multi-layer objects

     const deepClone=(obj) = >{
            let temp={}
            // Iterate over the object to determine if the attribute value in the object is an object
            for(let k in obj){
                if(typeof obj[k]=='object'){
                   temp[k]=deepClone(obj[k]);
                }
                else{
                    temp[k]=obj[k]
                }
            }
            return temp
        }

Copy the code

4.3 Tree recursive traversal of values

Requirement: Obtain the ids of all level 3 rights of a role

 getLeafkey(node,arr){
     if(! node.children){return arr.push(node.id)
     }
     node.children.forEach(item= >{
       this. getLeafkey(item,arr)
     })

   }
If there is no children attribute on the node, it means that the node has reached level 3. If there is a child attribute on the node, it continues to iterate through the number group and recurse to this level
Copy the code

4.4 Recursion is flat

Const o = {a: 1, b: [1, 2, {c: true}], D: {e: 2, f: 3}, g: null}; const o = {a: 1, b: [1, 2, {c: true}], D: {e: 2, f: 3}, g: null}; Fn (o) = > flat transformation {” a “: 1,” b [0] “: 1,” b “[1] : 2,” b [2]. C: “true,” d.e “: 2,… }

const o = { a: 1.b: [1.2, { c: true}].d: { e: 2.f: 3 }, g: null };
const fn = (root) = > {
  const obj = {};
  const f1 = (root, propName) = > {
    // Loop through the object and iterate over it into an array. The key and value form an array and store it in a large array
    for (let [key, value] of Object.entries(root)) {
      // Check whether the value exists and whether the type is an object
      if (value && typeof value === "object") {
        // is an object, then recurse the object to the previous step, pass the value of this object in the call,
        // Check whether the proName exists based on whether the value in the object is an array.
        // If so, pass the variable into the function along with the current object for recursion
        f1(value, propName ? `${propName}[${key}] ` : key);
      } else {
        // If proName exists, root should be an array
        if (propName) {
          if (Array.isArray(root)) {
            B [0]:1,b[1]:2
            obj[`${propName}[${key}] `] = value;
          } else {
            obj[`${propName}.${key}`] = value; }}else {
          "B [2].c": trueobj[key] = value; }}}}; f1(root);return obj;
};

console.log(fn(o));
Copy the code

4.5 Recursive Implementation of Fibonacci sequence

The Fibonacci sequence is a series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. This pattern involves adding the first two numbers, so 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, and so on. In other words, the Fibonacci number at position n(for n > 2) is Fibonacci number (n – 1) plus Fibonacci number (n – 2).

        function fibonacciSequence(n) {
        // Define the first and second terms
            const memo = [0.1];
            const fib = (n) = > {
            // When the array arrives
                if(memo[n] ! =null) return memo[n]; 
                // The last number equals the sum of the first two items in the array
                return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
            };
            return fib(n);
        }
Copy the code

4.6 Recursive array index calculation

Requirement: Given an array of numbers, find the index with the first negative value

        let sals = [134.56.562.22.357.81, -303.73.256.45, -453.78];
        const debitIndex = (data, index) = > {
            if (index === data.length) {
                 return false
                 }
            else if (data[index] < 0) {
                return index
            }
            else{
                 return debitIndex(data, index + 1)}; };let result = debitIndex(sals, 0);

Copy the code