[coding] Tail call

function foo(data) {
    a(data);
    return b(data);
}

call performed as the final action of a procedure

Tail call optimization

call frames -> call stack

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。

foo:
  call B
  call A
  ret

Tail-call elimination replaces the last two lines with a single jump instruction:

 foo:
  call B
  jmp  A

ex：

function foo(data1, data2)
   B(data1)
   return A(data2)

(where data1 and data2 are parameters) a compiler might translate that as:^[b]

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   push reg            ; put data2 on stack where A expects it
   call A              ; A uses data2
   pop                 ; remove data2 from stack.
   ret

A tail-call optimizer could then change the code to:

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   mov  [sp+data1],reg ; put data2 where A expects it
   jmp  A              ; A uses data2 and returns immediately to caller.

a 函数的输入参数 data2 不会被push进stack，不会有新的call frame产生

Trail call recusively

Without trail call：

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

Space complexity： O(N)

with trail call:

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

只保留一个调用记录，复杂度 O(1) 

Ref : https://en.wikipedia.org/wiki/Tail_call