define

In mathematics and computer science, the method of using the function itself in the definition of a function. In a literal sense, calling a function within a function itself.

A classic example

1. The factorial

  function factorial(n){
    if(n == 1 || n === 0) {return 1
     }
    return n * factorial(n-1)}Copy the code

2. Fibonacci numbers

  function fb(n){
    if(n == 0 || n == 1) {return n
    }
    return fb(n-1) + fb(n-2)}Copy the code

Analysis of the

As we can see from the two examples, it will also call the function itself again, and at that layer of the call, there may be a value to return, or it may call the function itself again. But no matter how many calls it makes in a row, it has a boundary, like n equals 1 for factorial, or n equals 2 for Fibonacci. From this we can summarize the characteristics of recursion: 1. Regular, there is a process of calling the function itself. 2. There are exits and boundary conditions that make recursion complete.

The advantages and disadvantages

Advantages: The process of repeated calculation can be expressed in a small piece of code, making the code look more concise disadvantages: 1. Recursion is the process of calling the function itself once or more, and during the function call, space is allocated in stack memory to store variables, parameters, addresses, etc., which consumes time and space, resulting in inefficient execution. 2. There are many repeated calculation processes in recursion, and overlapping calculation may occur. Such repeated calculation will also lead to low efficiency.

An optimization method

Recursion is the process of constantly calling a function. When a function is executed, an execution context is created and pushed into the execution context stack. When the function is finished, the execution context is ejected from the execution context stack. The process of calling the function over and over again, javascript will repeat the above process over and over again, which is very costly. We need a method to optimize this process, and that method is the tail call.

The tail call

A tail call means that the last action inside a function is a function call, and the return value is only the function, no other operations. Eg: Tail call:

function a(x){
  return f(x)
}
Copy the code

Non-tail call:

function b(x){
    return f(x) + 1
}
Copy the code

When the first function is executed, one function is called, but the original function A has finished executing, and the execution context of another function F is pushed in. This process is equivalent to pushing in only one execution context. That is, the execution context of function A will be pressed into f only after the execution context of function A is popped up. When the second function is executed, in the process of calling the function, function B needs to wait for the completion of function f and the sum of 1 before returning a value, which is equivalent to forcing two execution contexts. The purpose of a tail call is to reduce the number of execution contexts created.

Optimization example

Let’s optimize the factorial function:

function factorial(n,sum){
    if(n == 1 || n === 0) {return first
     }
    return factorial(n-1,n * sum)
  }
Copy the code

Where sum starts off as the final factorial number, 1.

If you find my articles useful, please like them and follow them. Also, please visit my personal blog github.com/BokFang