This is the 10th day of my participation in the August More Text Challenge

preface

Business code development, in fact, is writing if-else

Simply put, recursion is the behavior of calling itself from within the body of a function, which can sometimes make it easy to implement complex algorithms, such as calculating Fibonacci numbers or factorial. But there are some potential problems with recursion: Recursion termination conditions such as missing or not clear, it is easy to cause the user interface card at the same time because of the recursion is a space in time through the algorithm, in the process of its execution stack to save a lot of intermediate operations as a result, it is the memory overhead is proportional to the number of recursion, because the browser will restrict JavaScript call stack size, Recursive execution beyond the limit will fail.

Use an iterative

Any recursive function can be rewritten as an iterative loop, and while loops introduce their own performance problems, they still have a much lower performance overhead than long-executing recursive functions. Take merge sort as an example:

// implement merge sort recursively
function merge(left, right){
  const result = []
  while(left.length > 0 && right.length > 0) {
    // Put the smallest one into the result first
    if(left[0] < left[0]){
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  / / merge
  return result.concat(left).concat(right)
}

// a recursive function
function mergeSort(array){
  if(array.length == 1) return array
  // Compute the midpoint of the array
  const middle = Math.floor(array.length / 2)
  // Split the array
  const left = array.slice(0, middle)
  const right = array.slice(middle)
  // Perform recursive merge and sort
  return merge(mergeSort(left), mergeSort(right))
 }
Copy the code

As you can see, mergeSort() is called frequently. For an array of n elements, mergeSort() is called 2n-1 times, which is a severe test for the browser’s call stack as the number of array elements being processed increases. The iterative mode is as follows:

// Rewrite recursive functions iteratively
function mergeSort(array){
  if(array.length == 1 ) return array
  const len = array.length
  const work = []
  for(let i = 0 ; i < len; i ++){
    work.push([array[i]])
  }
  // Make sure the total length is even
  if(len & 1) work.push([])
  // The iteration merges in pairs
  for(let lim = len; lim > 1; lim = (lim+1) /2) {
    for(let j = 0,k = 0; k < lim; j += 1, k += 2){
      work[j] = merge(work[k], work[k+1])}// Add an empty array if the length is odd
    if(lim & 1) work[j] = []
  }
  return work[0]}Copy the code

The mergeSort() function implemented iteratively here is functionally the same as recursively, although it may be slower to flash over at execution time, but it does not suffer from browser constraints on the JavaScript call stack.

Avoid reinventing the wheel

If the result of a previous calculation can be used by a later calculation during recursion, caching the result of the previous calculation can effectively avoid a lot of rework, which can result in a good performance improvement. For example, recursion often handles the following factorial operations:

// Compute n factorial
function factorial(n){
  if(n === 0) {
    return 1
  } else {
    return n * fatorial(n-1)}}Copy the code

Factorial (2, 3, or 4) will be called 12 times to recalculate the factorial of 4 and the factorial of 2. You can see that if you cache the factorial of 3 before you compute the factorial of 4, then you only have to do the recursion one more time to compute the factorial of 4. In this way, by caching factorial calculation results, redundant calculation process can be avoided. The original 12 recursive calls can be reduced to 5 times. According to this appeal, provide a solution that effectively utilizes caching to reduce unnecessary computations:

// Use caching to avoid double counting
function memoize(func, cache){
  const cache = cache || {}
  return function(args){  
    if(! cache.hasOwnProperty(args)){ cache[args]=func(args); }returncache[args]; }}Copy the code

This method uses function closures to effectively avoid repeated operations such as computing multiple factorial, ensuring that new values are generated only when a calculation has never occurred before, so that the previous factorial function can be rewritten as:

// Cache the factorial scheme of the result
const memorizeFactorial = memorize(factorial, {'0': 1.'1': 1})
Copy the code

There are performance issues with this approach, such as function closures that prolong the lifetime of local variables, which can lead to memory overruns if the data is too large to be effectively reclaimed. This scheme can save time only when the same parameters are called many times in the program. Therefore, overall, the optimization scheme needs to be considered according to specific use scenarios.