javascript - 反转字符串 : Recursion vs iteration in javascript

Question

一个月前，我接受了一些 google PTO 成员的采访。其中一个问题是:js递归反转字符串并用大O符号解释运行时间

这是我的解决方案:

function invert(s){
    return (s.length > 1) ? s.charAt(s.length-1)+invert(s.substring(0,s.length-1)) : s;
}

我觉得很简单。

而且，关于大 O 表示法，我很快回答了 O(n)，因为运行时间与输入线性相关。 - 沉默 - 然后，他问我，如果你通过迭代实现它，在运行时间方面有什么不同？

我回答说，有时编译器将递归“翻译”为迭代(一些编程语言类(class)内存)，因此在这种情况下迭代和递归没有区别。顺便说一句，因为我没有关于这个特定问题的反馈，而且面试官没有回答“好”或“不”，我想知道你是否同意我的看法，或者你是否可以解释一下是否存在差异2 种实现方式。

非常感谢和问候!

Answer 1

在我看来，您的解决方案复杂度为 O(n²)。对 substring 的调用很可能是 O(n) — 典型的实现将为新字符串分配空间，然后复制子字符串。 [但请参阅评论。] 字符串连接 + 也可能是 O(n)。 length 甚至可能是 O(n)，但我认为这不太可能。

---

您提出了编译器可以将递归转换为迭代的想法。这是事实，但它很少在函数式语言和 Scheme 之外实现；通常唯一应用的转换是尾递归消除。在您的代码中，递归不在尾部位置:在递归调用invert 之后，您仍然需要计算+。因此尾递归消除不适用于您的代码。

这意味着 invert 的迭代版本必须以不同的方式实现。它可能具有相同或不同的复杂性，在我们看到它之前我们不能说。