Tail recursion

JavaScriptJunior~1 min read

In short: Tail recursion is a form of recursion where the recursive call is the last action of the function (i.e. nothing executes after it).

Detailed explanation

In ordinary recursion, after each recursive call the function has to save its context (variable values, the return point, etc.) in order to later execute the remaining operations. Because of this, deep recursion accumulates calls on the stack, and a stack overflow can occur.

Tail recursion solves this problem: if the recursive call is the function's last operation, the context does not need to be saved - the interpreter can optimize the call and reuse the same stack frame. This is called tail call optimization (TCO).

Example of ordinary recursion

javascript

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1); // there is a multiplication after the call
}

Here the recursive call is not a tail call, because a multiplication (* n) happens after it.

Example of tail recursion

javascript

function factorial(n, acc = 1) {
  if (n === 1) return acc;
  return factorial(n - 1, n * acc); // the call is the last action
}

Here the call factorial(n - 1, n * acc) is in the tail position of the function, nothing executes after it - this is tail recursion.

Advantages

Less memory usage - the stack does not grow. Faster for deep recursion. The code stays readable and safe.

Important

In theory, JavaScript supports tail call optimization (per the ES6 standard).
In practice - almost no JS engine (including V8 in Chrome and Node.js) implements it. So tail recursion in JS does not save the stack, but the principle remains useful to understand.

In one phrase:

Tail recursion is recursion in which the function's last action is the recursive call, which allows the execution to be optimized and avoids stack growth.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.

Tail recursion

#Detailed explanation

#Example of ordinary recursion

#Example of tail recursion

#Advantages

#Important