“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

1 introduction

Programming problem: Input an integer n, output the NTH term of the Fibonacci sequence

Some interviewers like to ask this question. You might think it’s too easy to do it all at once with recursion or recursion.

Just when you feel confident enough to do it two ways…

Interviewer: Now please optimize your recursive implementation with tail recursion and optimize your recursive implementation with ES6 deconstruction assignment

.

If your basic skills are not solid at this point, you may be confused.

Is such a simple question, contains quite a lot of JS knowledge points, especially its optimization process can see that your basic skills are not solid, so some interviewers like to ask this question.

Let’s look at recursive and recursive implementations and their respective optimization processes

2 recursion and tail recursion

2.1 Recursive implementation

Let’s start with the recursive implementation:

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

What’s wrong with this code

The first problem, which is easy to see, is that when n is very large, the recursion depth is too great and the stack runs out of memory.

The second problem is that there is quite a lot of double counting, such as:

fibonacci(7)
= fibonacci(6) + fibonacci(5) // F (5) = f(5)
= (fibonacci(5) + fibonacci(4)) + (fibonacci(4) + fibonacci(3)) // Count f(5) twice.Copy the code

2.2 the tail call

Before we solve these two problems, what is a tail call

Tail call: The last action in a function returns the result of a call to the function, that is, the return value of the last new call is returned by the current function

Such as:

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

These are not tail calls:

function f(x) {
  return g(x) + 1 // execute g(x) first and return the return value of g(x) +1
}

function f(x) {
  let ret = g(x) // execute g(x)
  return ret // Finally returns the return value of g(x)
}
Copy the code

2.3 Tail call elimination

When a function is called, the JS engine creates a new stack frame and pushes it to the top of the stack to represent the function call

When a function call occurs, the computer must “remember” where the function was called — the return location — so that it can return to that location with the return value at the end of the call, which is typically stored on the call stack.

In the special case of a tail call, the computer could theoretically return the current function’s return position with the return value from the called function without remembering the position of the tail call.

Because of the tail call, it is theoretically possible to not remember position 2 and return directly from function G to position 1 (the return position of function F) with the return value.

Because the tail calls the work has been done before, so the current function frame (that is, the call is created when the stack frame) contains the local variable etc. Most of the things don’t need the function of the current frame after appropriate changes can be used directly as the function called tail frame, then the program can jump to the function called by the tail.

To illustrate the above example, the work of f before calling g has already been done, so the function frame created when calling F is used by g directly, so there is no need to create a stack frame for g again.

This process of repeated use of function frames is called tail-call elimination or tail-call optimization

2.4 the tail recursion

If the function calls itself at the tail-call location, this is called tail-recursion. Tail-recursion is a special tail-call that calls its own recursive function directly at the tail

Because of tail call elimination, tail recursion has only one stack frame, so it never “bursts the stack”.

ES6 specifies that all ECMAScript implementations must deploy “tail call elimination”, so stack overflow does not occur as long as tail recursion is used in ES6

2.5 Tail recursive optimization of Fibonacci functions

Returning to two problems with Fibonacci functions in 2.1, tail recursion can be used to solve the problem of “stack bursting”

Note that tail call elimination in ES6 is only enabled in strict mode

To make a recursive function tail recursive, you need to rewrite the function so that the last step of the function calls itself

// The original recursive function
function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

/ / modified
'use strict'
function fibonacci(n, pre, cur) {
  if (n === 0) {
    return n;
  }
  if (n === 1) {
    return cur;
  }
  return fibonacci(n - 1, cur, pre + cur);
}
/ / call
fibonacci(6.0.1)
Copy the code

The modified calculation logic looks like this:

f(6.0.1) 
= f(5.1.0 + 1) 
= f(4.1.1 + 1) 
= f(3.2.1 + 2) 
= f(2.3.2 + 3)
= f(1.5.3 + 5)
= 8
Copy the code

You might have noticed, in fact, that this is recursion, starting at 0 plus 1, all the way to the NTH term

Alternatively, you can use ES6’s default arguments to have the function pass in just one argument, n

'use strict'
function fibonacci(n, pre = 0, cur = 1) {
  if (n === 0) {
    return n;
  }
  if (n === 1) {
    return cur;
  }
  return fibonacci(n - 1, cur, pre + cur);
}
fibonacci(6)
Copy the code

In addition, since the function is changed to a tail-recursive form, f(n) only depends on f(n-1), and a large number of double calculations are solved

3 recursive

Recursive implementation

function fibonacci(n) {
  let cur = 0;
  let next = 1;
  for (let i = 0; i < n; i++) {
    let temp = cur;
    cur = next;
    next += temp;
  }
  return cur;
}
Copy the code

Recursion has nothing to optimize in performance, but we can optimize in form

Using ES6’s deconstructive assignment can leave out intermediate variables

function fibonacci(n) {
  let cur = 0;
  let next = 1;
  for (let i = 0; i < n; i++) {
    [cur, next] = [next, cur + next]
  }
  return cur;
}
Copy the code