The original address

With input and without output === = white, this paper records the trampoline practice process of learning JS recursion -> recursive optimization means -> tail recursion.

Recursion and iteration

Especially when I first learned recursion a few years ago and got confused: recursion simply means calling yourself, passing it out and coming back. In fact, there are two characteristics:

  • Call your own function
  • There must be a termination condition to exit the loop call

Then I came across the concept of Turing-complete and realized that programming languages designed to conform to Turing-complete could map reality and solve all computable problems. To put it simply, the essence of a Turing-complete language requires only sequential execution, branching and looping to realize that recursion and iteration are equivalent to a certain extent.

There is no loop statement in pure functional language, while JS is well-learned and draws on the characteristics of different languages, so there are two features of recursion and loop statement at the same time. Turing completeness does not solve uncomputable problems, such as downtime problems: you cannot judge an infinite loop (which is why an infinite loop gets stuck). The JS engine also limits the maximum call stack to prevent non-computability problems, as recursive calls are constantly stacked.

Fibonacci numbers

Looping statements

const fibonacci = n= > {
  if (n === 0 || n === 1) return n
  let i = 1,
    current,
    previous,
    next
  while (i < n) {
    previous = current || 0
    current = next || 1 
    next = current + previous
    i++
  }
  return next
}
Copy the code

recursive

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

It is obvious that recursion is much simpler, but there is a problem that the call stack is too deep. Fibonacci (100000) directly reports an error stack overflow, so there is a tail recursion optimization scheme.

Tail recursion

The tail call

A tail-call is a function call at the return keyword, which looks like this:

const foo = () = > {
  // do something 
}
const fn = () = > {
  // do something
  return foo()       // line 6
}
const result = fn()  // line 8
Copy the code

The call stack status at different stages of code execution is as follows:

When line 6 is executed, the main logic of function fn has been completed, and the only function of fn execution context is to record the position to be returned to in stack: line 8. This layer can be optimized as follows:

Tail recursion

Tail-recursion is the use of tail-recursion, the function is to optimize the call stack too deep, rewrite the Fibonacci number column tail-recursion:

const fibonacci = (n, item0 = 0, item1 = 1) = > {
  if (n === 0) return 0
  if (n === 1) return item1
  return fibonacci(n - 1, item1, item0 + item1)
}
Copy the code

Fibonacci tail recursive analysis: The value of the NTH term of the Fibonacci sequence is the sum of the first two terms. Conversely, I can get the value of the NTH term by going through n iterations from the 0th term. Parameter 1 is the number of items in the sequence, parameter 2 and parameter 3 are two consecutive items (starting from 0 and 1), each last call iterates the two consecutive items once, so as to take item 5 as an example:

Recursion -> tail recursion idea: to find a way to pass the execution logic of a function to the next call through parameters, for different logic to think about how to abstract, abstraction ability needs a lot of practice. Due to:

  1. Although command line arguments can be used on Node6 and Node7--harmony-tailcallsThe tail recursive optimization function is enabled. However, this feature has been removed from V8, and subsequent versions of Node8 do not have tail-recursive optimization.
  2. Some versions before Chrome did passchrome://flags/#enable-javascript-harmonyIt’s on, but it’s been removed.

TC39 is also looking for new JS syntax to explicitly indicate the need to use tail-recursive optimization because tail-recursive optimization destroys function call stack information. According to justJavac test results, Firefox, Chrome and Node.js do not support tail-recursive optimization. Other engines are not tested. I guess they have removed the support for tail-recursive optimization.

Can’t a JS engine happily use tail recursion without calling tail optimizations? No, there’s another way.

Trampoline

A Trampoline? Tail-recursively modified functions can be consumed automatically in order to eliminate excessive call stacks, as follows:

const trampoline = fn= > (. args) = > {
  letresult = fn(... args)while (typeof result === 'function') {
    result = result()
  }
  return result
}

const fibonacci = (n, item0 = 0, item1 = 1) = > {
  if (n === 0) return 0
  if (n === 1) {
    debugger
    return item1
  }
  return () = > fibonacci(n - 1, item1, item0 + item1) // Tail recursion where a layer of functions is wrapped and then returned
}

const f = trampoline(fibonacci)

console.log(f(1000000)) // No stack overflow is reported
Copy the code

conclusion

Trampoline can be used to wrap tail recursion to optimize stack overflow, but some logic can take a long time to transform recursion into tail recursion.

Looping and recursion are equivalent to some extent, but they can be used in different scenarios, selectively, and happily coded.

reference

Tail recursion in Javascript and its optimization

What is Turing complete

Tail-call optimization