关于 js 尾递归优化时间复杂度的疑惑

[Alander]

当写出一段代码用尾递归来计算阶乘时：

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

这段代码的时间复杂度是多少呢？为什么？

js 引擎在处理这段代码的时候会优化操作吗，比如我写下 factorial(120, 1)，难道代码是直接执行 120 * 119 * 118 ... 1 吗？如果是，那将 factorial(120, 1)转换为这个常量整体是否需要一定时间？这段代码的时间复杂度是怎么算出来的呢？

我太菜了，想听听大佬们对于这段代码的时间复杂度的看法

[noe132]

如果某个阶乘问题大小的规模是 n，需要 t 的时间
当问题大小扩大到 2n，需要的时间则是 2t。

所以阶乘的时间复杂度是 O(n)

js 目前大部分引擎没有实现尾递归优化

[Rasphino]

尾递归优化不会影响复杂度的吧…只是消除频繁栈操作的开销

[ine181x]

是否有尾递归优化不涉及算法时间复杂度的变化。

[dartabe]

如果没有优化 是不是不如写成 for 循环?? 不过前端好像也不在意这个问题?

[Mistwave]

这两个问题没有关系
复杂度是运行时间和数据规模的**数学函数**
尾递归优化是编译成循环，消除调用栈的累积，避免爆栈

[Alander]

@noe132 js 确实对尾递归优化做的没那么准确

@ine181x
@Rasphino 所以只是影响了空间复杂度而不会影响时间复杂度吗？


@dartabe 突然看文章想到这个问题，文中大多写复杂度降为 O(1)，但是我就不明白时间复杂度是否变化


@Mistwave 你的 复杂度是运行时间和数据规模的**数学函数** 这个说法我觉得很对，所以你认为是尾递归优化和时间复杂度其实根本没有关系是嘛？那尾递归可以将空间复杂度降低？

[gaoryrt]

是这篇文章么，我评论的
我觉得是 O(n)，但是作者说是 O(1)

[gaoryrt]

忘了上链接： https://segmentfault.com/a/1190000020694801?_ea=21358770

[PALELESS]

有这个标准, 但是, 目前并没有实现
而且逐渐烂尾了
所以你这么写和不用尾递归并没有什么不同
当然我有段时间没关注过了, 不过也没有听说实现优化的新闻

[gaoryrt]

同事给了段代码对比尾递归优化：
```
int f(int n, long long t){
if (n == 1) {
return t;
}
return f(n-1, n * t);
}

(gdb) disassemble f
Dump of assembler code for function f(int, long long):
0x0000000000400abd <+0>: push %rbp
0x0000000000400abe <+1>: mov %rsp,%rbp
0x0000000000400ac1 <+4>: sub $0x10,%rsp
0x0000000000400ac5 <+8>: mov %edi,-0x4(%rbp)
0x0000000000400ac8 <+11>: mov %rsi,-0x10(%rbp)
0x0000000000400acc <+15>: cmpl $0x1,-0x4(%rbp)
0x0000000000400ad0 <+19>: jne 0x400ad8 <f(int, long long)+27>
0x0000000000400ad2 <+21>: mov -0x10(%rbp),%rax
0x0000000000400ad6 <+25>: jmp 0x400af2 <f(int, long long)+53>
0x0000000000400ad8 <+27>: mov -0x4(%rbp),%eax
0x0000000000400adb <+30>: cltq
0x0000000000400add <+32>: imul -0x10(%rbp),%rax
0x0000000000400ae2 <+37>: mov -0x4(%rbp),%edx
0x0000000000400ae5 <+40>: sub $0x1,%edx
0x0000000000400ae8 <+43>: mov %rax,%rsi
0x0000000000400aeb <+46>: mov %edx,%edi
0x0000000000400aed <+48>: callq 0x400abd <f(int, long long)>
0x0000000000400af2 <+53>: leaveq
0x0000000000400af3 <+54>: retq
End of assembler dump.

(gdb) disassemble f
Dump of assembler code for function f(int, long long):
0x0000000000400b70 <+0>: cmp $0x1,%edi
0x0000000000400b73 <+3>: mov %rsi,%rax
0x0000000000400b76 <+6>: je 0x400b9b <f(int, long long)+43>
0x0000000000400b78 <+8>: lea -0x2(%rdi),%esi
0x0000000000400b7b <+11>: xor %edx,%edx
0x0000000000400b7d <+13>: movslq %edi,%rdi
0x0000000000400b80 <+16>: add $0x1,%rsi
0x0000000000400b84 <+20>: nopl 0x0(%rax)
0x0000000000400b88 <+24>: mov %rdi,%rcx
0x0000000000400b8b <+27>: sub %rdx,%rcx
0x0000000000400b8e <+30>: add $0x1,%rdx
0x0000000000400b92 <+34>: imul %rcx,%rax
0x0000000000400b96 <+38>: cmp %rsi,%rdx
0x0000000000400b99 <+41>: jne 0x400b88 <f(int, long long)+24>
0x0000000000400b9b <+43>: repz retq
End of assembler dump.
```

上面一段没有优化，push callq leave 就一直进栈到最后再一个个出栈
下面的优化过，就是 jne 循环

优化的是栈吧

[Alander]

@gaoryrt 十分感谢，从这段来看就是对栈的优化，谢谢你的解答

[Alander]

@PALELESS 嗯嗯，就当知道个概念吧

[Alander]

@gaoryrt 哈哈哈哈，这篇我也在翻阅资料的时候看到了

[redbuck]

尾递归优化还没有哪个浏览器实现吧

[RHxW]

@gaoryrt 这个文章里说的是空间复杂度吧？

[azh7138m]

@redbuck safari:我对你来说就是个笑话吗？
不是不能做，优化后调用栈会变的不一样，debug 的时候就会很奇怪

[111qqz]

尾递归优化应该不影响时间复杂度吧，所以就是 O(n)?

[Alander]

@111qqz 按照上面大佬们的意思是的，而且尾递归优化浏览器方面也做的不好

[redbuck]

@azh7138m

http://kangax.github.io/compat-table/es6/#xs6

看了下,主流设备只有苹果家实现了啊😂

[azh7138m]

@redbuck 我猜是没啥开发者用 safari 所以影响不大，就上了（