1. Recursion

Recursion, in mathematics and computer science, refers to the use of a function itself in the definition of a function

Inside a function, other functions can be called. A function is recursive if it internally calls itself

Its core idea is to transform a large and complex problem into a smaller problem similar to the original problem to solve.

In general, recursion requires boundary conditions, a recursive forward phase, and a recursive return phase. When the boundary conditions are not satisfied, recursively advance; when the boundary conditions are satisfied, recursively return

The following implements a function pow(x, n) that computes x raised to the nth power

Use the iterative method as follows:

function pow(x, n) {
  let result = 1;

  // In the loop, multiply result n times by x
  for (let i = 0; i < n; i++) {
    result *= x;
  }
  return result;
}

Use recursion as follows:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

When pow(x, n) is called, the execution splits into two branches:

             if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

That is, pow calls itself recursively until n == 1

To compute pow(2, 4), the recursive variant goes through the following steps:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

So recursion reduces the function call to a simpler function call, which reduces it to a simpler function, and so on, until the result

# tail recursion

Tail recursion, that is, calling itself (or a function that tail calls itself, etc.) at the end of a function. Tail recursion is also a special case of recursion. Tail recursion is a special type of tail call, that is, a recursive function that directly calls itself at the tail

On the basis of ordinary tail calls, tail recursion has two more features:

• The function itself is called at the end
• It can be optimized so that the computation only takes up constant stack space

In the process of recursive call, the system opens up a stack for the return point, local quantity, etc. of each layer to store. Too many recursion times can easily cause stack overflow.

At this time, we can use tail recursion, that is, all recursive calls in a function appear at the end of the function. For tail recursion, since there is only one call record, the "stack overflow" error will never occur

Implement the factorial, if you use ordinary recursion, as follows:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

If n is equal to 5, this method needs to be executed 5 times before returning the final calculation expression, so this method needs to be saved every time, which is easy to cause stack overflow, and the complexity is O(n)

If we use tail recursion, as follows:

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

It can be seen that each time a new function is returned, without the parameters of the previous function, there is no need to store the previous function. Tail recursion only needs to save a call stack, and the complexity is O(1)

# Application scenarios

array summation

function sumArray(arr, total) {
    if(arr.length === 1) {
        return total
    }
    return sum(arr, total + arr.pop())
}

Finding the Fibonacci sequence using tail recursion optimization

function factorial2 (n, start = 1, total = 1) {
    if(n <= 2){
        return total
    }
    return factorial2 (n -1, total, total + start)
}

Array flattening

let a = [1,2,3, [1,2,3, [1,2,3]]]
// become
let a = [1,2,3,1,2,3,1,2,3]
// Implementation
function flat(arr = [], result = []) {
    arr.forEach(v => {
        if(Array.isArray(v)) {
            result = result.concat(flat(v, []))
        }else {
            result.push(v)
        }
    })
    return result
}

Array object formatting

let obj = {
    a: '1',
    b: {
        c: '2',
        D: {
            E: '3'
        }
    }
}
// which translates to the following:
let obj = {
    a: '1',
    b: {
        c: '2',
        d: {
            e: '3'
        }
    }
}

// Code
function keysLower(obj) {
    let reg = new RegExp("([A-Z]+)", "g");
    for (let key in obj) {
        if (obj.hasOwnProperty(key)) {
            let temp = obj[key];
            if (reg.test(key.toString())) {
                // Reassign the modified property name to temp and add a converted property to the object obj
                temp = obj[key.replace(reg, function (result) {
                    return result.toLowerCase()
                })] = obj[key];
                // Remove previously capitalized key attributes
                delete obj[key];
            }
            // If the property is an object or an array, re-execute the function
            if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') {
                keysLower(temp);
            }
        }
    }
    return obj;
};