Normally, when a function is called from within another function, a second stack frame is allocated to independently manage the variables and state of the second function call. This allocation consumes not only processing time but also additional memory.

Tail recursive call

Typically, there are at most 10 to 15 jumps from one function to another in the call stack. In this case, memory usage does not cause any real problems. However, when considering recursive programming, or when two or more functions call each other recursively, the depth of the call stack can easily be hundreds or thousands or more. If memory usage continues to grow indefinitely, you will run out of memory.

The JavaScript engine has to set a limit to prevent this programming technique from causing browsers and devices to run out of memory and crash. This is why we get the annoying “RangeError: Maximum Call stack Size exceeded” when this limit is reached.

The depth limit of the call stack is not controlled by the specification. It is implemented on a case-by-case basis and varies by browser and device. Don’t make any strong assumptions about the specific limits observed when coding, as they can vary from release to release.

There are some function call patterns called tail calls that can be optimized in such a way as to avoid extra stack frame allocation. If you can avoid extra allocation, there is no reason to limit the stack depth, so the engine does not have to set this limit.

A trailing call is a return function call that does nothing but return its return value.

This optimization is only applied in strict mode. This is yet another reason to stick with Strict code!

Here is a function call that is not at the end:

"use strict"

function foo(x) {
  return x * 2;
}

function boo(x) {
  // This is not a tail call!
  return 1 + foo(x);
}

boo(10); / / 21
Copy the code

After foo(x) is called, 1 +… , so boo (…). The state of the call needs to be preserved.

But the following code shows what happens to foo(…) And boo (…). The calls to are all at the end because they are the last thing that happens on their code path (except return);

"use strict"

function foo(x) {
  return x * 2;
}

function boo(x) {
  x = x + 1;
  if (x > 10) {
    return foo(x);
  }
  return boo(x + 1);
}

boo(5); / / 24
boo(15); 32
Copy the code

In the process, Boo (…) Recursion is obvious, and foo(…) It’s just a normal function call. In both cases, the function call is in the appropriate tail position. X + 1 in boo(…) It evaluates before it calls, and when it’s done, all it does is return.

These forms of Proper Tail Call (PTC) can be optimized, called Tail Call Optimization (TCO), so that additional stack frame allocation is not required. The engine does not need to create a new stack frame for the next function call, just reuse the existing stack frame. It works because a function doesn’t need to retain any current state — it doesn’t need to do anything with that state after PTC.

TCO means that there is no limit to the permissible depth of the call stack. This technique is slightly optimized for ordinary function calls in ordinary programs, but more importantly it opens the door to using recursion in program expression, even when the call stack may be tens of thousands of calls deep.

Instead of just using recursion as a theoretical solution to a problem, we can now actually use it in JavaScript programs!

For ES6, all PTC should be optimized in this way, recursive or not.

Tail call override

The problem here is that only PTC can be optimized, and non-PTC can of course continue to run, but trigger stack frame allocation as before. If you want this optimized access, you need to carefully design the function structure to support PTC.

If a function is not written in PTC mode, you may need to manually readjust code awareness and TCO.

Consideration:

"use strict"

function foo(x) {
  if (x <= 1) return 1;
  return (x / 2) + foo(x - 1);
}

foo(123456); // RangeError
Copy the code

Calling foo(x-1) is not PTC, because its result is appended with (x / 2) each time the return is preceded.

However, to make this code suitable for the ES6 engine TCO, you can rewrite it like this:

"use strict"

var foo = (function() {
  function_foo(acc, x) {
    if (x <= 1>) return acc;

    return _foo((x / 2) + acc, x - 1);
  }
  return function (x) {
    return _foo(1, x);
  };
  }
})();

foo(123456); / / 3810376848.5
Copy the code

If you run the above code in an ES6 engine that implements TCO, you will get 3810376848.5. However, it will still fail with RangeError in non-TCO engines.

The TCO optimization

There are several other techniques you can use to rewrite code so that the stack does not need to grow with each call.

One is called trampolining, which represents each partial result as a function that returns either another partial result function or the final result. And then you just loop until you get something that’s not a function, that’s the final result.

"use strict"

function trampoline(res) {
  while (typeof res === 'function') {
    res = res();
  }
  return res;
}

var foo = (function() {
  function_foo(acc, x) {
    if (x <= 1) return acc;

    return function partial() {
      return _foo((x/2) + acc, x - 1);
    };
  }

  return function(x) {
    return trampoline(_foo(1, x));
  }
})();

foo(123456);  / / 3810376848.5
Copy the code

This rewrite requires minimal modification to convert the recursion into a trampoline(…). The loop in.

  • First, thereturn _foo ...One line encapsulated inreturn partial() { ...Function expression.
  • Then,_foo(1, x)The call is wrapped intrampoline(...)In the call.

The reason this technique does not limit the call stack is that each internal partial(…) The function simply returns to the trampoline(…) In the while loop, trampolining runs the function and performs the next iteration of the loop. In other words, you’re partial. It doesn’t recursively call senior, it just returns another function, the stack depth stays the same, so it can run for any length of time.

Trampolining in this way uses inner partial(…) Closure of a function on variables X and ACC, holding state between iterations. The advantage is that the loop logic is extracted into reusable trampolines (…) Utility functions, many libraries provide various versions of it. You can reuse trampoline multiple times in your program with different trampoline algorithms (…) ;

Of course, if deep optimization is really needed (without considering reusability), then you can discard the ground closure state and use a loop to put the state tracking of ACC information online in the scope of a function. This technique is generally called recursive unrolling:

"use strict"

function foo(x) {
  var acc = 1;
  while (x > 1) {
    acc = (x / 2) + acc;
    x = x - 1;
  }

  return acc;
}

foo(123456); / / 3810376848.5
Copy the code

This way of expressing the algorithm is more readable and probably the highest performance of the various forms we explored earlier. So this one is shown to be the best, and you might wonder why we’re doing it any other way. Here are two reasons why we don’t always want to manually expand recursion:

  • There’s nothing here for reusabilitytrampoliningThe logic is extracted, but it’s online. This is fine when you only need to consider one example, but if you have multiple cases in your program, you probably need to increase reuse to keep your code shorter and more manageable.
  • The example here is very simple, just to show the various forms. But in business practice, there is much more complex logic in recursive algorithms, such as reciprocal recursion (not just a function call itself).

The deeper you explore this bottomless pit, the more manual and intricate unwinding optimization becomes. You quickly lose all the readability value you gained earlier. The main thing about recursion, even in the PTC form, is that it preserves the readability of the algorithm and leaves the burden of performance optimization to the engine.

If the algorithm is written in PTC form, the ES6 engine will apply TCO and the code will run at constant stack depth. Where you get recursive readability, you also get virtually no loss of performance and unlimited run length.

Finally, do you have any ideas to share in the comments section