这是一个创建于 1872 天前的主题，其中的信息可能已经有所发展或是发生改变。
当写出一段代码用尾递归来计算阶乘时：
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)转换为这个常量整体是否需要一定时间？这段代码的时间复杂度是怎么算出来的呢？
我太菜了，想听听大佬们对于这段代码的时间复杂度的看法
第 1 条附言 · 2019-10-16 12:22:21 +08:00
感谢大家的回答，目前按照各位大佬给出的资料来看：尾递归只是在对栈进行优化，js 对于尾递归优化可能没做啥优化，我个人在 nodejs 和 chrome 中执行尾递归代码都报了爆栈的 error
 |
1
noe132 2019-10-16 11:20:46 +08:00
如果某个阶乘问题大小的规模是 n，需要 t 的时间
当问题大小扩大到 2n，需要的时间则是 2t。 所以阶乘的时间复杂度是 O(n) js 目前大部分引擎没有实现尾递归优化 |
 |
2
Rasphino 2019-10-16 11:23:01 +08:00
尾递归优化不会影响复杂度的吧…只是消除频繁栈操作的开销
|
 |
3
ine181x 2019-10-16 11:24:03 +08:00
是否有尾递归优化不涉及算法时间复杂度的变化。
|
 |
4
dartabe 2019-10-16 11:32:36 +08:00
如果没有优化 是不是不如写成 for 循环?? 不过前端好像也不在意这个问题?
|
 |
5
Mistwave 2019-10-16 11:32:39 +08:00 via iPhone
这两个问题没有关系
复杂度是运行时间和数据规模的**数学函数** 尾递归优化是编译成循环，消除调用栈的累积，避免爆栈 |
 |
6
Alander OP |
 |
7
gaoryrt 2019-10-16 11:40:47 +08:00
是这篇文章么，我评论的
我觉得是 O(n)，但是作者说是 O(1) |
|
8
gaoryrt 2019-10-16 11:40:58 +08:00
|
 |
9
PALELESS 2019-10-16 11:48:07 +08:00
有这个标准, 但是, 目前并没有实现
而且逐渐烂尾了 所以你这么写和不用尾递归并没有什么不同 当然我有段时间没关注过了, 不过也没有听说实现优化的新闻 |
|
10
gaoryrt 2019-10-16 12:06:51 +08:00
同事给了段代码对比尾递归优化：
``` 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 循环 优化的是栈吧 |
 |
14
redbuck 2019-10-16 12:47:43 +08:00 via Android
尾递归优化还没有哪个浏览器实现吧
|
 |
16
azh7138m 2019-10-16 13:30:43 +08:00
@redbuck safari:我对你来说就是个笑话吗？
不是不能做，优化后调用栈会变的不一样，debug 的时候就会很奇怪 |
 |
17
111qqz 2019-10-16 14:04:07 +08:00
尾递归优化应该不影响时间复杂度吧，所以就是 O(n)?
|
|
19
redbuck 2019-10-16 16:12:54 +08:00
|
 |
21
secondwtq 2019-10-16 22:49:16 +08:00
我之前稍微研究过这个问题
印象是实现 PTC 处理 stacktrace 会有麻烦，V8 觉得不值当的就还没做 估计看这熊样到 V8 死了也不会做了 另外 PTC 的定义大概只是类似于”tail call 使用 O(1) 空间“之类的，跟时间复杂度没关系，跟实际性能也没关系 |
Select Language