Tail Recursion

most of the notes are taken from this SO post.

there's recursion, and there's tail recursion

a normal recursive function

const recsum = x => {
  if (x === 1) {
    return x
  } else {
    return x + recsum(x - 1)
  }
}

calling recsum(5) would make the javascript interpreter do:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

this is a recursion. Every function call has to wait for the next call to complete before javascript can free up space, because every function call is waiting for the nested call to complete.

a tail recursive function

const tailrecsum = (x, running_total = 0) => {
  if (x === 0) {
    return running_total
  } else {
    return tailrecsum(x - 1, running_total + x)
  }
}

calling tailrecsum(5) would now do:

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)

every function call has nothing left to do once it has returned. It is no longer waiting for the next call to finish, meaning the compiler can replace the current stack frame (I like to thinkthe bit of space the the compiler has allocated for your function to run) with something else (like your next recursion).

note how it looks like javascript's reduce function.

the consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. ... (the compiler will) simple reuse the current stack frame for the next recursive step.

"henrabotha" made a great tldr:

Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

OR

"Hoffmann" took a golden nugget of knowledge from the book Programming in Lua:

because a proper tail call (tail recursion) uses no stack space, there is no limit on the number of "nested" tail calls that a program can make. ... it will never overflow the stack.

OR

as long as your return call / function is the same as the next return call / function, you've got a tail recursion.

which is good. because it then runs like a loop, and will never cause a stack overflow.

again, just to hit home what both look like

Good (tail recursion)

function aFunction(params) {
  //... do stuff
  const newParams = params + 10
  return aFunction(newParams)
}

Bad (normal recursion)

function aFunction(params) {
  //... do stuff
  const newParams = params // + whatever
  return aFunction(newParams) + 10
}